StudyNp | BIT Second Semester – 2081 Question for Discrete Structure

Credit:

Eli Tamang

Tribhuwan University

Institute of Science and Technology

2081

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 graph isomorphism with an example. Using Kruskal's algorithm generate the Minimum Spanning Tree from following graph.

[5+5]

What are the uses of randomized algorithm? Find the solution to the recurrence relation

a_n = 6a_{n-1} - 11a_{n-2} + 6a_{n-3}

with the initial conditions

a_0 = 2

a_1 = 5

and

a_2 = 15

. [2+8]

Define Boolean function, exponential function and partial ordering. List the computer representations for following set over universal set

U = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}

: (a) Set that contains even number (b) Set that contains multiple of 5 (c) Set that contains number greater than 7 (d) Set that contains prime number. [6+4]

Section B

Short Answers Questions

Attempt any Eight questions.

[8*5=40]

Define proposition. Convert the following sentences to predicate: (a) Some kind hearted peoples do still exist. (b) Student who study hard and do the homework get good marks in exam. [5]

Prove that

1^3 + 2^3 + 3^3 + \cdots + n^3

is a perfect square using mathematical induction. [5]

Find the multiplicative inverse of 6 in

\mathbb{Z}_{25}

using Extended Euclidean Algorithm. [5]

State generalized Pigeonhole principle. How many ways can you draw four digits integers without repetition of the digit? [5]

Explain any two ways of representing the graph. [5]

Compute the value of

8 \text{ MOD } 8

-9 \text{ MOD } 4

7 \text{ MOD } 17

6 \text{ MOD } 7

and

-8 \text{ MOD } 3

. [5]

10.

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

11.

Define cut vertices and cut edges. How do you determine whether the graph has Euler path? [5]

12.

Explain about structural induction and recursive definitions with example. [5]