Questions
Syllabus
Qns. By Syllabus

Semester

Subject

Year

Tribhuwan University

Institute of Science and Technology

2081

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.
List any four rules of inference. Using direct and indirect proof show that, for any real number xx, if x3−7x2+x−7=0x^3 - 7x^2 + x - 7 = 0, then x=7x = 7 [10]
2.
What are the necessary and sufficient conditions for graphs to have Euler path only and Euler circuit? Let RR be a relation defined on set of natural numbers NN, such that a,b∈N,aRb↔ab=2ka,b \in N, aRb \leftrightarrow ab = 2k, where k∈{0,1,2,...}k \in \{0,1,2,...\}. Show that RR is a partial ordering relation on NN [10]
3.
Determine whether the function f(x) = x-1 from set of integers to the set of integers is injective, surjective or bijective. Write the type of Fuzzy set operations with their definition. Give the floor and ceiling value of 1.2 and -1.2. [10]
Section B

Short Answers Questions

Attempt any Eight questions.
[8*5=40]
4.
Find the GCD of 12 and 16 using Extended Euclidean Algorithm. [5]
5.
Using mathematical induction show that 5+2+5+8+...+(3n−1)=n(3n+1)25 + 2 + 5 + 8 + ... + (3n-1) = \frac{n(3n+1)}{2} [5]
6.
State sum rule and product rule. If 26 integers are chosen from the set of consecutive integers {1,2,3,...,50}, prove that there are sure to be two numbers so that one is multiple of the other. [5]
7.
Discuss about meet and join operation between Boolean matrices. What are the values of 5 mod 75 and -5 mod 77? [5]
8.
Define chromatic number. How does Kruskal's algorithm find Minimum Spanning Tree? [5]
9.
Solve the recurrence relation an=an−1+2an−2a_n = a_{n-1} + 2a_{n-2} with initial conditions a0=2a_0 = 2 and a1=7a_1 = 7. [5]
10.
What is network flow? Give an example of saturated edge, unsaturated edge, and slack. [5]
11.
When do we use permutation rather than combination? How many 5-digit numbers can be generated using the digits 0 to 9, if each number starts with 98 and no digit appears more than once? [5]
12.
Define subset and power set. How do you prove correctness of recursive algorithm using Induction? Illustrate with an example. [5]