Discrete Structure 2079

Section A

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

1. Give any four examples that are not propositions. Assume the premises: all oversmart persons are stupid, children of stupid persons are naughty, John is oversmart, Sam is a child of John. Using rules of inference, show that Sam is naughty. [4+6]

2. Why do we need the principle of inclusion and exclusion? How many ways can we express four-character words ending with a digit and beginning with three lowercase alphabets, ensuring no character is repeated? Using induction, show that 3ⁿ - 1 is a multiple of 2 for n ≥ 1. [2+3+5]

3. State the necessary and sufficient conditions for a graph to have an Euler path and circuit. Find the GCD of 12 and 18 using the Extended Euclidean Algorithm. [4+6]

Section B

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

4. Show that the sum of two even numbers is even using direct proof. [5]

5. Define power set. What is the power set of the set A = {1, 2, 3, 4}? [1+4]

6. Explain one-to-one correspondence with an example. What is an identity function? [3+2]

7. Use mathematical induction to prove that the sum of the first n odd positive integers is n². [5]

8. What is a recursively defined function? Suppose that f is defined recursively by f(0) = 3, f(n+1) = 2f(n) + 3. Find f(1), f(2), f(3), and f(4). [5]

9. What is arithmetic modulo m? Use the definition of addition and multiplication in Z_m to find 7 +₁₁ 9 and 7 *₁₁ 9. [2+3]

10. Define equivalence relation with an example. [5]

11. What is the generalized pigeonhole principle? If a class has 24 students, what is the maximum number of possible grades that must be done to ensure that at least two students have the same grade? [2+3]

12. Write Dijkstra's algorithm to find the shortest path between two nodes in a graph. [5]