Discrete Structure 2072

Attempt all questions:

Group A (10x2=20)

1. What is conjunction? Discuss with suitable example and truth table.

2. Show that (p∧q ) → p  is a tautology by using truth table.

3. What is valid argument?

4. In how many ways we can draw a heart or a diamond from an ordinary deck of playing cards?

5. What is pigeonhole principle?

6. Show that an undirected graph has an even number of vertices of odd degree.

7. What is minimum spanning tree?

8. Define saturated edge in a transport network.

9. What is a phrase-structure grammar?

10. What are the strings in the regular sets specified by the regular expression 10*.

Group B (5x4=20)

11. What is logical equivalence? Show that p→q  and ¬q → ¬q are logically equivalent.

OR

Discuss Modus Ponens with suitable example.

12. Discuss the principles of inclusion-exclusion. How many bit strings of length eight either start with a 1 bit or end with two bits 00?

13. What is graph isomorphism? What are the different invariants of graph isomorphism?

14. Discuss adjacency matrix representation of graph with example.

15. Let G be the grammar with vocabulary V = {S, 0, 1}, set of terminals T = {0, 1}, starting symbol S, and production P ={ S→ 11S,S→0}. What is the L(G) of this grammar?

Group C (5x8=40)

16. Discuss the different rules of inference for quantified statements along with suitable example of each.

17. Find all the solutions of the recurrence relation a_n  = 4a_{n −1}+n² . Also find the solution of the relation with initial condition  a₁ =1.

18. Discuss the algorithm for constructing Euler circuit with suitable example.

19. Discuss Kruskal’s algorithm for constructing a minimum spanning tree. Use this algorithm to find minimum spanning tree in the graph given below.

20. State and prove Max-Flow Min-Cut theorem.