Course

Introduction– Asymptotic Notations- Monotonicity vs. Nonmonotonicity – Examples.Analysis of iterative programs, Analysis of recursive programs: Recurrence Relation:Substitution method, Recursion Tree Methods, Master Method. Sorting: Bubble – Insertion Sort- Selection Sort. Divide and Conquer: Quick Sort- Merge Sort- Bucket Sort-Lower Bounds- Heap Sort – Comparisons of Sorting. Greedy Algorithm: Fractional Knap-sack Problem- Task Scheduling Problem. Dynamic Programming: Matrix Multiplication Problem- 0/1 Knap-sack Problem. Branch and Bound – backtracking

Graph Algorithms: Graph Traversals (DFS, BFS with Analysis) – Shortest Path Algorithms (with Analysis) – Dijkstra – Bellman Ford- Floyd Warshall’s all Pair shortest path Algorithm-Minimum spanning Tree (with Analysis) – Kruskal– Prims – Applications of BFS and DFS. Network Flow algorithms

NP Problems: Definition: P-NP-NP Complete-NP Hard. Examples:P-NP.

1. CormenT.H ,Leiserson C.E, Rivest R.L and Stein C, “Introduction to Algorithms”, Third Edition, Prentice Hall of India, 2009.
2. Baase.S and Gelder A.V., “Computer Algorithms- Introduction to Design and Analysis”, Third edition, Pearson Education Asia, 2003.
3. Ellis Horowitz ,SartajSahni.S and Rajasekaran.S, “Fundamentals of Computer Algorithms”, Silicon Press, 2008.
4. Goodrich M.T and Tamassia.R, “Algorithm Design Foundations, Analysis, and Internet Examples”, Fourth Edition, John Wiley and Sons, 2002.
5. Dasgupta.S, Papadimitriou.C. andVazirani.U, “Algorithms”, Eighth edition, Tata McGraw-Hill, 2009.