Discrete Structure 2078

Section A

Long Answer Questions

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

1. Explain direct proof, indirect proof, and proof by contradiction. Use direct proof to show that "If n is an odd integer, then n² is an odd integer". Also, use indirect proof to show that "If n is an integer and n² is odd then n is odd".         (6+2+2)

2. What is linear nonhomogeneous recurrence relation of degree k with constant coefficients? 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.     (2+6+2)

3. Define spanning tree and minimum spanning tree with suitable example. Use Kruskal's algorithms to find minimum spanning tree in the given graph.     (4+6)

Section B

Short Answer Questions

Attempt any eight questions.     (8×5=40)

4. What is tautology? Show (p ∧q)→(p∨q) is a tautology.

5. Define cartesian product. Find A³ for the set A= {a, b, c}. (1+4)

6 How can you represent relations using matrices? Suppose that A= {1, 2, 3} and B= {1, 2}. Let R be the relation from A to B containing (a, b) if a ∈A, b ∈B, and a > b. What is the matrix representing R if a₁= 1, a₂= 2, and a₃= 3, and b₁= 1 and b₂=2?     (2.5+2.5)

7. Use mathematical induction to show that the sum of first n positive integers is .

8. What is congruent modulo? Determine whether 20 is congruent to 8 modulo 6 and 25 is congruent to 17 modulo 5.     (3+2)

9. Explain trial division with example? Using trial division, show that 101 is prime. (2+3)

10. Explain product rule. How many strings are there of four lowercase letters that have the letter x in them?         (2+3)

11. What is graph? Explain simple graph and pseudograph with example.         (1+2+2)

12. What is Euler path? Compare it with Hamilton path.     (2+3)