Jawaharlal Nehru Technological University, Hyderabad MCA-I Semester Supplementary Examinations July 2010 DISCRETE STRUCTURES Question paper

Code No: 31001

Time: 3hours Max.Marks:60

Answer any Five questions
All questions carry equal Marks

1.a) Discuss about equivalence implications.
b) State and explain various normal forms.

2. What is meant by predicate? Describe the automatic theorem proving.

3.a) Let U = {1,2,3,4,5}, A = {1,5}, B = {1,2,3,4} and C = {2,5}. Determine the following sets.
i) (A?B)n(A?C)
ii) (AnB)?(B?C)
b) Discuss about Lattice and its properties.

4.a) What is meant by Group, Semi-Group, Sub-Group?
b) How many different license plates are there that involves 1,2 or 3 letters followed by 4 digits?

5.a) Show that C(r+m+n, r) C(m+n, m) = ( )! ! ! !
r m n
r m n
+ +.
b) What is the coefficient of x3x7 in (x+y)10?

6.a) Find a generating function to count the number of integral solutions to e1+ e2 + e3=10 if for each i, 0 i = e .
b) What is a Generating function? Discuss any one method of solving recurrence relation.

7.a) Discuss the Kruskal's algorithm for finding minimal spanning tree.
b) What is a graph? Discuss about chromatic numbers.

8. Write short notes on any three of the following.
a) Hamiltonian graphs
b) Planar graph
c) Isomorphism
d) Truth tables.