COL758: Advanced Algorithms


Course Information

Instructor: Keerti Choudhary

Lecture Timing: Tues, Fri 5:00-6:00 PM; Wed 12:00 - 1:00 PM.

TA: Kashish Jain (2021JCS2259)

Reference Books:

  • Randomized Algorithms by Rajeev Motwani, Prabhakar Raghavan
  • Approximation Algorithms by Vijay Vazirani
  • Understanding and Using Linear Programming by Jiří Matoušek, Bernd Gärtner
  • The design of competitive online algorithms via a primal-dual approach by Niv Buchbinder, Joseph (Seffi) Naor

Logistics

Evaluation: The course evaluation policy is:

  • Assignments - 20%
  • Exams - 30% + 35%
  • Project - 10%
  • Attendance - 5%

Acadmic Honesty: Cheating or allowing anyone to copy in exams/assignments would lead to strict disciplinary action.

Course Content


Lec. No. Topic Further reading + Links
01 Introduction (Randomized Algorithms, Geometric Algorithms)
02 Introduction (LP based Algorithms, Online Algorithms)
03 Random variable, Linearity of Expectation, Balls Bin Problem, Smallest Enclosing Circle Emo Welzl's Paper
04 Randomized Quick Sort (Expected Time Complexity)
05 Randomized Quick Sort (High Probability Bound)
06 Markov’s Inequality, Chernoff bound Chap 3.2, 4.1 of Randomized Algorithms
07 Median Estimation, Estimating Set Size
08 Estimating Set Size (contd..), Approximate Transitive closure Edith Cohen's paper, Ilya's article
09 Approximate Transitive closure (contd..), Boolean Product Witness Matrix
10 Boolean Product Witness Matrix (contd..) Chap 10.1 of Randomized Algorithms
11 Thorup and Zwick’s Distance Oracle
12 Convex Hull Problem Chap 9.2 of Randomized Algorithms
13 Convex Hull Problem (contd..)
14 Minimum pairwise distance
15 Karger’s Min Cut Algorithm Sanjeev Arora's notes
16 Karger and Stein’s Min Cut Algorithm Chap 10.2 of Randomized Algorithms
17 Probabilistic Method: Bounding the number of Global Min-Cuts
18 Minor Exam Discussion
19 Linear Programs (LPs), Geometric Interpretation
20 Farka’s Lemma, Fourier-Motzkin elimination, Approximate Optimality using Feasibility Ryan O’Donnell's notes (I)
21 Primal and Dual Linear Programs, Bipartite Perfect Matching Ryan O’Donnell's notes (II)
22 Vertex Cover, LP Rounding, Set Cover (Randomized algorithm)
23 Set Cover (Greedy algorithm), Approximation analysis via Dual Fitting Luca Trevisan's notes
24 Set Cover (Greedy algorithm contd..), LP of Max-Flow Problem
25 (s,t)-Min-Cuts, Max-Flow Min-Cut Theorem Rajat Mittal's notes
26 Zero-sum Games, Mixed Strategy Nash Equilibrium
27 Computing Nash Equilibrium for Zero-sum Games using LP Chap 8.1 of Linear Programming
28 Online Matching
29 Online Matching (contd..) + Elevator Problem
30 Ski-Rental Problem Chap 3 of Online Algorithms
31 Ski-Rental: Maintaining Feasible solutions to Primal-Dual in online manner
32 Randomized Algorithm for Ski-Rental Problem
33 Online Ad-allocation using Primal-Dual Chap 10.1 of Online Algorithms
34 Load Balancing
35 Load Balancing (contd..) Chap 8 of Online Algorithms
36 Online Matching: (1-1/e) competitive ratio