Questions
Syllabus
Qns. By Syllabus

Semester

Subject

Year

Tribhuwan University

Institute of Science and Technology

2080

Bachelor Level / First Year / Second Semester / Science

Bachelors in Information Technology (BIT152)

(Discrete Structure)

Full Marks: 60

Pass Marks: 24

Time: 3 Hours

Candidates are required to give their answers in their own words as for as practicable.

The figures in the margin indicate full marks.

Section A

Long Answers Questions

Attempt any TWO questions.
[2*10=20]
1.
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.[10]
2.
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.[5]
3.
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. [4+6]
Section B

Short Answers Questions

Attempt any Eight questions.
[8*5=40]
4.
Describe pre-order, postorder and inorder traversal of a tree with an example. [5]
5.
Explain one-to-one and onto function with example. What is identity function? [5]
6.
How can you represent relations using matrices? Explain with suitable example. [5]
7.
Prove that $\sqrt{2}$ is irrational number. [5]
8.
Solve the system of following congruences using Chinese Remainder theorem: x = 2 (mod 3), x = 3 (mod 5), x = 2 (mod 7) [5]
9.
What is the 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 \). [5]
10.
What is permutation? What is the next permutation in lexicographic order after 362541? [5]
11.
Explain incidence matrix representation of a graph with example. [5]
12.
Define tree traversal. Explain pre-order traversal with example. [5]