Discrete Structure 2073

Attempt all Question :

1. Show that the implication and its contrapositive are logically equivalent.

2. Which rule of inference is used in the following argument?

If I work all night on this homework, then I can answer all the exercise. IF answer

all the exercise, I will understand all the material. Therefore, if I work all night on

this homework, then I will understand the material.

3. Use binomial coefficient in the expansion of (x + y)⁴.

4. Determine whether the sequence {an} is solution of the recurrence relation a_n =2a_n−1 − a_n−2 where a_n = 3n.

5. Define linear nonhomogeneous recurrence relation of degree k with coefficients.

6. What is context free grammar?

7. Differentiate between DFA and NFA.

8. What is bipartite graph?

9. What is decision tree?

10.Define saturated and unsaturated edge?

Group B (5 x 4 = 20)

11. State and prove pigeonhole principle. What is the minimum number of student required in a discrete mathematics class to be sure that at least six receive the same grade, if there are five possible grades A, B, C, D, and F?

12. Discuss the importance of recurrence relation in the analysis pf divide – and – conquer algorithms.

13. Let G be the grammar with vocabulary V= {S, A, a, b}, set of terminals T ={a,b}, starting symbol S, and productions P ={S→aA, S→b, A→aa}. What is L(G), the language of this grammar?

14. What is planar graph? Show that K_3,3 is non-planar.

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

Group C (5 x 8=40)

16. Discuss direct =, indirect and vacuous proof with suitable example.

17. Find the solution to the recurrence relation an = 6a_n−1 − 11a_n−2 + 6a_n−3 with the initial conditions a₀ = 2, a₁ = 5, and a₂ = 15.

OR

Find the explicit formula for the Fibonacci numbers. Use f_n = f_n−1 + f_n−2 as recursive condition and f₀ = 0 and f₁ = 1 as initial condition.

18. Discuss finite state machine with output with suitable example. What are the strings in the regular set specified by the regular expression 01*0?

19. Describe Dijkstra’s algorithm for finding the shortest path in a weighted graph between two vertices with suitable example.

20. Find all S-D cuts in the following transport network. What is the value of a maximal flow?