Questions
Syllabus
Qns. By Syllabus

Semester

Subject

Year

Tribhuwan University

Institute of Science and Technology

2078

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 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'. [10]
2.
What is linear nonhomogeneous recurrence relation of degree k with constant coefficients? Find all the solutions of the recurrence relation a, 4a+n. Also find the solution of the relation with initial condition a, 1. [10]
3.
Define spanning tree and minimum spanning tree with suitable example. Use Kruskal's algorithms to find minimum spanning tree in the given graph
question image
[10]
Section B

Short Answers Questions

Attempt any Eight questions.
[8*5=40]
4.
What is tautology? Show (p∧q)→(p∨q)(p \land q) \rightarrow (p \lor q) is a tautology. [5]
5.
Define cartesian product. Find A3 for the set A = (a, b, c). [5]
6.
How can you represent relations using matrices? Suppose that A={1, 2, 3}A = \{1,\,2,\,3\} and B={1, 2}B = \{1,\,2\}. Let RR be the relation from AA to BB containing (a, b)(a,\,b) if a∈Aa \in A, b∈Bb \in B, and a>ba > b. What matrix representing RR if a1=1a_1 = 1, a2=2a_2 = 2, a3=3a_3 = 3, and b1=1b_1 = 1 and b2=2b_2 = 2? [5]
7.
Use mathematical induction to show that the sum of first n positive integers is n(n+1)/2. [5]
8.
What is congruent modulo? Determine whether 20 is congruent to 8 modulo 6 and 25 is congruent to 17 modulo 5. [5]
9.
Explain trial division with example? Using trial division, show that 101 is prime. [5]
10.
Explain product rule. How many strings are there of four lowercase letters that have the letter x in them? [5]
11.
What is graph? Explain simple graph and pseudograph with example. [5]
12.
What is Euler path? Compare it with Hamilton path. [5]