BITM 2nd Semester
Discrete Structure Board Question Paper 2023

TRIBHUVAN UNIVERSITY
FACULTY OF MANAGEMENT
Office of the Dean
March - April 2023
Full Marks:60 Pass Marks:30 Time:3 hrs
BIM /
Second Semester /
MTH 202:
Discrete Structure

Candidates are required to give their answers in their own words as for as practicable.
The figures in the margin indicate full marks

Long Answer Questions
Section "A"

Brief Answer Questions:

[10 × 1 = 10]
1.

Brief Answer Questions:
a. Find the negation of the statement "Some persons are loyal".
b. Define cryptology.
c. How does Boolean matrix used to represent relation? Give example.
d. What is the value of⌈2.1⌉?
e. Find the order and size of complete graph K₁₅.
f. Define connected graph with example?
g. When is a directed graph said to be unilaterally connected?
h. State Pigeonhole principle.
i. List the steps used in mathematical induction.
j. Find the number of pendant vertices in a full binary tree with 15 vertices.

Section "B"

Descriptive Answer Questions:

[9 × 4 = 36]
2.

Translate the following into logical expression using quantifier and logical connectives.
a. All living things who can fly are birds.
b. Fish can swim.
c. All file system can be backed up.
d. Some children don't like math.

3.

What is the importance of big Oh and big Omega in algorithmic complexity analysis? Trace the insertion sort algorithm for the following data 12, 5, 7, 18, 10

4.

Define divisibility and relatively prime with example. Using divisibility rule Show that if a|b and a|c then a |(b+c)

5.

Define source vertex and sink vertex. How many different words can be generated from the word "ANIMAL" with or without meaning?

6.

Differentiate between domain and range. Determine whether the function f(x) = x² is onto, one-to-one, or one-to one correspondence.

7.

Discuss the adjacency matrix and incidence matrix representation of directed graph. How can we find the in degree and out degree of each vertices of directed graph from adjacency matrix?

8.

Define spanning tree. How many spanning tree are possible from wheel graph W₃? Find using Kirchhoff's theorem.

9.

Determine whether the following pair of graph is isomorphic or not.
graph isomorphic comparison image

10.

List the applications of tree. Prove that a tree with n vertices has n-1 edges.

Section "C"

Short Answer Questions:

[7 × 2 = 14]
11.

Prove that inverse and converse of an implication are logically equivalent, using truth table.

12.

Given a relation R = {(a, b): |a - b| is even} over a set of integers. Show that R is equivalent relation.

13.

Prove that (n+1 r) = (n r-1) + (n r)

14.

Find the first five terms of sequence defined by recurrence relation aₙ=2aₙ₋₁+3aₙ₋₂, a₀=3, a₁=-2.

15.

What is tree traversal? Construct an expression tree from a×b+(c /d×e-f) $g.

16.

State and verify handshaking theorem.

17.

Give an necessary and sufficient condition for a graph to have Eulerian Circuit.