Discrete Structure 2071

Attempt all questions:

Group A (10x2=20)

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

2. Discuss universal quantifier with example.

3. Define universal instantiation.

4. How many different license plates is available if each plate contains sequence of three letters followed by three digits?

5. How many students must be in a class to guarantee that at least two students receive the same score on the final exam, if the exam is graded on a scale from 0 to 100 points?

6. Define cut vertices and cut edges.

7. Suppose that a planar simple graph has 20 vertices, each of degree 3. Into how many region does a representation of this planar graph split the plane?

8. What is minimal cut?

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

10. 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?

Group B (5x4=20)

11. Use mathematical induction to prove that the sum of the first n odd positive integers is n²?

OR

Discuss Modus Ponens with suitable example.

12. What is binomial theorem? Use this theorem to find the coefficient of x¹² y¹³ in the expansion of(2x – 3y)²⁵.

13. Show that K3,3 is not planar?

14. Show that a tree with n vertices has n-1 edges.

15. Construct a nondeterministic finite-state automaton that recognizes the regular set 1* ∪ 01.

Group C (5x8=40)

16. Discuss direct proof, indirect proof, and proof by contradiction with suitable example.

17. What is shortest path problem? Find the length of a shortest path between a and z in the given weighted

graph.

18. Find the recurrence relation to find the number of moves needed to solve the TOH (Tower of Hanoi) problem with n disks. Discuss application of recurrence relation in divide-and-conquer algorithms.

19. An undirected graph is a tree if and only if there is a unique simple path between any two of its vertices.

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