Design and Analysis of Algorithms
This course introduces basic elements of the design and analysis of computer algorithms. Topics include asymptotic notations and analysis, divide and conquer strategy, greedy methods, dynamic programming, basic graph algorithms, NP-completeness, and approximation algorithms. For each topic, beside in-depth coverage, one or more representative problems and their algorithms shall be discussed.
Tribhuvan University
Institute of Science and Technology
2081
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.
Section A
Attempt any TWO questions.
Differentiate between dynamic programming and memorization. Compute the shortest path between every pairs in the following graphs using Floyd Warshal algorithm.
What is the worst case of quick sort and how does randomize quick sort handle this problem? Sort the data { -2, 4, -3, 6, 12, 10, 11, 13, 9 } using quick sort.
Does greedy algorithm guarantee optimal solution? Solve the Fractional knapsack problem to find maximum loot from given information.
| Item | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Value | 12 | 10 | 20 | 15 | 2 | 3 | 50 |
| Weight (kgs) | 2 | 1 | 3 | 2 | 12 | 10 | 1 |
Section B
Attempt any EIGHT questions.
Given a set A=(5,7,10,12,15,18,20}, find the subset that sum to 35 using backtracking.
Solve the following recurrence relations using master’s method.
(a)
\[
T(n) = 2T\left( \frac{n}{2} \right) + n^3, \quad n > 1
\]
\[
T(n) = 1, \quad n = 1
\]
(b)
\[
T(n) = 2T\left( \frac{n}{4} \right) + 1, \quad n > 1
\]
\[
T(n) = 1, \quad n = 1
\]
Write an algorithm to find the nth fibonacci number with its time and space complexity.
Define order statistics problem. Find the edit distance between “cat” and “car” using dynamic programming.
Discuss about recursion and backtracking. Analyze the complexity of Miller Rabin Randomized Primality test.
Solve the following linear equation using Chinese Remainder Theorem.
x = 1 MOD 3
x = 2 MOD 5
x = 0 MOD 7
Explain the approximation algorithm for vertex cover of a connected graph with an example.
State cooks theorem. Discuss about problem reducibility.
Write short notes on:
a) Big Oh, Big Omega, Big theta
b) Class P, Class NP and NP-Complete