R20/R19/R18
[Accredited by NAAC & NBA, Approved by AICTE New Delhi & Permanently Affiliated to JNTUH]
Aziznagar Gate, ChilkurBalaji Road, Hyderabad - 500 075. Subject Code: A43504/A33505/A23505
II B. Tech. I SEMESTER SUPPLEMENTARY EXAMINATION, DEC/JAN-2022-23
Subject: Mathematical Foundations of Computer Science Branch: CSE,IT,AI & CSE(DS)
Time: 3 hours Max Marks: 75
Note: This Question Paper contains two Parts A and B. Answer all the questions.
Part A is compulsory which carries 25 marks. Ten questions from five units.
Part-B consists of 5 Questions (numbered from 11 to 15) carrying 10 marks each.
Bloom's Level:
Remember L1 Apply L3 Evaluate L5
Understand L2 Analyze L4 Create L6
PART-A 25 Marks Outcomes Bloom's
Marks
ANSWERALLTHEQUESTIONS CO PO Level
Write the converse and contra positive of the statement: “If P is a
1 1 1-12 L1 2M
square, then P is a rectangle”?
Rewrite the following statement informally without quantifiers or
2 1 1-12 L2 3M
variables, ɏx€R, if x>2 then x2 >4
3 Distinguish pigeonhole principle with its extended version. 2 1-12 L3 2M
Find out how many 5-digit numbers greater than 30,000 can
4 2 1-12 L5 3M
be formed from the digits 1,2,3,4 and 5.
Use the binomial identifier to evaluate the sum 1.2.3 + 2.3.4
5 3 1-12 L3 2M
+...+ (n-2)(n-1)n.
6 Find the coefficient of X20 in (X3 + X4 + X5 +…..+) 5. 3 1-12 L5 3M
7 Define equivalence relation with an example. 4 1-12 L1 2M
Compute the transitive closure of the relation
8 4 1-12 L3 3M
R={(1,1),(1,2),(1,3),(2,3),(3,1)} defined over a set S={1,2,3}.
9 What do you mean by chromatic number? 5 1-12 L2 2M
What do you mean by isomorphism? Give examples of
10 5 1-12 L4 3M
isomorphic graphs.
PART-B 5Q x 10M = 50Marks
ANSWER ALL THE QUESTIONS
11 Obtain the principal disjunctive normal form of the following
1 1-12 L5 10M
i) formula : P V (┐P → (Q V ( ┐Q → R)))
[OR]
Prove or disprove the following statements:
A) All men are mortal
ii) 1 1-12 L4 10M
B) All kings are men
Therefore, All kings are mortal
The question paper of DSM comprises questions divided into 2
12 i) groups of 5 questions each. In how many ways can an examine 2 1-12 L4 10M
answer 6 questions taking at least 2 questions from each group?
[OR]
P.T.O.
Outcomes Bloom's
Marks
CO PO Level
A computer password consists of a letter of the English alphabet
followed by 3 or 4 digits. Find
ii) 2 1-12 L4 10M
A) The total number of passwords that can be formed.
B) The total number of passwords in which no digit repeats.
Solve the following recurrence relation using substitution
13 i) method: 3 1-12 L4 10M
[OR]
Find the generating function for the following sequence:
ii) 3 1-12 L5 10M
What is Equivalence relation? Prove that R={(1,1), (1,2), (2,1),
14 i) (2,2), (3,3), (3,4), (4,3), (4,4), (5,5), (5,6), (6,5), (6,6)} is 4 1-12 L4 10M
Equivalence relation.
[OR]
Define a poset. Give any two partial ordering relations. Draw the
ii) Hasse diagram for the relation R={(x, y) | x divides y} 4 1-12 L3 10M
on ={2, 3,6,12,24,36}.
What is a Hamiltonian Cycle? Draw bipartite graph K3,4 and
15 i) 5 1-12 L2 10M
prove that this graph does not have a Hamiltonian cycle.
[OR]
Construct spanning tree by applying BFS algorithm on the
following graph. Follow alphabetical order :
ii) 5 1-12 L5 10M
***VJIT(A)***