Design & Analysis of Algorithms (DAA) — Summer 2021

Do as directed. 1) Define Space complexity. 2) What do you mean by pruning? 3) Define amortized analysis. 4) What is the worst case time complexity of Binary Search? 5) What do you mean by feasible solution? 6) What are the basic steps involved for Divide and Conquer strategy of solving algorithms? 7) What do you understand by Residual Capacity in Network flow problems?

Write a short note on Asymptotic notations.

Write a note on algorithm used to multiply two big numbers using Divide and conquer strategy.

Write a short note on Binary Search algorithm. Compare and contrast the Recursive and the Iterative approach for solving Binary Search.

Give the difference between Greedy approach and Dynamic approach for solving algorithms. Also explain job Scheduling algorithm. Solve the following. Number of Jobs = 5. Deadlines ={2,1,3,2,1} and Profit ={60,100,20,40,20}.

Write a short not on Rod cutting problem. Explain it using proper example.

Write a note on Prims algorithm to find MST. Also give the difference between prims and kruskal’s algorithm.

07 1) Solve the following coin change problem Amount to be made = 9 and coins available {2,6,4,1,3}. Find the minimum number of coins required to make the given amount. 2) Write a note on Mcoloring problem.

Write a note on Knapsack algorithm using greedy strategy.

Discuss Longest common subsequence algorithm (LCS).

What is n – queens problem? Explain it giving the example of 4-queens problem. OR1

Write a note on 2-way merge sort algorithm.

Write a note on 16 puzzle problem. Explain it giving the example of 8 -puzzle.

Give the algorithm for bubble sort. Also explain how it can be made more efficient when the data which is given is already in sorted fashion.

Explain the concept of Sieve of Eratosthenes.

Write a note on P,NP,NP hard and NP complete algorithms. Explain how the algorithms are categorized in the above-mentioned categories.

Explain how the efficiency of Iterative algorithms can be improved?