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 an=7an−1−10an−2 with initial conditions a0 = 2 and a1 = 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 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 binomn+1k=binomnk−1+binomnk where n and k are positive integers with n≥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]