BITM 2nd Semester
Discrete Structure Board Question Paper 2022

TRIBHUVAN UNIVERSITY
FACULTY OF MANAGEMENT
Office of the Dean
April 2022
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. List any two examples of propositions.
b. State Absorption law.
c. Represent "not all politicians are bad" using quantifier.
d. Mention the two ways to represent relation.
e. Define ceiling function. For what values of x, ceiling(x) = -1.
f. Define complete bipartite graph with example.
g. Define pairwise relative prime with example.
h. In how many ways letters of word DISCRETE can be arranged without repetition of characters?
i. Differentiate between Euler path and Hamilton path.
j. State Pigeon hole principle.

Section "B"

Descriptive Answer Questions:

[9 × 4 = 36]
2.

Define proposition and predicate. Find the inverse and converse of the following implications.
a. if you send me an email message then I will finish writing the program.
b. if Aldo is Italian then Bob is not English.

3.

What is recurrence relation? Find the first 5 terms of recurrence relation aₙ = 2aₙ₋₁ + 3aₙ₋₂ where a₀ = 1 and a₁ = 3.

4.

Let (a, b) ∈ R over a set of positive integers such that |a - b| is even. Show that R is equivalence relation.

5.

What is sorting? Sort the following data using bubble sort 30, 20, 11, 45, 10.

6.

State Binomial theorem and binomial coefficients. Find the coefficient of x²y³ in the (x + y)⁵.

7.

Why do we need to know the growth of a function? Show that 3x² + 8x + 7 is big Oh of x².

8.

Define degree of a vertex. List the necessary invariants for isomorphic graphs.

9.

Discuss adjacency matrix and incidence matrix representation of graph with suitable example.

10.

Using mathematical induction prove that n³ + 2n is divisible by 3?

Section "C"

Short Answer Questions:

[7 × 2 = 14]
11.

Using indirect proof, prove that if n² is odd then n is also odd.

12.

How many lowercase words are there of three characters, that can either start with "a" or end with "c".

13.

What is Pascal's triangle? Find the expansion of (2-x)⁶ using Pascal's triangle.

14.

Define expression tree with example.

15.

Show that (p ∧ q) →(p ∧q) is a tautology using truth table.

16.

State and verify handshaking theorem.

17.

Given a function f(x) = x² over a set of integers, find whether it is onto or one to one with reason.