Monday, November 15, 2010

Jawaharlal Nehru Technological University, Hyderabad M.C.A - I Semester Supplementary Examinations July 2010 MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE Question paper

Time: 3hours Max.Marks:60

Answer any Five questions
All questions carry equal Marks

1. a) Construct truth table for each of the following compound statements.
i) (P?Q)?(7P?Q)
ii) P?(7Q?r).
b) Obtain the principal conjunctive normal form of the formula S given 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 five distinct Hasse diagrams for partially ordered sets that contains three 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 2 simple connected graphs with 'n' vertices, all of degree 2, are isomorphic.

5. a) In how many ways can 3 boys share 15 different sized apples if each takes 5?
b) State and explain 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 2 4 4 ( 1) n n n a a a n - - - + = + given a0 = 0, a1 = 1.

7. a) Explain the algorithm for breadth first search traversal of a graph.
b) What is a minimum spanning tree? What are the different ways of creating minimum spanning trees?

8. a) Find 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 second graph consisting of 6 vertices and 9 edges is non-planar.

*****
R09

No comments:

Post a Comment