Andhra University 2003 M.Sc Computer Science Discrete Mathematical Structures - Question Paper

M.Sc. DEGREE exam - Computer Science

First Year 1st Semester

Discrete Mathematical Structures - November 2003

Time: three hours
Maximum: 75 marks

ans ques. No. one and any other FOUR.

ans every ques. at 1 place only.

All ques. carry equal marks.

1. a. Prove P -> Q = -PVQ

b. State Demorgan's Laws for sets

c. What is absurdity? provide example.

d. What is ICM of 233572 and 2433?

e. State Pigeon-hole principle

f. Solve the recurrence relation an- an-1 = 2, a0 = 1.

g. describe Poset and provided an example.

h. describe Hamiltonian graph.

i. What is minimal spanning tree? provide an example.

j. Simplify B. (A+B)

2. a. Show that
i. [(p->q) ? ~ P] -> ~q is a fallacy.
ii. [(P -> q) ? ~q] -> ~p is a tautology.

b. Prove that (AUC)C = AC n BC and (A nB)C = AC? BC

3. a. How many 4-digit telephone numbers have 1 or more repeated digits.

b. Prove that n + mcr = nCo mCr + nC1 mCr-1 + . . . + nCr mCo for integers n7, r7, 0, m7, r7, 0

4. a. obtain the number of solutions of x1 + x2+ x3 = 20 where two =x1=5, four = x2 = seven and -2 = x3 = 9.

b. find the solution of Fibonacci relation by using generating function.

5. a. A relation R on a set A is stated to be circular if, for all a,b,c&isn;A(a,b) &isn;R and (b,c) &isn;R imply that (c,a) &isn;R. Prove that R is reflexive and circular if R is an equivalence relation.

b. Determine whether the graphs provided beneath are isomorphic

6. a. Prove that a multgraph has an Euler path if an only if it is connected and has 'O' or exactly two vertices of odd degree.

b. A tree with n vertices has exactly n-1 edges.

7. a. discuss the procedure for obtaining BFS and DFS spanning trees of a provided graph.

b. Show that in Boolean Algebra:
i. a.b1 + a1 - b = (a + b) . (a1+ b1)

ii. (a.b) + [(a+b1).b] one = one

8. a. discuss
i. Equivalent states of a finite state machine.
ii. Simplification of machines

b. Show that, if the language L is recognized by a non deterministic finite state automation Mo than L is also recognized by a deterministic finite state automation.

Earning:   Approval pending.