Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

Indian Institute of Technology, Kharagpur

Selected Topics in Algorithms

Indian Institute of Technology, Kharagpur and NPTEL via Swayam

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
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

Reviews

Start your review of Selected Topics in Algorithms

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.