Tribhuvan University

Institute of Science and Technology

2079

Bachelor Level / fifth-semester / Science

Computer Science and Information Technology( CSC314 )

Design and Analysis of Algorithms

Full Marks: 60 + 20 + 20

Pass Marks: 24 + 8 + 8

Time: 3 Hours

Candidates are required to give their answers in their own words as far as practicable.

The figures in the margin indicate full marks.

**Group A**

**Attempt any TWO questions.**

1

Explain the divide and conquer strategy for problem solving. Describe the worst-case linear time selection algorithm and analyze its complexity.

2

Write the dynamic programming algorithm for matrix chain multiplication. Find the optimal parenthesization for the matrix chain product ABCD with size of each is given as A_{5×10 }, B_{10×15} , C_{15×20} , D_{20×30}

3

What do you mean by Backtracking? Explain the backtracking algorithm for solving 0-1

knapsack problem and find the solution for the problem given below:

**Group B**

**Attempt any EIGHT questions**

4

Explain the iterative algorithm to find the GCD of given two numbers and analyze its complexity.

5

Generate the prefix code for the string ” CYBER CRIME” using Huffman algorithm and find the total number of bits required.

6

Define tractable and intractable problem. Illustrate vertex cover problem with an example.

7

Find the edit distance between the string ” ARTIFICIAL” and “NATURAL” Using dynamic programming.

8

Write short notes on:

a) Best, Worst and average case complexity

b) Greedy Strategy

9

Solve the following recurrence relations using masters method

a. T(n) = 2T(n/4) + kn^{2}, n > 1

=1 , n=1

b. T(n) = 5T(n/4) + kn , n > 1

=1 , n=1

10

Solve the following linear congrvences using Chinese Remainder Theorem.

X=l (MOD 2)

X=3 (MOD 5)

x=6 (MOD 7)

11

Find the MST from following graph using Kruskal’s algorithm.

12

Trace the quick sort algorithm for sorting the array A[ ]={15,7,6,23, 18,34,25} and write it’s best and worst complexity.

HAMROCSIT.COM