BITM Discrete Structure

Why do we need quantifier?

Define logic.

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

Represent the following sentences using predicate.

a. Not all heroes are brave.

b. Employee who work overtime are awarded.

State inference rule for universal instantiation.

Give an example of fallacy.

List the negation of quantifier with example. Prove that \(\sqrt{2}\) is irrational.

Define pseudorandom integer.

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.

Solve the following linear congruence using Chinese Remainder Theorem.

\(x \equiv 1 \pmod 5\)

\(x \equiv 2 \pmod 7\)

What is the value of \(-2\ \mathrm{MOD}\ 5\)?

What is the multiplicative inverse of 28 modulo 1000?

Use the Chinese Remainder Theorem to solve the following congruences

\(x \equiv 2\ \mathrm{MOD}\ 3\)

\(x \equiv 3\ \mathrm{MOD}\ 4\)

\(x \equiv 1\ \mathrm{MOD}\ 5\)

Use the Extended Euclidean algorithm to find the GCD of 20 and 24.

Apply Chinese remainder theorem in computer arithmetic with large integers to find the sum of 123684 and 413456.

Give an example of recursively defined set.

How do you define hypothesis in strong induction?

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

What is difference between strong and weak induction?

How do recursive algorithms differ with iterative algorithms?

Using mathematical induction show that \(n^3 + 2n\) is divisible by 3, \(n \ge 0\).

Prove that the following recursive algorithm to compute \(a^n\), is correct using mathematical induction.

int power(int a, int n)
{ if (n == 0) return 1;
  else return a * power (a, n - 1);}

When do you use sum rule?

(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.

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.

(a) Expand \((x + y)^5\) 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\).

Differentiate between homogeneous and non homogeneous recurrence relation.

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

List any two applications of recurrence relations.

Define simple graph.

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

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

Define planar graph.

What do you mean by connectivity of graph?

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.

Trace the path from 0 to 6 in following graph uing BFS and DFS.

What does prefix code mean?

Define binary search tree.

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.

What is prefix code?

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