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 $a_n = 3a_{n-1} - 3a_{n-2} + a_{n-3}$, with initial conditions $a_0 = 1, a_1 = 3, a_2 = 7$.[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 $n \geq 1, n^2 + n$ 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? $\text{a. } (Z, =)$ $\text{b. } (Z, \neq)$ $\text{c. } (Z, \leq)$ [5]
7.
Define reflexive closure and symmetric closure. Find the remainder when $4x^2 - x + 3$ 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]