StudyNp | BIT Second Semester – 2081 Question | Discrete Structure (Syllabus Wise)

Bachelors Level/First Year/Second Semester/Science bit/second semester/discrete structure/syllabus wise questions

Bachelors In Information Technology

Institute of Science and Technology, TU

Discrete Structure (BIT152)

Year Asked: 2081, syllabus wise question

Counting and Discrete Probability

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

Induction and Recursion

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]

Prove that

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

is a perfect square using mathematical induction. [5]

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

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

Logic and Proof Methods

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]

Number Theory

Find the multiplicative inverse of 6 in

\mathbb{Z}_{25}

using Extended Euclidean Algorithm. [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]

Sets, Relations and Functions

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]

Tree and Graphs

Define graph isomorphism with an example. Using Kruskal's algorithm generate the Minimum Spanning Tree from following graph.

[5+5]

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

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