CSIT 2nd Semester
Discrete Structure Board Question Paper 2080

CSC 165-2080 ✡
Tribhuvan University
Institute of Science and Technology
2080
✡
Bachelor Level/First Year/Second Semester/Science
Computer Science Information Technology (CSC 165)
(Discrete Structure)
(New Course)
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 Answer Questions
Attempt any Two question.
[2x10=20]
1.

How can you use mathematical induction to prove statements? Use mathematical induction to show that the sum of first n positive integers is n(n+1)/2.

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?

3.

What is shortest path problem? Use Dijkstra�s shortest path algorithm to find the shortest path between the vertices a and z in the weighted graph given below.

weighted graph with vertices a b c d e z and edges with weights

Section B

Attempt any Eight questions

[8x5=40]
4.

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

5.

Define function. Let f1 and f2 be functions from R to R such that f1(x) = x� and f2(x) = x - x�. What are the functions f1 + f2 and f1 f2?

6.

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

7.

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

8.

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

9.

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

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.

11.

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

12.

Explain matrix representation of relations with example.