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

  1. 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.

  2. Jon Kleinberg and Eva Tardos. Algorithm Design, Pearson, 2015, ISBN:978-93-325-1864.

  3. Sanjoy DasGupta, C. H. Papadimitriou, Umesh Vazirani. Algorithms, First Edition, Tata McGraw Hill, 2006. ISBN: 978-0073523408.

References

  1. Dexter C Kozen. The Design and Analysis of Algorithms, Texts and Monographs in Computer Science, Springer, 1992. ISBN:0-387-97687-6.

Metadata

  • Proposing Faculty : Dr. Jasine Babu
  • Department / Centre : Computer Science and Engineering
  • Programme : B.Tech
  • Proposal Type: New course
  • Offerings