Design and Analysis of Algorithm

Unit I

Introduction: Algorithms, Analyzing Algorithms, Complexity of Algorithms, Growth of Functions, Performance Measurements, Sorting and Order Statistics — Shell Sort, Quick Sort, Merge Sort, Heap Sort, Comparison of Sorting Algorithms, Sorting in Linear Time.

Unit II

Advanced Data Structures: Red-Black Trees, B-Trees, Binomial Heaps, Fibonacci Heaps, Tries, Skip List.

Unit III

Divide and Conquer & Greedy Methods: Divide and Conquer with examples — Sorting, Matrix Multiplication, Convex Hull, Searching. Greedy Methods with examples — Optimal Reliability Allocation, Knapsack, Minimum Spanning Trees (Prim's and Kruskal's Algorithms), Single Source Shortest Paths (Dijkstra's and Bellman-Ford Algorithms).

Unit IV

Dynamic Programming & Backtracking: Dynamic Programming with examples — Knapsack, All Pair Shortest Paths (Warshall's and Floyd's Algorithms), Resource Allocation Problem. Backtracking, Branch and Bound with examples — Travelling Salesman Problem, Graph Coloring, n-Queen Problem, Hamiltonian Cycles, Sum of Subsets.

Unit V

Selected Topics: Algebraic Computation, Fast Fourier Transform, String Matching, Theory of NP-Completeness, Approximation Algorithms and Randomized Algorithms.