Why do we need principle of inclusion and exclusion? How many ways can we express the four character words ending with a digit and beginning three are lowercase alphabets. Be sure that none of the character can be repeated. Using induction, show that $3^n-1$ is multiple of 2 for n $\geq$ 1. [5+5]
2.
What is generalized pigeonhole principle. If a class has 24 students, what is the maximum number of possible grading that must be done to ensure that there at least two students with the same grade. [5]
Induction and Recursion
1.
Use mathematical induction to prove that the sum of the first n odd positive integers is $n^2$. [5]
2.
What is 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]
Logic and Proof Methods
1.
Give any four examples that are not propositions. Assume the premises, all over smart persons are stupid, children of stupid persons are naughty, John is over smart, Sam is children of John. Using rules of inferences, show that Sam is naughty. [10]
2.
Show that the sum of two even numbers is even using direct proof. [5]
Number Theory
1.
What is arithmetic modulo $m$? Use the definition of addition and multiplication in $\mathbb{Z}_m$ to find $7 +_{11} 9$ and $7 *_{11} 9$. [5]
Sets, Relations and Functions
1.
Define power set. What is the power set of the set A= {1,2, 3, 4}? [5]
2.
Explain one-to-one correspondence with example. What is identity function? [5]
3.
Define equivalence relation with an example. [5]
Tree and Graphs
1.
State necessary and sufficient conditions for a graph to have Euler path and circuit. Find the GCD of 12 and 18 using Extended Euclidian Algorithm. [4+6]
2.
Write the Dijkstra's algorithm to find the shortest path between two nodes in graph. [5]