Discrete Structure 2080

Section A

Long Answer Questions
Attempt any TWO questions. [2 × 10 = 20]

1. What is a proposition? Explain the rules of inference with examples. Prove that if n is an integer and n² is odd, then n is odd using proof by contraposition. [2+3+5]

2. Explain the principle of inclusion and exclusion with an example. How many ways can we arrange a four-character string starting with two digits followed by two lowercase letters, where no character is repeated? Using induction, prove that 1 + 3 + 5 + ... + (2n - 1) = n² for all positive integers n. [2+3+5]

3. What is a Hamiltonian circuit? Explain the conditions for a graph to have a Hamiltonian circuit. Find the GCD of 24 and 36 using the Euclidean Algorithm and express it as a linear combination of 24 and 36. [2+3+5]

Section B

Short Answer Questions
Attempt any EIGHT questions. [8 × 5 = 40]

4. Prove that the product of two odd integers is odd using direct proof. [5]

5. Define a Cartesian product. Find the Cartesian product of sets A = {a, b} and B = {1, 2, 3}. [1+4]

6. Explain injective and surjective functions with examples. What is a ceiling function? [3+2]

7. Use mathematical induction to prove that 2ⁿ > n² for all integers n ≥ 5. [5]

8. What is a recurrence relation? Solve the recurrence relation aₙ = 3aₙ₋₁ + 2 with initial condition a₀ = 1. [2+3]

9. Define modular arithmetic. Compute 8 +₁₃ 10 and 8 *₁₃ 10 in Z₁₃. [2+3]

10. Define a partial order relation with an example. [5]

11. Explain the pigeonhole principle with an example. If 30 students are in a class, what is the minimum number of students who must share the same birth month? [2+3]

12. Write short notes on:

• a. Graph isomorphism
• b. Tree traversal