What is the pigeonhole principle? Show that binomn+1k=binomnk−1+binomnk where n and k are positive integers with n≥k .[5]
2.
What is permutation? What is the next permutation in lexicographic order after 362541?[5]
Induction and Recursion
1.
State ceiling function and floor function with examples. How mathematical induction can be used to prove the correctness of recursive algorithm? Illustrate with an example.[5]
Number Theory
1.
Prove that 2 is irrational number.[5]
2.
Solve the system of following congruences using Chinese Remainder theorem: x = 2 (mod 3), x = 3 (mod 5), x = 2 (mod 7)[5]
Sets, Relations and Functions
1.
Explain how set operations can be represented using venn diagram with example.Convert the following sentences using quantifier: a.) Not all good peoples are heroes. b.) Every peoples in our country are loyal. c.) Some people hate good people.[10]
2.
Explain one-to-one and onto function with example. What is identity function?[5]
3.
How can you represent relations using matrices? Explain with suitable example.[5]
Tree and Graphs
1.
What does connectivity in graphs mean? Differentiate between permutation and combination.Solve the recurrence relation an=7an−1−10an−2 with initial conditions a0 = 2 and a1 = 3.[4+6]
2.
Describe pre-order, postorder and inorder traversal of a tree with an example.[5]
3.
Explain incidence matrix representation of a graph with example.[5]
4.
Define tree traversal. Explain pre-order traversal with example.[5]