BIT Discrete Structure

Define graph isomorphism with an example. Using Kruskal's algorithm generate the Minimum Spanning Tree from following graph.

What are the uses of randomized algorithm? Find the solution to the recurrence relation \(a_n = 6a_{n-1} - 11a_{n-2} + 6a_{n-3}\) with the initial conditions \(a_0 = 2\), \(a_1 = 5\) and \(a_2 = 15\).

Define Boolean function, exponential function and partial ordering. List the computer representations for following set over universal set \(U = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}\).

a. Set that contains even number

b. Set that contains multiple of 5

c. Set that contains number greater than 7

d. Set that contains prime number

Define proposition. Convert the following sentences to predicate.

a. Some kind hearted peoples do still exist.

b. Student who study hard and do the homework get good marks in exam.

Prove that \(1^3 + 2^3 + 3^3 + \ldots + n^3\) is a perfect square using mathematical induction.

Find the multiplicative inverse of 6 in \(Z_{25}\) using Extended Euclidean Algorithm.

State generalized Pigeonhole principle. How many ways can you draw four digits integers without repetition of the digit.

Explain any two ways of representing the graph.

Compute the value of \(8 \text{ MOD } 8\), \(-9 \text{ MOD } 4\), \(7 \text{ MOD } 17\), \(6 \text{ MOD } 7\) and \(-8 \text{ MOD } 3\).

Using direct proof show that the sum of odd and even number is odd.

Define cut vertices and cut edges. How do you determine whether the graph has Euler circuit and Euler path?

Explain about structural induction and recursive definitions with example.