Selected Topics in Algorithms

ABOUT THE COURSE: Every application area of computer science and engineering demands efficient design of algorithms. Indeed an efficient algorithm for a problem may take much less time even on a old computer than an inefficient algorithm for the same problem running on the fastest computer on the earth. In basic data structure and algorithm course, we learn elementary techniques like greedy algorithms, divide and conquer, dynamic programming, etc. In this course, we will learn more advanced algorithm design techniques.INTENDED AUDIENCE: Under-graduate and post-graduatesPREREQUISITES: Knowledge of basic algorithmsINDUSTRY SUPPORT: All software companies especially google,microsoft,etc.

Week 1: Network Flows, Ford-Fulkerson Algorithm, Edmond-Karp AlgorithmWeek 2:Max-Flow Min-Cut Theorem, Application of Network Flows, Edmond’s Matching AlgorithmWeek 3:Randomization as Algorithm Design Technique, Karger’s Min Cut Algorithm, Randomized Algorithm for 2-SATWeek 4:Polynomial Identity Testing, Schwartz-Zippel Lemma Application of PIT: Perfect Bipartite MatchingWeek 5:Elementary Concentration Inequalities: Markov, Chebyshev, Chernoff-HoeffdingWeek 6:Markov Chain, Random Walks, Monte Carlo Method, DNF CountingWeek 7:NP-CompletenessWeek 8:Approximation Algorithm: Vertex Cover, Set Cover, Travelling Salesman Problem APTAS for Bin PackingWeek 9:FPTAS for Knapsack, Linear Programming BasicsWeek 10:Designing Approximation Algorithms using Linear Programs: Rounding, Primal-Dual SchemaWeek 11:Parameterized Algorithms: Fixed Parameter Tractable Algorithms, Kernelization, Bounded SearchWeek 12:Iterative Compression, Color Coding