StudyNp | BIT Second Semester – 2080.1 Question for Discrete Structure

Credit:

Nikesh Dhimal

Tribhuwan University

Institute of Science and Technology

2080.1

Bachelor Level / First Year / Second Semester / Science

Bachelors in Information Technology (BIT152)

(Discrete Structure)

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]

Define randomized algorithm with an example. Solve the recurrence relation

a_n = -4a_{n-1} - 4a_{n-2}

for

n \ge 2

, with initial condition

a_0 = 0

and

a_1 = 1

. [3+7]

What is Boolean matrix and list its operations? Prove that the sum of first

N

odd integers is

N^2

using mathematical induction. [4+6]

Differentiate between graph and tree. Describe about the necessary conditions for graphs to be isomorphic with an example. [2+8]

Section B

Short Answers Questions

Attempt any Eight questions.

[8*5=40]

List the negations of following statements: (a) He has passed the exam. (b) All dogs are loyal. (c) Some medicine has side effect. (d) If you study then you will pass the exam. (e) Open the door. [5]

How does Kruskal algorithm work? Illustrate with an example. [5]

State generalized Pigeonhole principle. How many ways can we get the 3 digit integers without repeating the digit? [5]

Using direct proof show that the sum of square of even number is even. [5]

Define equivalence relation. How do you represent relation? [5]

How do you solve computer arithmetic with large integers using Chinese remainder theorem? Give an example. [5]

10.

Write Dijkstra’s algorithm to find the shortest path from source node to goal node. [5]

11.

How do you plot graph for function

f(x) = x + 1

? Define ceiling, floor and exponential function. [5]

12.

List any five rules of inferences. [5]