BIT 2nd Semester
Discrete Structure Board Question Paper 2078

Views: ...
BIT 152-2078 ✡
Tribhuvan University
Institute of Science and Technology
2078
✡
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.

Explain direct proof, indirect proof, and proof by contradiction. Use direct proof to show that "If n is an odd integer, then n³ is an odd integer". Also use indirect proof to show that "If n is an integer and n³ then n is odd".

2.

What is linear nonhomogeneous recurrence relation of degree k with constant coefficients? Find all the solutions of the recurrence relation aₙ₊₄a+n. Also find the solution of the relation with initial condition a₀ 1.

3.

Define spanning tree and minimum spanning tree with suitable example. Use Kruskal's algorithms to find minimum spanning tree in the given graph.

Section B

Attempt any Eight questions

[8x5=40]
4.

What is tautology? Show (p ∧ q)→(p ∨ q) is a tautology.

5.

Define cartesian product. Find A3 for the set A = (a, b, c).

6.

How can you represent relations using matrices? Suppose that A= {1, 2, 3} and B= {1, 2}. Let R be the relation from A to B containing (a, b) if a ∈A, b ∈B, and a > b. What matrix representing R if a1 = 1, a2 = 2, a3 = 3, and b1 = 1 and b2 = 2?

7.

Use mathematical induction to show that the sum of first n positive integers is n(n+1)/2.

8.

What is congruent modulo? Determine whether 20 is congruent to 8 modulo 6 and 25 is congruent to 17 modulo 5.

9.

Explain trial division with example? Using trial division, show that 101 is prime.

10.

Explain product rule. How many strings are there of four lowercase letters that have the letter x in them?

11.

What is graph? Explain simple graph and pseudograph with example.

12.

What is Euler path? Compare it with Hamilton path.