Design and Analysis of Algorithms — Summer 2018

Explain why analysis of algorithm is important? Explain: Worst Case, Best Case & Average Case Complexity with suitable example.

Explain linear inequality and linear equations.

Explain how multiplication of large integers can be done efficiently by using divide and conquer method.

Write an algorithm for selection sort and show that the time complexity of this algorithm is quadratic.

Why amortized analysis is required? Explain any two method of amortized analysis with suitable example.

Write Quick sort algorithm and derive the worst case time complexity of quick sort algorithm.

Explain Knapsack problem using greedy method with example.

Explain LCS problem using dynamic programming with suitable example.

Design and explain Dijkstra’s shortest path algorithm

Explain Backtracking concept and apply the same on 8-queen problem.

Describe an assembly line scheduling problem and give dynamic programming algorithm to solve it.

What is Articulation Point? Explain how to find an Articulation Point of the graph with suitable example.

Explain Branch and Bound technique with suitable example.

Explain naive string matching algorithm with example.

Explain the concept of P, NP and NP-complete problem

Explain Breadth First Traversal Method for Graph with algorithm.

Explain Floyd’s algorithm for finding out shortest path with example.