Questions
Syllabus
Qns. By Syllabus

Semester

Subject

Year

Bachelors Level/First Year/Second Semester/Science bit/second semester/discrete structure/syllabus wise questions

Bachelors In Information Technology

Institute of Science and Technology, TU

Discrete Structure (BIT152)

Year Asked: 2082, syllabus wise question

Counting and Discrete Probability
1.
List some advantages of randomized algorithm. Given any set of ten natural numbers between 1 and 99 inclusive, prove that there are two disjoint nonempty subsets of the set with equal sums of their elements. How do you generalize permutations and combinations? [2+4+4]
Induction and Recursion
1.
Using mathematical induction prove that sum of first N odd integers is N2N^2. [5]
2.
Solve the recurrence relation an=an−1+an−2a_n = a_{n-1} + a_{n-2} with initial conditions a0=0a_0 = 0 and a1=1a_1 = 1. [5]
3.
Prove the correctness of following recursive algorithm for computing ana^n using induction.
Power(a, n)\text{Power(a, n)}
{\text{\{}
if (n = 0) return 1;\text{if (n = 0) return 1;}
else return a * Power(a, n-1);\text{else return a * Power(a, n-1);}
}\text{\}}
[5]
Logic and Proof Methods
1.
Why do we need quantifiers? List any three rules of inferences. Prove that 2\sqrt{2} is irrational using prove by contradiction. [2+3+5]
Number Theory
1.
State division theory. Add two integers 13578 and 45730 using Chinese Remainder Theorem. [2+8]
Sets, Relations and Functions
1.
How do you represent set? Explain. [5]
2.
Define Boolean and exponential function. Discuss about partial ordering. [2+3]
Tree and Graphs
1.
Mention the necessary and sufficient conditions for Euler path and Euler circuit with example. [5]
2.
Find the shortest path from a to z in following graph using Dijkstra’s algorithm.
question image
[5]
3.
Define spanning and minimum spanning tree? How do you traverse tree? [2+3]
4.
What do you mean by connectivity in graph? Discuss about Bipartite and Planar graph. [1+4]