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: Maxflow 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
NPcompleteness: Reduction amongst problems, classes NP, P, NPcomplete, 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  MaxCut, Derandomization using conditional expectation.
Textbooks

Thomas H. Cormen, Charles E. Leiserson, Ronald L Rivest, Clifford Stein. Introduction to Algorithms, Third Edition, PHI Learning, 2009. ISBN:9788120340077.

Jon Kleinberg and Eva Tardos. Algorithm Design, Pearson, 2015, ISBN:978933251864.

Sanjoy DasGupta, C. H. Papadimitriou, Umesh Vazirani. Algorithms, First Edition, Tata McGraw Hill, 2006. ISBN: 9780073523408.
References
 Dexter C Kozen. The Design and Analysis of Algorithms, Texts and Monographs in Computer Science, Springer, 1992. ISBN:0387976876.
Past Offerings
 Offered in JanMay, 2018 by Mathew Francis (ISI Chennai)
Course Metadata
Item  Details 

Course Title  Design and Analysis of Algorithms 
Course Code  CS4802 
Course Credits  3104 
Course Category  PME/PME* 
Approved on  Senate of IIT Palakkad 