Tribhuvan University
Bachelor of Science in Computer Science and Information Technology
Semester 2 · TU Board 2080
Course Title: Discrete Structure (CSC165)
Full Marks: 60Pass Marks: 24Time: 3 hours
Candidates are required to give their answers in their own words as far as practicable. The figures in the margin indicate full marks.
Group A
Attempt any two questions.(2 × 10 = 20)
- 1.10
Explain strong induction in detail. What is recursively defined function? Use mathematical induction to prove 7^n+2 + 8^2^n+1 is divisible by 57.
- 2.10
State pigeonhole principle. Solve the recurrence relation a_n = 5a_n-1 – 6a_n-2 with initial conditions a_0 = 1 and a_1 = 3.
Answer comingAlso asked in 2081, 2078, 2076, 2075
- 3.10
State max flow min cut theorem. Find the value of maximal flow in the graph below:
[figure in the original paper]
Group B
Attempt any eight questions.(8 × 5 = 40)
- 4.5
Explain the principle of inclusion and exclusion. How many integers from 1 to 30 are multiples of 2 or 3?
- 5.5
Give the example of ceiling, floor and boolean function. How do you plot the graph of the function?
- 6.5
Using Chinese remainder theorem solve the following congruences.
x = 1 (MOD 3)
x = 3 (MOD 5)
x = 6 (MOD 7)
- 7.5
Find the multiplicative inverse of 4 in Z_11 using extended euclidean algorithm.
Answer comingAlso asked in 2082, 2081, 2079
- 8.5
Express the following sentences using quantifier.
a) Not all people are loyal.
b) Everybody loves somebody.
c) Someone has passed the exam.
d) Aquatic animals can't live without water.
e) Some subjects are not interesting.
- 9.5
What is proof by contradiction? Give a proof by contradiction to show that if 3n+2 is odd then n is odd.
- 10.5
State the necessary conditions for two graphs to be isomorphic. How many different words from "MANAGER" can be generated with or without meaning?
- 11.5
Define symmetric closure. What is the symmetric closure of the relation R = {(1,1), (1,2), (2,2), (2,3), (3,1), (3,2)} on the set A = {1,2,3}?
- 12.5
Represent following graph using adjacency matrix.
[figure in the original paper]
— The End —