Jawaharlal Nehru Technological University Hyderabad 2010-1st Sem M.C.A -ester Supplementary s MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE - Question Paper

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
MCA-I Semester Supplementary exams July 2010
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE
Time: 3hours Max.Marks:60
ans any 5 ques.
All ques. carry equal Marks
- - -
1. a) Construct truth table for every of the subsequent compound statements.
i) (P?Q)?(7P?Q)
ii) P?(7Q?r).
b) find the principal conjunctive normal form of the formula S provided by
(7P?R)?(Q?P).
2. With reference to automatic theorem proving, show that S ? R is tautologically
implied by(P?Q)?(P?R)?(Q?S).
3. a) Let C be a collection of sets which are closed under union and intersection. Verify
whether (C,n,?) is a lattice.
b) Show that there are only 5 distinct Hasse diagrams for partially ordered sets
that contains 3 elements.
4. a) H is a non-empty complex of a group. Prove that the necessary and sufficient
condition for H to be a subgroup of G is a, b ? H ? ab-1? H, where b-1 is the
inverse of b in G.
b) Prove that any two simple connected graphs with 'n' vertices, all of degree 2, are
isomorphic.
5. a) In how many ways can three boys share 15 various sized apples if every takes 5?
b) State and discuss the applications of Pigeon hole principle.
6. a) Solve the recurrence relation r r1 r2 a a a - - = + using generating function.
b) Solve 2
1 two four 4 ( 1) n n n a a a n - - - + = + provided a0 = 0, a1 = 1.
7. a) discuss the algorithm for breadth 1st search traversal of a graph.
b) What is a minimum spanning tree? elaborate the various ways of creating
minimum spanning trees?
8. a) obtain the chromatic numbers of
i) a bipartite graph K3,3
ii) a complete graph Kn and
iii) a wheel graph W1,n
b) Prove that the Kurtowskis 2nd graph consisting of six vertices and nine edges is
non-planar.
*****
R09

Earning:   Approval pending.