Brief Answer Questions:
[10 × 1 = 10]State inference rule for universal instantiation.
What is difference between strong and weak induction?
What is the value of -2 MOD 5?
Give an example of fallacy.
How do recursive algorithms differ with iterative algorithms?
What is the multiplicative inverse of 28 modulo 1000?
List any two applications of recurrence relations.
Define planar graph.
What do you mean by connectivity of graph?
What is prefix code?
Short Answer Questions: (Attempt any FIVE Questions)
[5 × 3 = 15]Use the Chinese Remainder Theorem to solve the following congruences
x ≡ 2 MOD 3
x ≡ 3 MOD 4
x ≡ 1 MOD 5
Use the Extended Euclidean algorithm to find the GCD of 20 and 24.
Using mathematical induction show that n³ + 2n is divisible by 3, n ≥ 0.
Using Dijkstra's Algorithm, find the shortest distance from source vertex 'A' to 'D' and 'E' in the following graph.
Justify if the graphs shown below are isomorphic or not.
Find the minimum spanning tree from following graph using Prim's Algorithm.
Long Answer Questions: (Attempt any THREE Questions)
[3 × 5 = 15]Apply Chinese remainder theorem in computer arithmetic with large integers to find the sum of 123684 and 413456.
Prove that the following recursive algorithm to compute aⁿ, is correct using mathematical induction.
int power(int a, int n)
{ if (n == 0) return 1;
else return a * power (a, n - 1);}
Differentiate between permutation and combination. A box contains 2 white balls, 3 black balls and 4 red balls. In how many ways can 3 balls can be drawn from the box such that at least one ball black most be included.
Trace the path from 0 to 6 in following graph using BFS and DFS.
Comprehensive Answer / Case / Situation Analysis Questions:
[2 × 10 = 20]List the negation of quantifier with example. Prove that √2 is irrational.
(a) Expand (x + y)⁵ using the binomial theorem.
(b) Use Pascal's identity to prove that the sum of the first n positive integers is equal to n(n+1)/2.