I plan to cover some advanced techniques in algorithm design. The course
will be divided into four modules - approximation algorithms, randomized
algorithms, streaming and online algorithms.
Students taking this course should have done one course on programming,
and one on design and analysis of algorithms.
I also expect familiarity with basic concepts in probability.
There is no single textbook for the course.
I will post references for each topic. Most of the references will be available
There will be two assignments, a mid-semester exam, an end-semester exam,
and an oral exam.
The weightage is 10%
for each assignment, 30% for midsem, 40% for endsem, and 10% for the oral exam.
Here are some practice problems based on the topics we covered so far.
You are encouraged to first try them on your own. If you can not solve, take
a hint from other students or from me. You can also look for online sources.
If you find one, mail it to me.
- Problem set 1: Problems 2.2, 2.3, 2.4 from WS, problems 3.4, 3.5, 3.7 from VV (Posted on Jan 13)
You are not supposed to discuss the assignments with anyone or refer to any
source on the internet. Students found copying assignments from each other
will get a fail grade. If you are stuck while solving the assignment, you
are welcome to discuss with me. I will be glad to give hints so that you can
proceed. Assignments submitted after the due date will not be accepted.
Assignment 1 (Due on Feb 17th):
Problems 2.2, 3.1, 3.9 from WS, Problems 3.4, 3.5 from VV
Assignment 2 (Due on April 21st) here
- Jan 3: Introduction, 2-approximation for vertex cover, 2-approximation for metric
TSP using minimum spanning trees (Ref: Sections 1.1 and 3.2 of VV)
- Jan 6: Christofides' 1.5-approximation algorithm for TSP, Scheduling on identical
parallel machines (Ref: Sections 2.4, 2.3 of WS)
- Jan 10: Scheduling on identical parallel machines continued: 2-approximation, LPT rule and 3/2-approximation, 4/3-approximation using LPT rule (Ref: Section
2.3 of WS, and this for 3/2 approximation)
- Jan 13: Introduction to randomized algorithms, Karger's min-cut algorithm (Ref:
- Jan 17: Karger's min-cut algorithm continued, Improving the running time
of Karger's min-cut (Ref: this), Introduction to online algorithms: Ski rental
- Jan 20: Randomized algorithms for weighted MAX-SAT: 1/2 approximation
and 0.618 approximation (Ref: Sections 5.1, 5.2, 5.3 of WS)
- Jan 24: Set cover greedy algorithm, Knapsack problem dynamic programming
algorithm (Ref: Section 2.1 of VV and Section 3.1 of WS)
- Jan 27: Knapsack problem FPTAS, Introduction to bin packing, hardness and
inapproximability, 2-approximation by first-fit (Ref: Sections 3.1 and 3.3 of WS)
- Feb 6: Bin packing: Better than 4/3 inapproximability result for online
algorithms, 4/3-approximation for first-fit decreasing (Ref: this)
- Feb 7: APTAS for Bin-packing (Ref: Section 3.3 of WS)
- Feb 10: APTAS for bin-packing continued, Introduction to LP, Weighted
vertex-cover by LP-rounding (Ref: this)
- Feb 13: Uncapacitated facility location: 6-approximation (Ref: this)
- Feb 14: Uncapacitated facility location continued
- Feb 17: LP duality, primal-dual algorithm for weighted vertex cover (Ref:
this, Section 11.4 of Kleinberg-Tardos)
- Feb 28: Feedback vertex set primal-dual algorithm (Ref: Section 7.2 of WS)
- Mar 3: Feedback vertex set primal-dual algorithm continued, Introduction
to Hopcroft-Karp algorithm
- Mar 7: Hopcroft-Karp algorithm (Ref: this)
- Mar 10: Hopcroft-Karp algorithm continued, Weighted bipartite matching (Ref: this)
- Mar 14: Weighted bipartite matching - Primal-dual algorithm, Bipartite
matching polytope (Ref: this)
- Mar 17: Non-bipartite matching: Edmond's blossom shrinking algorithm (Ref:
- Mar 21: (Lecture by Partha) Randomized parallel algorithm for bipartite matching
- Mar 24: Edmond's algorithm continued, Introduction to streaming algorithms:
Majority (Ref: Chapter 1 of this)
- Mar 28: Streaming algorithms: Misra-Gries algorithm (Ref: Same as previous lecture), a lower bound on Most-frequent element problem (Ref: this)
- Mar 31: Estimating the number of distinct elements (Ref: this)
- Apr 4: Streaming algorithms for graph problems: Connectedness, bipartiteness, distance estimate (Ref: Lecture 13 of this)
- Apr 7: Matchings in streaming model (Ref: Section 15.2 of this)
- Apr 11: Lovász Local Lemma: Constructive proof and applications to
hypergraph coloring and k-CNF SAT (Ref: this)
- Apr 18: Approximate counting: FPRAS for DNF counting (Ref: this)