2003 Andhra University MSc Computer Science Discrete Mathematical Structures Question paper for exam preparation. Question paper for 2003 Andhra University MSc Computer Science Discrete Mathematical Structures Question paper, 2003 Andhra University MSc Computer Science Discrete Mathematical Structures Question paper. SiteMap
K2Questions Logo

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.



About us | SiteMap | Terms of use | Privacy Policy | Disclaimer | Contact us | ©2010 K2Questions.com