Analysis Design of Algorithm (CS-402) - Important Questions

Apply Quick Sort step-by-step to sort the given array: 15, 31, 1, 9, 80, 12, 14, 7, 24. Show partitioning at each step and analyse its time complexity.

What are asymptotic notations? Explain the different asymptotic notations - Big-Oh, Big-Omega and Theta - used for algorithm complexity with suitable examples.

What is Merge Sort? Sort the following list of elements using Merge Sort: 22, 12, 30, 46, 28, 14, 8, 10, 56, 18, 3. Analyse its time complexity.

Give the divide and conquer algorithm for Binary Search and analyse its time complexity for best, average and worst cases.

Obtain a set of optimal Huffman codes for messages with relative frequencies (4, 5, 7, 8, 10, 12, 20). Draw the decode tree for this set of codes and write applications of Huffman coding.

Solve the job sequencing with deadlines problem using Greedy method for n=5 with profits (p1,p2,p3,p4,p5)=(5,20,10,15,1) and deadlines (d1,d2,d3,d4,d5)=(3,2,1,2,3). Find the optimal job sequence and maximum profit.

Explain Prim's algorithm for minimum spanning tree with an example. Construct a minimal spanning tree using Prim's algorithm and analyse its complexity.

Find the optimal solution to the 0/1 Knapsack instance using dynamic programming where n=4, m=40, (w1,w2,w3,w4)=(2,11,22,15) and (p1,p2,p3,p4)=(11,21,31,33).

Explain the Floyd-Warshall all-pairs shortest path algorithm with a suitable example. Write its pseudocode and analyse its time complexity.

Construct and solve a multistage graph for the given graph using forward approach. Find the minimum cost path from source to sink.

Write an algorithm for the 8-queens problem using backtracking. Explain how backtracking places queens so that no two queens attack each other.

Solve the given Travelling Salesman Problem cost-matrix instance using Branch and Bound method. Find the minimum cost tour.

Describe lower bound theory and its use in solving algebraic problems with suitable examples.

What do you mean by balance factor in AVL tree? Explain height-balanced AVL tree with a suitable example of insertion and balancing with rotations.

Compare / differentiate between BFS and DFS graph traversal techniques with algorithm steps, example and applications.

Explain the classes P, NP and NP-complete problems. What is NP-completeness? Explain with suitable examples.