Semester
Subject
Year
Tribhuwan University
Institute of Science and Technology
2080.1
Bachelor Level / First Year / Second Semester / Science
B.Sc in Computer Science and Information Technology (CSC165)
(Discrete Structures)
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.
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}$[10]
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$?[10]
3.
What is shortest path problem? Use Dijkstra's shortest path algorithm to find the shortest path between vertices a and z in the weighted graph below:
[10]
Section B
Short Answers Questions
Attempt any Eight questions.
[8*5=40]
4.
Let us assume that R be a relation on the set of ordered pair of positive integers such that $((a, b), (c, d)) \in R$ if and only if ad = bc. Is R an equivalence relation? [5]
5.
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$? [5]
6.
Explain fuzzy set with example. How do you find complement of a fuzzy set? [5]
7.
What is congruent modulo? Determine whether 37 is congruent to 3 modulo 7 and whether -29 is congruent to 5 modulo 17. [5]
8.
Define network flow with example. What are saturated edge, unsaturated edge and slack value? [5]
9.
Give an example of tautology and contradiction. Show that implication and contrapositive are equivalence. [5]
10.
What is direct proof? Give a direct proof that if m and n are both perfect squares, then mn is also a perfect square. [5]
11.
What is product rule? How many strings are there of four lowercase letters that have the letter x in them? [5]
12.
Explain the matrix representation of relations with example. [5]