Discrete Structures Model Question

Section A

Long Answer Questions.

Attempt any 2 questions.            [2 x 10 = 20]

1. Why breaking down of large integer into set of small integers is preferred while performing integer arithmetic? Find sum of numbers 123,684 and 413,456 by representing the numbers as 4-tuple by using reminders modulo of pair-wise relatively prime numbers less than 100.

2. Define linear homogeneous recurrence relation. Solve the recurrence relation a_n=a_n/2+n+1, with a₁=1.Also discuss about probabilistic primility testing with example.

3. How Zero-one matrix and diagraphs can be used to represent a relation? Explain the process of identifying whether the graph is reflexive, symmetric, or anti-symmetric by using matrix or diagraph with suitable example.

Section B

Short Answer Questions.

Attempt any 8 questions.            [8 x 5 = 40]

4. Prove that  by using set builder notation. How sets are represented by using bit string? Why it is preferred over unordered representation of sets?

5. How can you relate domain and co-domain of functions with functions in programming language? Discuss composite and inverse of function with suitable examples.

6. State Euclidean and extended Euclidean theorem. Write down extended Euclidean algorithm and illustrate it with example.

7. State and prove generalized pigeonhole principle? How many cards should be selected from a deck of 52 cards to guarantee at least three cards of same suit?

8. Represent the argument “If it does not rain or if is not foggy then the sailing race will be held and the lifesaving demonstration will go on. If sailing race is held then trophy will be awarded. The trophy was not awarded. Therefore it not rained” in propositional logic and prove the conclusion by using rules of inferences.

9. Discuss common mistakes in proof briefly. Show that n is even if n³+5 is odd by using indirect proof.

10. How mathematical induction differs from strong induction? Prove that 1²+2²+3²+........+n² = n(n+1)(2n+1)/6 by using strong induction.

11. Write down recursive algorithm for computing aⁿ. Argue that your algorithm is correct by using induction.

12. What is meant by chromatic number? How can you use graph coloring to schedule exams? Justify by using 10 subjects assuming that the pairs {(1,2), (1,5), (1,8), (2,4), (2,9), (2,7), (3,6), (3,7), (3,10), (4,8), (4,3), (4,10), (5,6), (5,7)} of subjects have common students.