Questions
Syllabus
Qns. By Syllabus

Semester

Subject

Year

Tribhuwan University

Institute of Science and Technology

2079

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.
Give any four examples that are not propositions. Assume the premises, all over smart persons are stupid, children of stupid persons are naughty, John is over smart, Sam is children of John. Using rules of inferences, show that Sam is naughty. [10]
2.
Why do we need principle of inclusion and exclusion? How many ways can we express the four character words ending with a digit and beginning three are lowercase alphabets. Be sure that none of the character can be repeated. Using induction, show that 3n−13^n-1 is multiple of 2 for n ≥\geq 1. [5+5]
3.
State necessary and sufficient conditions for a graph to have Euler path and circuit. Find the GCD of 12 and 18 using Extended Euclidian Algorithm. [4+6]
Section B

Short Answers Questions

Attempt any Eight questions.
[8*5=40]
4.
Show that the sum of two even numbers is even using direct proof. [5]
5.
Define power set. What is the power set of the set A= {1,2, 3, 4}? [5]
6.
Explain one-to-one correspondence with example. What is identity function? [5]
7.
Use mathematical induction to prove that the sum of the first n odd positive integers is n2n^2. [5]
8.
What is recursively defined function? Suppose that f is defined recursively by f(0) = 3, f(n + 1) = 2f (n) +3. Find f(1), f(2), f(3), and f(4). [5]
9.
What is arithmetic modulo mm? Use the definition of addition and multiplication in Zm\mathbb{Z}_m to find 7+1197 +_{11} 9 and 7∗1197 *_{11} 9. [5]
10.
Define equivalence relation with an example. [5]
11.
What is generalized pigeonhole principle. If a class has 24 students, what is the maximum number of possible grading that must be done to ensure that there at least two students with the same grade. [5]
12.
Write the Dijkstra's algorithm to find the shortest path between two nodes in graph. [5]