Semester
Subject
Year
Bachelors In Information Technology
Institute of Science and Technology, TU
Discrete Structure (BIT152)
Year Asked: 2078, syllabus wise question
Counting and Discrete Probability
1.
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]
2.
Explain product rule. How many strings are there of four lowercase letters that have the letter x in them? [5]
Induction and Recursion
1.
Use mathematical induction to show that the sum of first n positive integers is n(n+1)/2. [5]
Logic and Proof Methods
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 tautology? Show is a tautology. [5]
Number Theory
1.
What is congruent modulo? Determine whether 20 is congruent to 8 modulo 6 and 25 is congruent to 17 modulo 5. [5]
2.
Explain trial division with example? Using trial division, show that 101 is prime. [5]
Sets, Relations and Functions
1.
Define cartesian product. Find A3 for the set A = (a, b, c). [5]
2.
How can you represent relations using matrices? Suppose that and . Let be the relation from to containing if , , and . What matrix representing if , , , and and ? [5]
Tree and Graphs
1.
Define spanning tree and minimum spanning tree with suitable example. Use Kruskal's algorithms to find minimum spanning tree in the given graph 
[10]
2.
What is graph? Explain simple graph and pseudograph with example. [5]
3.
What is Euler path? Compare it with Hamilton path. [5]