--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
--- Content provided by FirstRanker.com ---
MCA I Semester Examinations, January - 2018
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE
--- Content provided by FirstRanker.com ---
Time: 3hrs--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
Max.Marks:75
--- Content provided by FirstRanker.com ---
Note: This question paper contains two parts A and B.Part A is compulsory which carries 25 marks. Answer all questions in Part A.
--- Content provided by FirstRanker.com ---
Part B consists of 5 Units. Answer any one full question from each unit. Each question
carries 10 marks and may have a, b, c as sub questions.
--- Content provided by FirstRanker.com ---
PART - A
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
5 ? 5 Marks = 25
1.a)
--- Content provided by FirstRanker.com ---
Give the formal definition of a well-formed formula in propositional logic with examples of
formulae that are well-formed and not-well-formed.
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
[5]b)
Draw the Hasse diagram for divisibility on the set
--- Content provided by FirstRanker.com ---
}
17
--- Content provided by FirstRanker.com ---
,16
,
--- Content provided by FirstRanker.com ---
13
,
--- Content provided by FirstRanker.com ---
11,
7
--- Content provided by FirstRanker.com ---
,
5
--- Content provided by FirstRanker.com ---
,3
{
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
[5]c)
What is a Pascal triangle? Expand the binomial expression
--- Content provided by FirstRanker.com ---
3
(2x y) using Pascal triangle. [5]
--- Content provided by FirstRanker.com ---
d)What is the general form of a non-homogeneous recurrence relation? Explain how the
solution is obtained.
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
[5]
--- Content provided by FirstRanker.com ---
e)
What is a spanning tree? Give the applications of a spanning tree.
--- Content provided by FirstRanker.com ---
[5]
PART - B
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
5 ? 10 Marks = 50
2.a)
--- Content provided by FirstRanker.com ---
Define the following terms and give examples.
i) Substitution Instance
ii) Logical equivalence
--- Content provided by FirstRanker.com ---
b)
Show that ( Q
--- Content provided by FirstRanker.com ---
(P Q)) P
using automatic theorem proving.
--- Content provided by FirstRanker.com ---
[5+5]
OR
--- Content provided by FirstRanker.com ---
3.a)
Write the following statements in predicate logic.
i) Everybody loves somebody
--- Content provided by FirstRanker.com ---
ii) There is somebody whom everybody lovesiii) Nobody loves everybody
iv) There is somebody whom no one loves.
b)
--- Content provided by FirstRanker.com ---
Find a CNF for ((
p (q r)) ( q
--- Content provided by FirstRanker.com ---
) ( r) )
p
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
[5+5]
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
4.a)
Let S
--- Content provided by FirstRanker.com ---
,
3
--- Content provided by FirstRanker.com ---
,2
,
--- Content provided by FirstRanker.com ---
1
{
--- Content provided by FirstRanker.com ---
...,}
15
--- Content provided by FirstRanker.com ---
,
14
--- Content provided by FirstRanker.com ---
and R be the equivalence relation on S defined by x y(mod ),5 that
is x y is divisible by 5. Find the partition of S induced by R.
--- Content provided by FirstRanker.com ---
b)
--- Content provided by FirstRanker.com ---
Define the following terms with examples:i) Permutation group
ii) Normal subgroup
iii) Cyclic group
iv) Kernel
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
[5+5]
--- Content provided by FirstRanker.com ---
OR
--- Content provided by FirstRanker.com ---
5.a)
Draw the following posets, and determine the maximal and minimal elements:
--- Content provided by FirstRanker.com ---
i) Divisors of 36 ordered by divisibilityii) The poset P(S) for S
}
--- Content provided by FirstRanker.com ---
2,
1
--- Content provided by FirstRanker.com ---
,
0
--- Content provided by FirstRanker.com ---
{ordered by subset relation.
b)
--- Content provided by FirstRanker.com ---
Simplify the following Boolean functions using Boolean algebra:
i) f ( ,
x ,
--- Content provided by FirstRanker.com ---
y z) xy (
x yz) x y
--- Content provided by FirstRanker.com ---
zii) f (x, y, z) xy xyz z
xy x yz
--- Content provided by FirstRanker.com ---
x z
y
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
[5+5]
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
6.a)
--- Content provided by FirstRanker.com ---
A multiple choice test contains 5 questions and each of these has four answer choices, withone correct answer per question. In how many ways can the questions be answered if only
one of the answer choices is selected and nothing is left blank? Explain.
b)
--- Content provided by FirstRanker.com ---
We choose 12 cards from the deck of 52 playing cards.
i) How many different ways can it be done?
ii) How many ways can it be done if they must all come from the same suit?
--- Content provided by FirstRanker.com ---
iii) How many ways can it be done if we need exactly 3 kings and 3 queens?iv) How many ways can it be done if all cards must have different face values?
[5+5]
--- Content provided by FirstRanker.com ---
OR7.a)
Fill in the numerators:
--- Content provided by FirstRanker.com ---
tC
4
--- Content provided by FirstRanker.com ---
4.3.2.1i)
7C
--- Content provided by FirstRanker.com ---
t
--- Content provided by FirstRanker.com ---
ii)t(t )
1 .. 1
--- Content provided by FirstRanker.com ---
.
b)
--- Content provided by FirstRanker.com ---
Explain pigeon hole principles.--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
[5+5]
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
x3
--- Content provided by FirstRanker.com ---
8.
Find the sequence generated by the function f (x)
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
[10]
1 x
--- Content provided by FirstRanker.com ---
OR--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
9.Solve the following recurrence relation using characteristic polynomial:
a 6a
--- Content provided by FirstRanker.com ---
11a
6a where a ,
--- Content provided by FirstRanker.com ---
2 a 5and a 15 .--- Content provided by FirstRanker.com ---
[10]
n
--- Content provided by FirstRanker.com ---
n 1n2
n3
--- Content provided by FirstRanker.com ---
0
1
--- Content provided by FirstRanker.com ---
2--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
10.a) Which of the following graphs have a Euler path/circuit? Explain
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
i.
--- Content provided by FirstRanker.com ---
ii.
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
iii.
b) Draw the planar representation of the following graph:
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
[5+5]
--- Content provided by FirstRanker.com ---
OR
11.a) Are the graphs given below bipartitie? Explain.
--- Content provided by FirstRanker.com ---
i.
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
ii.b) Draw all the subgraphs of the following graph.
--- Content provided by FirstRanker.com ---
[5+5]
--- Content provided by FirstRanker.com ---
---oo0oo---