BIT 2nd Semester
Discrete Structure Board Question Paper 2079

Views: ...
BIT 152-2079 ✡
Tribhuvan University
Institute of Science and Technology
2079
✡
Bachelor Level/First Year/Second Semester/Science
Bachelors in Information Technology (BIT 152)
(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 Answer Questions
Attempt any Two question.
[2x10=20]
1.

Give any four examples that are not propositions. Assume the premises, all oversmart persons are stupid, children of stupid persons are naughty, John is oversmart, Sam is children of John. Using rules of inferences, show that Sam is naughty.

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 3ⁿ-1 is multiple of 2 for n ≥ 1.

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.

Section B

Attempt any Eight questions

[8x5=40]
4.

Show that the sum of two even numbers is even using direct proof.

5.

Define power set. What is the power set of the set A= {1,2, 3, 4}?

6.

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

7.

Use mathematical induction to prove that the sum of the first n odd positive integers is n².

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

9.

What is arithmetic modulo m? Use the definition of addition and multiplication in Z₁₁ to find 7 + ₁₁9 and 7* ₁₁9.

10.

Define equivalence relation with an example.

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.

12.

Write the Dijkstra's algorithm to find the shortest path between two nodes in graph.