Discrete Structure 2070

Attempt all questions:

Group A (10x2=20)

1. What is compound proposition? Discuss implication with suitable example.

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

Ram is hard working. If Ram is hard working, then he is intelligent. Therefore Ram is intelligent.

3. What is the coefficient of x¹² y¹³ in the expansion of (2x – 3y)²⁵ ?

4. Is the sequence {an} a solution of the recurrence relation a_n = -3a_n-1 + 4a_n-2 if a_n = 2n?

5. Define linear homogeneous recurrence relation of degree k with constant coefficients.

6. What is phrase-structure grammar?

7. What is regular expression?

8. What is chromatic number of a graph?

9. What is spanning tree?

10. State max-flow min-cut theorem.

Group B (5x4=20)

11. How many bit strings of length eight either start with a 1 bit or end with two bits 00?

12. Discuss the importance of recurrence relations in the analysis of divide-and-conquer algorithms.

13. 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}. Determine the language L(G) of this grammar.

14. Discuss adjacency matrix representation of a graph with suitable example.

15. Prove that “a simple graph is connected if and only if it has a spanning tree”.

Group C (5x8=40)

16. What is mathematical induction? Use mathematical induction to prove that1.1! + 2.2! + ... + n.n! = (n+1)! – 1, wherever n is a positive integer.

17. Solve the recurrence relation an = 2a_n-1 + 2a_n-2 + 2a_n-3 for n ≥ 3, a₀ = 3, a₁ = 6 and a₂ = 9.

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 without output with suitable example. What are the strings in the regular set specified by the regular expression 0* 1*?

19. Define an Euler circuit and Euler path in an undirected graph. How can it be determined whether an undirected graph has an Euler circuit and an Euler path? Explain with suitable example.

20. Define maximal flow and minimal cut and state and prove min-cut max-flow theorem.

OR

Find a maximal flow for the network shown in the figure below: