BIT Discrete Structure

Explain how set operations can be represented using venn diagram with example. Convert the following sentences using quantifier.

a. Not all good peoples are heroes.

b. Every peoples in our country are loyal.

c. Some people hate good people.

State ceiling function and floor function with examples. How mathematical induction can be used to prove the correctness of recursive algorithm? Illustrate with an example.

What does connectivity in graphs mean? Differentiate between permutation and combination. Solve the recurrence relation \(a_n = 7a_{n-1} - 10a_{n-2}\) with initial conditions \(a_0 = 2\) and \(a_1 = 3\).

Describe pre-order, postorder and inorder traversal of a tree with an example.

Explain one-to-one and onto function with example. What is identity function?

How can you represent relations using matrices? Explain with suitable example.

Prove that \(\sqrt{2}\) is irrational number.

Solve the system of following congruences using Chinese Remainder theorem.

\(x \equiv 2 \pmod{3}\)

\(x \equiv 3 \pmod{5}\)

\(x \equiv 2 \pmod{7}\)

What is pigeonhole principle? Show that \(\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}\) where \(n\) and \(k\) are positive integers with \(n \geq k\).

What is permutation? What is the next permutation in lexicographic order after 362541?

Explain incidence matrix representation of a graph with example.

Define tree traversal. Explain pre-order traversal with example.