How many 3 digits numbers can be formed from the digits 1,2,3,4 and 5 assuming that:a. Repetitions of digits are allowed b. Repetitions of digits are not allowed [5]

Define ceiling and floor function. Why do we need Inclusion - Exclusion principle? Make it clear with suitable example. [5]

State pigeonhole principle. Solve the recurrence relation $a_n = 3a_{n-1} - 3a_{n-2} + a_{n-3}$, with initial conditions $a_0 = 1, a_1 = 3, a_2 = 7$. [10]

Prove that for every positive integer $n \geq 1, n^2 + n$ is even integer using mathematical induction. [5]

Find the value of x such that x = 1 (mod 3), x = 1 (mod 4), x = 1 (mod 5) and x = 0 (mod 7) using Chinese remainder theorem. [10]

Define reflexive closure and symmetric closure. Find the remainder when $4x^2 - x + 3$ is divided by x + 2 using remainder theorem. [5]

All over smart people are stupid. Children of stupid people are naughty. John is a children of Jane. Jane is over smart. Represent these statements in FOPL and prove that John is naughty. [5]

Define Euler circuit with suitable example. Find the maximal flow s to t from the given network flow. [10]

Which of the following are possets? $\text{a. } (Z, =)$ $\text{b. } (Z, \neq)$ $\text{c. } (Z, \leq)$ [5]

Define Euler path and Hamilton path. Give examples of both Euler and Hamilton path. [5]

What is minimum spanning tree? Explain Kruskal's algorithm for finding minimum spanning tree. [5]

List any two applications of graph coloring theorem. Prove that 'A tree with n vertices has n-1 edges'. [5]