Tribhuvan University

Institute of Science and Technology


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.


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


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


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:

- Hamro CSIT

Group B

Attempt any EIGHT questions


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


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


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


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


Write short notes on:
a) Best, Worst and average case complexity

b) Greedy Strategy


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




Solve the following linear congrvences using Chinese Remainder Theorem.
X=l (MOD 2)
X=3 (MOD 5)
x=6 (MOD 7)


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

- Hamro CSIT


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.