Design and Analysis of Algorithm — Winter 2024

Describe class P, NP and NP-Complete problems.

Explain Asymptotic notation.

Explain Multiplying large integers problem and its solution using Divide and Conquer strategy.

Write characteristics of Best case, Average case and Worst case of algorithm.

State and explain Master’s method to solve recurrence equation.

Compare and analyze Insertion sort and Heap sort.

Compare and analyze Bucket sort and Radix sort.

Describe Activity selection problem and find solution for given details. Id A1 A2 A3 A4 A5 A6 A7 Start time 5 1 3 2 5 8 End time 8 2 4 5 7 9

Explain fractional knapsack problem and solution with example.

Write and Explain Krushkal’s algorithm with example. Show algorithmic steps in example.

Describe Job scheduling algorithm and find solution for given details. Number of jobs N = 4. Profits associated with Jobs : (P1, P2, P3, P4) = (80, 20, 13, 32). Deadlines associated with jobs (d1, d2, d3, d4) = (2, 1, 3, 2)

Explain Huffman code with example.

Write and Explain Prim’s algorithm with example. Show algorithmic steps in example.

State and describe principle of optimality.

Describe the naive string matching algorithm.

Explain All points shortest path using dynamic programming with example.

Differentiate Greedy strategy and Dynamic programming.

Describe the Rabin-Karp algorithm.

Explain Longest common subsequence with example.

State limitations of Divide and Conquer strategy.

Describe DFS algorithm with example.

Explain travelling salesman problem using branch and bound strategy with example.

Describe Topological sorting in graphs.

Explain BFS algorithm with example.

Explain Eight queens problem using backtracking strategy with example.