Discrete Structure TU Board 2080 (new course) question paper

How can you use mathematical induction to prove statements? Use mathematical induction to show that sum of first n positive integer is
$$\frac{n(n+1)}{2}$$

Explain linear homogeneous recurrence relation with constant coefficients. What is the solution of the recurrence relation a_n = 6a_n-1 – 9a_n-2 with initial conditions a_0 = 1 and a_1 = 6?

What is shortest path problem? Use Dijkstra's shortest path algorithm to find the shorteszt path between vertices a and z in the weighted graph below:

[figure in the original paper]

Let us assume tha R be a relation on the set of ordered pair of positive integers such that ((a, b), (c, d)) ∈ R if and only if ad = bc. Is R an equivalence relation?

Define function. Let f_1 and f_2 be function from R to R such that f_1(x) = x^2 and f_2(x) = x – x^2 . What are the functions f_1 + f_2 and f_1 . f_2?

Explain fuzzy set with example. How do you find complement of a fuzzy set?

What is congurent modulo? Determine whether 37 is congurent to 3 modulo 7 and wheather -29 is congurent to 5 modulo 17.

Define network flow with example. What are saturated edge, unsaturated edge and slack value?

Give an example of tautology and contradiction. Show that implication and contrapositive are equivalence.

What is direct proof ? Give a direct proof that if m and n are both perfect squares, then mn is also a perfect square.

What is product rule? How many strings are there of four lowercase letters that have the letter x in them?

Explain the matrix representation of relations with example.