Discrete Structure 2067

Attempt all questions:

Group A (10x2=20)

1. What do you mean by proposition? Give example to justify your answer.

2. How do you define logically equivalent propositions?

3. Give examples of addition rule and simplification rule of inference.

4. State and prove the Pigeonhole principle.

5. How many ways are there to select a first, second and third – prize winners from 10 different people?

6. Discuss the types of phrase structure grammars and their relations.

7. Give formal definition of regular expressions over a set I.

8. Verify the Handshaking theorem in the figure.

9. Is the graph K4 planar? How?

10. Determine the chromatic number K_n.

Group B (5x4=20)

11. Explain the 2 rules of inference for quantified statements and give suitable examples.

OR

Show that the propositions pV( p ᴧ r ) and ( rV q) ᴧ ( p V r) are logically equivalent.

12. Define the binomial coefficient and give the general term of the binomial coefficient. Show that the sum of the binomial coefficient is 2ⁿ.

13. How do you distinguish deterministic and nondeterministic finite-state automaton? Give suitable examples.

14. Determine whether the graphs shown in the following figure are isomorphic.

What can you say about the graph isomorphism algorithms in terms of efficiency?

15. Prove that a tree with n-vertices has n-1 edges.

Group C (5x8=40)

16. Discuss the techniques of direct proof indirect proof and vacuous proof for proving implications with suitable examples.

17. Find the solution to the recursion relationan = 6a_n-1 – 11a_n-2 + 6a_n-3 with initial conditions a₀ = 2, a₁ = 5 and a₂ = 15.

OR

Suppose that a person deposits Rs.10,000/- in a fixed account at a bank yielding 11% per year with interest

compounded annually. How much will be in the account after 10 years? Solve the problem with modeling it into

recursion relations.

18. What do you mean by phase-structure grammar? Let C1 be the grammar with vocabulary V = {S, 0, 1}; set of terminals T= {0, 1}; starting symbol S, and productions P= {S→11s, S→0}. Determine the language L(G) of this grammar.

19. Explain the concept of network flows and max-flow min-cut theorem with suitable examples.

OR

Define Euler circuit and Euler path with suitable examples. Give the multi-graph model of the two of Koenigsberg state a necessary and sufficient condition for Euler circuit in connection to your definitions and models.

20. Discuss the Algorithm of Dijkstra for finding the shortest path in a weighted graph between two vertices with suitable example. Moreover, explain the travelling salesman problem and the efficiency of algorithm for solving this problem.