BITM Discrete Structure

Why do we need quantifier?

Define pseudorandom integer.

Give an example of recursively defined set.

When do you use sum rule?

Define simple graph.

What does prefix code mean?

Define logic.

How do you define hypothesis in strong induction?

Differentiate between homogeneous and non homogeneous recurrence relation.

Define binary search tree.

Compute the value of \(5 \bmod 6\), \(-5 \bmod 6\) and \(2 \bmod 2\).

Use the Extended Euclidean algorithm to find the GCD of 16 and 28.

What is chromatic number. Define graph coloring with its applications.

Find the minimum spanning tree from following graph using Prim's algorithm.

Create a BST from 6, 5, 8, 10, 2, 100 and traverse it in post order.

Solve the following linear congruence using Chinese Remainder Theorem.

\(x \equiv 1 \pmod 5\)

\(x \equiv 2 \pmod 7\)

Using mathematical induction prove that \(n! \geq 2n\) for \(n \geq 4\).

Using proof by contradiction, show that the sum of odd integers is even.

Solve the recurrence relation \(a_n = 3a_{n-1} - 2a_{n-2}\), with initial conditions \(a_0 = 1\) and \(a_1 = 2\).

Represent the following sentences using predicate.

a. Not all heroes are brave.

b. Employee who work overtime are awarded.

Define path, Hamilton path, Euler path and planar graph. Explain any two ways for representing graph with example.

(a) A company wants to hire a new team of five employees from a pool of 15 candidates. How many different possible teams can be formed if the company requires at least one male and two female?

(b) A group of 101 people attend a party. Show that there must be at least two people at the party who were born on the same day of the week.