Tribhuvan University
Bachelor of Information Technology
Semester 2 · TU Board 2078
Course Title: Discrete Structure (BIT152)
Full Marks: 60Pass Marks: 24Time: 3 hours
Candidates are required to give their answers in their own words as far as practicable.
Group A
Attempt any Two questions.(2 × 10 = 20)
- 1.10
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.10
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.10
Define spanning tree and minimum spanning tree with suitable example. Use Kruskal's algorithms to find minimum spanning tree in the given graph.
Group B
Attempt any Eight questions(8 × 5 = 40)
- 4.5
What is tautology? Show (p ∧ q)→(p ∨ q) is a tautology.
- 5.5
Define cartesian product. Find A3 for the set A = (a, b, c).
- 6.5
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.5
Use mathematical induction to show that the sum of first n positive integers is n(n+1)/2.
Answer comingAlso asked in 2079
- 8.5
What is congruent modulo? Determine whether 20 is congruent to 8 modulo 6 and 25 is congruent to 17 modulo 5.
- 9.5
Explain trial division with example? Using trial division, show that 101 is prime.
- 10.5
Explain product rule. How many strings are there of four lowercase letters that have the letter x in them?
- 11.5
What is graph? Explain simple graph and pseudograph with example.
- 12.5
What is Euler path? Compare it with Hamilton path.
— The End —