Discrete Structure 2065

Attempt all questions:

Group A (10x2=20)

1. Given propositions p and q, define conjunction and disjunction of them.

2. Define existential quantifications with suitable examples.

3. State which rule of inference is basis of the following argument: “It is below freezing and raining now, therefore, it is below freezing now.”

4. State and prove the Pigeonhole principle.

5. Define linear homogeneous recurrence relation.

6. Define the terms a language over a vocabulary and the phrase-structure grammar.

7. Distinguish between deterministic and nondeterministic finite state automaton.

8. Define the complete graph K_n on n vertices and the complete bipartile graph K_m,n with suitable examples.

9. Which of the undirected graphs in the following figure have an Euler circuit? Explain.

10. What is the chromatic number of the complete bipartile graph K_m,n , where m and n are positive integers?

Group B (5x4=20)

11. Explain the 4 rules of inference for quantified statements.

12. Find an explicit formula for the Fibonacci numbers, with recursion relation f_n−1 + f_n−2 and f₀ = 0 , f₁ = 1

13. Define finite-state with output with suitable examples.

OR

Define deterministic finite state automata. When are two finite state automata equivalent? Give an

example.

14. Show that the graphs in the following figure are not isomorphic.

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

15. Prove that an undirected graph is a tree if there is a unique simple path between any two of its vertices.

Group C (5x8=40)

16. Explain Tautologies, contradiction and contingencies with suitable examples.

OR

Explain the method of proving theorems by direct, indirect, contradiction and by cases.

17. Define linear homogeneous recursion relation of degree K with constant coefficient with suitable examples. What

is the solution of the recurrence relation a_n = a_n−1 + 2_an−2 with a₀ = 2 and a₁ = 7?

18. Let G 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}. What is L(G), the language of this grammar?

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

20. Define Euler and Hamiltonian circuits and paths with examples illustrating the existence and nonexistence of them.

OR

Discuss the shortest path algorithm of Dijkstra for finding the shortest path between two vertices. Use this algorithm to find the length of the shortest path between a and z in the following weighted graph?

Give the idea of travelling salesman problem and the difficulties of solving it.