CSIT-403 – Analysis & Design of Algorithm (ADA)

Explain algorithm design technique? How do you measure the algorithm running time?

Give the divide and conquer solution for binary search and analyze the time complexity for it.

Explain the quick sort algorithm, simulate it with the following data 20, 35, 10, 16, 54, 21, 25.

Write an algorithm for traveling salesperson problem using check bounds.

Discuss the operations performed on the binary search tree for the following data : 20, 49, 41, 93, 69, 90, 76, 62, 81, 75, 10, 79, 87, 38 and delete 41 and 76.

Differentiate between BFS and DFS.

Solve the following 0/1 Knapsack problem using dynamic programming P= (11, 21, 31, 33), W= (2, 12, 23, 15), C= 42, n= 4.

$P = (11, 21, 31, 33), W = (2, 12, 23, 15), C = 42, n = 4$

Design a three stage reliability system with device types $d_1, d_2$ and $d_3$. The costs are $30,$15 and $20 respectively. The cost of the system is to be no more than$105. The reliability of each device is 0.9, 0.8 and 0.5 respectively.

$d_1, d_2, d_3$

On which type of problem we apply multi stage graph technique? Explain with example.

Briefly explain 8-queen problem using backtracking with algorithm.

Identify the Hamiltonian cycle from the following graph. alt=''

Compute the optimal solution for job sequencing with deadlines using greedy method. N = 4, profits $(P_1, P_2, P_3, P_4)$ = (100, 10, 15, 27), deadlines $(d_1, d_2, d_3, d_4)$ = (2, 1, 2, 1).

$N = 4, (P_1, P_2, P_3, P_4) = (100, 10, 15, 27), (d_1, d_2, d_3, d_4) = (2, 1, 2, 1)$

Consider the following instance of the knapsack problem and solve it using greedy method n= 7, m= 15. $(P_1, P_2, P_3, P_4, P_5, P_6, P_7)$ = (10, 5, 15, 7, 6, 18, 3) and $(W_1, W_2, W_3, W_4, W_5, W_6, W_7)$ = (2, 3, 5, 7, 1, 4, 1).

$n = 7, m = 15, (P_1, P_2, P_3, P_4, P_5, P_6, P_7) = (10, 5, 15, 7, 6, 18, 3), (W_1, W_2, W_3, W_4, W_5, W_6, W_7) = (2, 3, 5, 7, 1, 4, 1)$

Apply the Kruskal algorithm for the following graph and explain. alt=''

2-3 trees

Merge sort

Optimal merge patterns

Floyd Warshall algorithm