Design & Analysis of Algorithms (DAA) — Winter 2019

(1) Define algorithm. (2) Define growth rate function. (3) What do you mean by time efficiency? Explain. (4) What is significance of space efficiency? (5) Give example of algorithm which follows decrease-and-conquer approach. (6) Explain concept of local optimum. (7) Explain principal of optimality.

(1) Derive worst case and best case time analysis for sequential (linear) search technique. (2) Differentiate iterative and recursive approach.

Compare divide-and-conquer approach with greedy approach and dynamic approach. Also write difference among them.

Explain the basic idea behind divide-and-conquer approach. How can divide-and- conquer approach could be applicable for making search operation more efficient? Explain with suitable example.

Explain Big-Oh Notation, Theta Notation and Omega Notations in detail.

Explain multiplication algorithm which uses divide-and-conquer technique and it requires fewer single-digit multiplication operations.

Define minimum spanning tree. Explain how to use union-find data structure for finding minimum spanning tree using Krushkal’s algorithm.

Solve following fractional knapsack problem using greedy approach. The capacity of the knapsack (W) is 50, values of products are {60, 100, 120, 50} and weights of products in respective order are {10, 20, 30, 25}

Write and explain abstract method of greedy approach. Explain how to solve fractional Knapsack problem using greedy approach.

Show how to find minimum coin change problem using dynamic programming method, where amount to be pay is 8 Rs. and available coin denomination d = {1, 4, 6}

Explain chain matrix multiplication problem. Explain how to solve it using dynamic programming approach with suitable example.

Show how to find longest common subsequence for {B, A, C, D, B} and {B, D, C, B} using dynamic programming. Also explain its procedure in brief.

Discuss travelling salesman problem with suitable example.

Explain backtracking method. How can N-Queen problem solve with backtracking method?

Differentiate BFS and DFS algorithm with suitable example.

Discuss best case and worst case time analysis for bubble sort.

Demonstrate how quick sort algorithm rearrange following data into ascending data using first element as pivot number. {50, 10, 60, 30, 80, 20, 40, 90}