CSIT 2nd Semester
Discrete Structure Board Question Paper 2080 Old Course

Explain proof by contraposition and proof by contradiction. Show that if n is an integer and n� + 5 is odd, then n is even using a) a proof by contraposition, b) a proof by contradiction.

Define recurrence relation. Compare linear homogeneous recurrence relation with linear nonhomogeneous recurrence relation. What is the solution of the recurrence relation a? = -4a??1 � 4a??2 for n = 2, a0 = 0, a1 = 1?

Explain graph as models of flow of Commodities. How do you find maximal flow in the transport network? State max-flow min-cut theorem.

How can you represent sets using bit strings? Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. What bit strings represent the subset of all odd integers in U, the subset of all even integers in U, and the subset of integers not exceeding 5 in U?

Define floor and ceiling function. What do you mean by exponential function?

Define summation. What is the value of the double sum ?�??1 ?�??1(i + j)?

Find the Boolean product of A =

Define predicate. Compare existential quantifier with universal quantifier.

What is structural induction? Explain.

What is the probability that a positive integer selected at random from the set of positive integers not exceeding 100 is divisible by either 2 or 5?

Explain Hamilton path and circuit with suitable example.