State generalized Pigeonhole principle. How many ways can we get the 3 digit integers without repeating the digit?[5]
Induction and Recursion
1.
Define randomized algorithm with an example.Solve the recurrence relation an=−4an−1−4an−2 for n≥2, with initial condition a0=0 and a1=1.[3+7]
2.
Using direct proof show that the sum of square of even number is even.[5]
Logic and Proof Methods
1.
List the negations of following statements: (a) He has passed the exam. (b) All dogs are loyal. (c) Some medicine has side effect. (d) If you study then you will pass the exam. (e) Open the door.[5]
2.
List any five rules of inferences.[5]
Number Theory
1.
How do you solve computer arithmetic with large integers using Chinese remainder theorem? Give an example.[5]
Sets, Relations and Functions
1.
What is Boolean matrix and list its operations?Prove that the sum of first N odd integers is N2 using mathematical induction.[4+6]
2.
Define equivalence relation. How do you represent relation?[5]
3.
How do you plot graph for function f(x)=x+1? Define ceiling, floor and exponential function.[5]
Tree and Graphs
1.
Differentiate between graph and tree.Describe about the necessary conditions for graphs to be isomorphic with an example.[2+8]
2.
How does Kruskal algorithm work? Illustrate with an example.[5]
3.
Write Dijkstra’s algorithm to find the shortest path from source node to goal node.[5]