Selected Topics in Algorithms
Offered By: Indian Institute of Technology, Kharagpur via Swayam
Course Description
Overview
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.
Syllabus
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
Taught by
Prof. Palash Dey
Tags
Related Courses
Linear and Discrete OptimizationÉcole Polytechnique Fédérale de Lausanne via Coursera Linear and Integer Programming
University of Colorado Boulder via Coursera Graph Partitioning and Expanders
Stanford University via NovoEd Discrete Inference and Learning in Artificial Vision
École Centrale Paris via Coursera Convex Optimization
Stanford University via edX