Semester
Subject
Year
Tribhuwan University
Institute of Science and Technology
2076
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.
State pigeonhole principle. Solve the recurrence relation , with initial conditions . [10]
2.
Find the value of x such that x = 1 (mod 3), x = 1 (mod 4), x = 1 (mod 5) and x = 0 (mod 7) using Chinese remainder theorem. [10]
3.
Define Euler circuit with suitable example. Find the maximal flow s to t from the given network flow. 
[10]
Section B
Short Answers Questions
Attempt any Eight questions.
[8*5=40]
4.
Prove that for every positive integer is even integer using mathematical induction. [5]
5.
All over smart people are stupid. Children of stupid people are naughty. John is a children of Jane. Jane is over smart. Represent these statements in FOPL and prove that John is naughty. [5]
6.
Which of the following are possets? [5]
7.
Define reflexive closure and symmetric closure. Find the remainder when is divided by x + 2 using remainder theorem. [5]
8.
Define Euler path and Hamilton path. Give examples of both Euler and Hamilton path. [5]
9.
How many 3 digits numbers can be formed from the digits 1,2,3,4 and 5 assuming that:a. Repetitions of digits are allowed b. Repetitions of digits are not allowed [5]
10.
What is minimum spanning tree? Explain Kruskal's algorithm for finding minimum spanning tree. [5]
11.
List any two applications of graph coloring theorem. Prove that 'A tree with n vertices has n-1 edges'. [5]
12.
Define ceiling and floor function. Why do we need Inclusion - Exclusion principle? Make it clear with suitable example. [5]