### Exam Year

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 A5×10 , B10×15 , C15×20 , D20×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) + kn2, 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.