Learning Objectives
This is an intermediate level course on algorithm design techniques. The first part of this course course will provide a detailed introduction to different algorithm design paradigms . The middle part of this course is intended to make students familiar with some well known classical algorithms and their design strategies and efficiency analysis. The third part of this course will deal with computationally hard problems and tacking them using approximation algorithms.
Learning Outcomes
By the end of this course, students will be able to design efficient algorithms for moderately difficult computational problems, using various algorithm design techniques taught in the course. Students will be able to apply commonly used approximation techniques like randomization and LP rounding in computationally hard problems, yet simple to describe optimization problems.
Syllabus
Greedy Algorithms: Greedy choice, Example like Interval Scheduling, Fractional knapsack, and Huffman coding.
Dynamic Programming: Optimal Substructure and Overlapping sub problems, Examples like Weighted Interval Scheduling, Integral knapsack, Coin changing and Longest increasing subsequence.
Network Flow algorithms: Max-flow mincut theorem, Ford Fulkerson algorithms, Edmond’s shortest path heuristic, Dinitz algorithm, Bipartite Matching.
Matching: Weighted Bipartite Matching, Hungarian algorithm, Edmond’s algorithm for matching in general graphs.
String Matching: KMP algorithm, Boyer Moore algorithm
NP-completeness: Reduction amongst problems, classes NP, P, NP-complete, and polynomial time reductions
Approximation algorithms: Approximation factor, Vertex cover via maximum matching, greedy algorithm for set cover, Metric TSP, Hardness of approximation, LP rounding – set cover, vertex cover. Randomized approximation - Max-Cut, De-randomization using conditional expectation.
Textbooks
-
Thomas H. Cormen, Charles E. Leiserson, Ronald L Rivest, Clifford Stein. Introduction to Algorithms, Third Edition, PHI Learning, 2009. ISBN:978-81-203-4007-7.
-
Jon Kleinberg and Eva Tardos. Algorithm Design, Pearson, 2015, ISBN:978-93-325-1864.
-
Sanjoy DasGupta, C. H. Papadimitriou, Umesh Vazirani. Algorithms, First Edition, Tata McGraw Hill, 2006. ISBN: 978-0073523408.
References
- Dexter C Kozen. The Design and Analysis of Algorithms, Texts and Monographs in Computer Science, Springer, 1992. ISBN:0-387-97687-6.
Past Offerings
- Offered in Jan-May, 2018 by Mathew Francis (ISI Chennai)
Course Metadata
| Item | Details |
|---|---|
| Course Title | Design and Analysis of Algorithms |
| Course Code | CS4802 |
| Course Credits | 3-1-0-4 |
| Course Category | PME/PME* |
| Approved on | Senate of IIT Palakkad |