StudyNp | BIT Second Semester – 2082 Question for Discrete Structure

Tribhuwan University

Institute of Science and Technology

2082

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]

State division theory. Add two integers 13578 and 45730 using Chinese Remainder Theorem. [2+8]

Why do we need quantifiers? List any three rules of inferences. Prove that

\sqrt{2}

is irrational using prove by contradiction. [2+3+5]

List some advantages of randomized algorithm. Given any set of ten natural numbers between 1 and 99 inclusive, prove that there are two disjoint nonempty subsets of the set with equal sums of their elements. How do you generalize permutations and combinations? [2+4+4]

Section B

Short Answers Questions

Attempt any Eight questions.

[8*5=40]

Mention the necessary and sufficient conditions for Euler path and Euler circuit with example. [5]

How do you represent set? Explain. [5]

Using mathematical induction prove that sum of first N odd integers is

N^2

. [5]

Solve the recurrence relation

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

with initial conditions

a_0 = 0

and

a_1 = 1

. [5]

Find the shortest path from a to z in following graph using Dijkstra’s algorithm.

[5]

Define Boolean and exponential function. Discuss about partial ordering. [2+3]

10.

Prove the correctness of following recursive algorithm for computing

a^n

using induction.

\text{Power(a, n)}

\text{\{}

\text{if (n = 0) return 1;}

\text{else return a * Power(a, n-1);}

\text{\}}

[5]

11.

Define spanning and minimum spanning tree? How do you traverse tree? [2+3]

12.

What do you mean by connectivity in graph? Discuss about Bipartite and Planar graph. [1+4]