Discrete Structures 2076

Group A

Long answer questions:

Attempt any two questions: (2 x 10 = 20)

1. State pigeonhole principle. Solve the recurrence relation a_n = 3a_n-1 -  3a_n-2 + a_n-3 with initial conditions a₀=1 ,a₁ = 3, a₂=7.

2. Find the value of x such that x = 1 (mod 3), x = 1 (mod 4),  x = 1 (mod 5) and x = 0 (mod 7) using Chinese remainder theorem.

3. Define Eular circuit with suitable example. Find the maximal flow s to t from the given network flow. 

Group B

Short answer questions:

Attempt any eight questions: (8 x 5 = 40)

4. Prove that for every positive integer n ≥ 1, n²+n is even integer using mathematical induction.

5. All over smart people are stupid. Children of stupid people are naughty. John is a children of Jane. Jane is over smart. Represent these statements in FOPL and prove that John is naughty.

6. Which of the following are posets?

7. Define reflexive closure and symmetric closure. Find the remainder when 4x² - x + 3  is divided by x + 2 using remainder theorem.

8. Define Eular path and Hamilton path. Give examples of both Eular and Hamilton path.

9. How many 3 digits numbers can be formed from the digits 1,2,3,4 and 5 assuming that:

a. Repetitions of digits are allowed

b. Repetitions of digits are not allowed 

10. What is minimum spannung tree? Explain Kruskal's algorithm for finding minimum spanning tree.

11. List any two applications of graph coloring theorem. Prove that "A tree with n vertices has n-1 edges"

12. Define ceiling and floor function. Why do we need Inclusion - Exclusion principle? Make it clear withsuitable example.