Design and Analysis of Algorithms TU Board 2081 question paper

Differentiate between dynamic programming and memorization. Compute the shortest path between every pairs in the following graphs using Floyd Warshal algorithm.

[figure in the original paper]

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

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,n>1$$
$$T(n)=1,n=1$$

(b)
$$T(n)=2T\left(\frac{n}{4}\right)+1,n>1$$
$$T(n)=1,n=1$$

Write an algorithm to find the n^th 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