CSIT 2nd Semester
Discrete Structure Board Question Paper 2082

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)
(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.

State inclusion � exclusion principle. For which number x is true that [x] = [x]? Let f and g be functions from {1, 2, 3, 4} to {a, b, c, d}, and from {a, b, c, d} to {1, 2, 3, 4}, respectively with f(1)=d, f(2)=c, f(3)=a, and f(4)=b, and g(a)=2, g(b)=1, g(c)=3 and g(d)=2.
a. If f and g one � to � one?
b. If f and g on � to?
c. Does either f or g have an inverse? If so find this inverse.

2.

How many ways are there to assign 24 students to five faculty advisors? Find the solution of the recurrence relation a_n = 3a_{n-1} � 3a_{n-2} + a_{n-3} if a_0=2, a_1 = 2 and a_2 = 4.

3.

Define an Euler circuit and Euler path in an undirected graph. Compute the maximal flow form following network flow.

undirected graph with capacities

Section B

Attempt any Eight questions

[8x5=40]
4.

Explain how the pigeonhole principle can be used to show that among any 11 integers, at least two must have the same last digit. Find a minimum spanning tree from following graph where the degree of each vertex in the spanning tree does not exceed 2.

graph with vertices a b c d e and weighted edges

5.

Find the solution to the system x = 1 (MOD 4), x = 2 (MOD 5) and x = 3 (MOD 7) using Chinese Remainder theorem.

6.

Suppose that on an island there are three types of people, knights, knaves, and normals. Knights always tell the truth, knaves always lie, and normals sometimes lie and sometimes tell the truth. Detectives questioned three inhabitants of the island�Amy, Brenda, and Claire�as part of the investigation of a crime. The detectives knew that one of the three committed the crime, but not which one. They also knew that the criminal was a knight, and that the other two were not. Additionally, the detectives recorded these statements: Amy: �I am innocent.� Brenda: �What Amy says is true.� Claire: �Brenda is not a normal.� After analyzing their information, the detectives positively identified the guilty party. Who was it?

7.

Use mathematical induction to prove that 1� + 2� + 3� + � + n� = (n�(n+1)�)/4.

8.

Suppose that R is the relation on the set of strings of English letters such that aRb if and only if L(a) = L(b), where L(x) is the length of the string x. Is R an equivalence relation?

9.

What is the negation of �This is a boring course�? Give a direct proof for the statement: �If n is even, then n + 4 is even.�

10.

Define well ordering property. Find the multiplicative inverse of 7 modulo 19 using Extended Euclidean Algorithm.

11.

What are the necessary conditions for graph to be isomorphic? List and illustrate with an example.

12.

Solve the recurrence relation an = an-1 + 2a_n-2 with a0 = 2 and a1 = 7.