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

CSC 165-2082 ✡
Tribhuvan University
Institute of Science and Technology
2082
✡
Bachelor Level/First Year/Second Semester/Science
Computer Science Information Technology (CSC 165)
(Discrete Structure)
(Old 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.

Define graph coloring. What are the types of graphs? Describe the techniques for representing graph.

2.

Why do we need fuzzy set? Describe the operations in fuzzy set. Define set, power set and sub set.

3.

What is discrete probability? Define Pascal�s triangle. Solve the recurrence relation a_n = 5a_{n-1} - 6a_{n-2} with a0 = 1 and a1 = 4.

Section B

Attempt any Eight questions

[8x5=40]
4.

State Pigeonhole principle. What are the properties of a relation?

5.

Describe the different operations on Boolean matrices with example.

6.

Describe what is meant by a valid argument in propositional logic and show that the argument �If the earth is flat, then you can sail off the edge of the earth,� �You cannot sail off the edge of the earth,� therefore, �The earth is not flat� is a valid argument.

7.

Prove that n3 + 2n is divisible by 3 for any positive integer n using mathematical induction.

8.

How Kruskal�s algorithm can be used to find MST? Illustrate with an example.

9.

Using indirect proof show that if n2 is odd then n is odd.

10.

Define recursively defined set. Find the GCD of 12 and 20 using Euclidean Algorithm.

11.

Define network flow, saturated edge, unsaturated edge and slack.

12.

What is sum and product rule? How many numbers are there between 99 and 1000, having at least one of their digits 7?