Second Level Algorithms

ABOUT THE COURSE:This is a second level algorithms course. We will cover the following topics: amortized analysis, Fibonacci heap, network flow, computational geometry, NP-completeness, approximation algorithms, randomized algorithms, and parameterized algorithms.INTENDED AUDIENCE: PG studentsPREREQUISITES: A first level course on AlgorithmsINDUSTRY SUPPORT: Every software company including Google, Microsoft, IBM, etc.

Syllabus

Week 1: Amortized Complexity: aggregate method, accounting method, potential function method
Week 2:Fibonacci heaps.
Week 3:Max flow problem: Ford-Fulkerson method, Edmond-Karp algorithm, Dinic’s algorithm
Week 4:Max flow problem: Push relabel method,Applications of max flow: Hall’s Theorem
Week 5:Applications of max flow: Maximum bipartite matching, Konig’s Theorem.
Week 6:Edmond’s blossom algorithm for maximum matching
Week 7:Stable matching
Week 8:Order Statistics, String Matching
Week 9:Randomized algorithms: Karger's algorithm, Karger-Stein algorithm
Week 10:Lower bound on sorting, introduction to NP-completeness
Week 11:Np-completeness: reductions
Week 12:Approximation algorithms for 3SAT, Metric TSP