top of page
Modern Algorithm Design
Course Description: This is a second course in algorithms and a follow-up course of algorithm design and analysis (ADA). On one hand, in contrast to classical problems that solves one computational task, modern day algorithms also process huge amount of data that is often available in a restricted way. We will explore theoretical aspects of algorithms for big-data. On the other hand, we shall also dive deeper into the other recent advancements of algorithm designs for fundamental problems. These include optimization, and coping with computationally hard problems (NP-Completeness). This includes network flows and exposure to approximation algorithms, and fixed-parameter tractability.
Pre-Requisites: Algorithm Design and Analysis (crucial), Discrete Probability and Discrete Mathematics (desirable).
Evaluation policy: Midsem 25%, Endsem 30%, Homeworks 25%, Quiz 10%, and Lecture Scribe 10%. While solving the assignments, you are allowed to discuss or look up in the internet. But, mention the names of the classmates (or anybody) whom you have discussed with. Also, in case you have found the solution in the internet, then provide the link where you have found it out. Understand the solution and write in your own language. Otherwise, this will be considered as plagiarism.
Lecture scribe template: available here.
Text and Reference Books:
[MU] Probability and Computing: M. Mitzenmacher and E. Upfal.
[KT] Algorithm Design: J. Kleinberg and E. Tardos.
[MR] Randomized Algorithms: R. Motwani and P. Raghavan.
[AC] Data Streaming Lecture Notes: Amit Chakrabarti.
[GOd] Lecture Notes from CMU on Linear Programming: Anupam Gupta and Ryan Odonel.
Teaching Assistant: Suryendu Dalal.
Lecture Schedule: Tuesday and Thursday 11am-12:30 pm.
Module 1 - Algorithms for Big-Data and Optimization:
- Lecture 1 (30th August 2022): Introduction, Randomized Quick-Sort.
Section 2.5 from [MU]. Chapter 13 from [KT].
- Lecture 2 (1st September 2022): Randomized Algorithm for Min-Cut.
Section 1.5 from [MU]. Chapter 13 from [KT].
- Lecture 3 (6th September 2022): Probabilistic Method and Max-Cut.
Markov's Inequality, Chebyshev's Inequality and some applications.
Chapter 6 of [MU] for Max-Cut and Probabilistic Method.
Chapter 3 of [MU] for Markov and Chebyshev's Inequality.
- Lecture 4 (8th September 2022): Chernoff Bound and it's applications.
Coin toss (continued from previous lecture).
Chapter 13 from [KT], Chapter 4 and 5 from [MU].
See cheat sheet and Chapter 7 from here.
- Lecture 5 (13th September 2022): Derandomization of Max-Cut.
Pairwise independence.
See lecture from Eshan Chattopadhyay and Bobby Kleinberg.
- Lecture 6 (15th September 2022): Hashing I. Universal Class of Hash Functions.
Construction of pairwise independent random bits.
Balls and Bins model using 2-universal hashing and pairwise independent hashing.
Chapter 13.3 from [MU].
- Lecture 7 (20th September 2022): Hashing II.
Pairwise independent hashing construction.
Introduction to perfect hashing. Quadratic space hash table construction.
Chapter 13.3 from [MU].
- Lecture 8 (22nd September 2022): Hashing III.
Constructing a linear space hash table.
Streaming I - Introduction to Streaming - reservoir sampling.
Chapter 13.3.3 from [MU] and lecture from Avrim Blum for hashing.
See lecture from Chandra Chekuri for streaming and reservoir sampling.
- Lecture 9 (27th September 2022): Streaming I: Reservoir Sampling.
Sampling k-items without replacement. Analysis begins.
- Lecture 10 (29th September 2022): Streaming II: Reservoir Sampling.
Continued analysis for k-items without replacement.
See notes from Syamantak Das here.
- Lecture 11 (4th October 2022): Streaming III.
Counting Distinct Elements using Pairwise Independent Hashing.
See lecture from Chandra Chekuri.
See Chapter 2 from [AC].
- Lecture 12 (6th October 2022): Streaming IV.
Estimating F2 in a stream using 4-wise independent hashing.
See Lecture 3 and Lecture 4 from Chandra Chekuri.
Also see Lecture 2 for more information on frequency moments.
- Lecture 13 (11th October 2022): Network Flow I: Introduction.
Revisiting Ford-Fulkerson and Max-Flow Min-Cut.
Edmond Karp's Algorithm.
Read Chapter 7 from [KT] and Lec-1 by Tim Roughgarden.
- Lecture 14 (13th October 2022): Network Flow II.
Edmond Karp's Algorithm. Proof of Correctness.
See Lecture 2 by Tim Roughgarden.
Also see Lecture 19 by David Witmer.
- Lecture 15 (1st November 2022): Maximum Bipartite Matching.
Structure of maximum matching using M-augmenting Path.
See lecture note from MIT here and Cornell University here.
Module 2 - NP-Completeness and ways to deal-with it:
- Lecture 16 (3rd November 2022): NP-Completeness revisited.
Polynomial time reductions, decision problems, and NP-Completeness.
Chapter 15 from [KT].
- Lecture 17 (10th November 2022): Introduction to Linear Programming.
Concepts and structures of Linear Program (LP) and Integer Linear Program.
Structure of LP, hyperplane, Halfspace, Polyhedron, Extreme points etc.
See lecture notes from [GOd].
- Lecture 18 (12th November 2022): LP Duality with Examples.
See lecture notes by Tim Roughgarden here.
- Lecture 19 (15th November 2022): LP Duality - weak and strong duality.
Complementary Slackness Condition. See lecture notes by Tim Roughgarden here.
See lecture notes by Luca Trevisan and notes from Stanford University.
- Lecture 20 (17th November 2022): Approximation Algorithm I.
Introduction and LP rounding to get approximation algorithm.
Vertex Cover (2-factor) and Cluster Vertex Deletion Set (3-factor).
- Lecture 21 (22nd November 2022): Approximation Algorithm II.
Primal-Dual method for Feedback Vertex Set in Bipartite Tournament.
- Lecture 22 (24th November 2022): Approximation Algorithm III.
FVS on Bipartite Tournament using Primal Dual finish.
Introduction to Parameterized Complexity. FPT algorithm for Vertex Cover.
- Lecture 23 (29th November 2022): Parameterized Algorithms I.
Cluster Vertex Deletion using Bounded Search Trees.
Improved FPT Algorithm for Vertex Cover.
Introduction to Kernelization and Parameterized Preprocessing.
See Chapter 2 and Chapter 3 of CFKLMPPS (parameterized algorithms).
- Lecture 24 (1st December 2022): Parameterized Algorithms II.
Iterative Compression - the key framework and Feedback Vertex Set.
An O(5^k poly(n))-time algorithm for Feedback Vertex Set.
See the paper by Fomin et al. for more specific details.
See the Chapter 4 of PC-book.
- Lecture 25 (6th December 2022): Parameterized Algorithms III.
Revisiting the O(5^k poly(n))-time algorithm for Feedback Vertex Set.
Some other uses of iterative compression.
bottom of page