# 2003 Andhra University MSc Computer Science Discrete Mathematical Structures Question paper

** University Question Papers **

**
**2003 Andhra University MSc Computer Science Discrete Mathematical Structures Question paper

M.Sc. DEGREE EXAMINATION - Computer Science

First Year First Semester

Discrete Mathematical Structures - November 2003

Time: 3 hours

Maximum: 75 marks

Answer Question No. 1 and any other FOUR.

Answer each question at one place only.

All questions carry equal marks.

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

b. State Demorgan's Laws for sets

c. What is absurdity? Give 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. Define Poset and given an example.

h. Define Hamiltonian graph.

i. What is minimal spanning tree? Give 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 one 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. Find the number of solutions of x1 + x2+ x3 = 20 where 2 =x1=5, 4 = x2 = 7 and -2 = x3 = 9.

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

5. a. A relation R on a set A is said 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 given below are isomorphic

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

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

7. a. Explain the procedure for obtaining BFS and DFS spanning trees of a given graph.

b. Show that in Boolean Algebra:

i. a.b1 + a1 - b = (a + b) . (a1+ b1)

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

8. a. Explain

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.