The objective of the course is to help students learn basic algorithms and their rigorous analysis. The analysis will involve proofs of correctness and efficiency analysis of implementation using appropriate data structures. The course also will provide a detailed introduction to the different algorithm design paradigms for problems from various domains.
Preliminaries: Asymptotic notations, Efficiency of algorithms, Notions of time and space complexity. (3 lectures)
Design Paradigms: Greedy Strategy, Divide & Conquer and Dynamic Programming with applications in different problem domains like sorting, searching, string matching, scheduling and simulation. (15 lectures)
Graph Algorithms: Depth First Search, Breadth First Search, Minimum Spanning Tree algorithms, Shortest path algorithms, Network flow algorithms. (24 lectures)
- To acquire basic mathematical tools and techniques for algorithm design and analysis.
- To familiarize with basic data structures and develop the ability to choose the appropriate data structure for designing efficient algorithms.
- To develop the ability to analyze the running time and prove the correctness of algorithms.
- To be able to design efficient algorithms for computational problems using various algorithm design techniques taught in the course.
- Introduction to Algorithms (3rd Edition) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. PHI Learning, 2009. ISBN:978-81-203-4007-7.
- Algorithms by Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani. McGraw-Hill Education, 2006. ISBN: 978-0073523408.
- Algorithm Design by Jon Kleinberg and Eva Tardos. Pearson, 2015. ISBN:978-93-325- 1864.
- The Design and Analysis of Algorithms by Dexter C. Kozen, Springer, 1992. ISBN: 978-0- 387-97687-7.