| Course Outline | General Information | Study Material | Lectures (classwise) |
The course consists of 4 lecture hours per week.
The basic thrust of the course would be to study approximation algorithms and randomization techniques in computer science and discrete mathematics.
We will try to stick to the basic course outline as given in this page.
We would assume in this course that you have undergone the Data and File Structures, Design and Analysis of Algorithms and Discrete Structures courses and have some knowledge of elementary discrete probability.
| Taught by: Arjit Bishnu (ArB) |
Class Timings: | Tuesday 14:15-16:00, Friday 14:15-16:00 Room 718 or ACMU Seminar room Room |
| The necessary evil - marks, exam, etc.: | Mid-sem: 20, End-sem: 50, Internal evaluation: 30 |
| Books |
(B1) Algorithm Design J. Kleinberg and Eva Tardos Pearson Education (B2) Probability and Computing: Randomized Algorithms and Probabilistic Analysis Michael Mitzenmacher and Eli Upfal Cambridge (B3) Randomized Algorithms Rajeev Motwani and Prabhakar Raghavan Cambridge (B4) Computational Geometry: Algorithms and Applications Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars Springer Verlag (B5) Computational Geometry: An Introduction Through Randomized Algorithms Ketan Mulmuley Prentice Hall (B6) The Probabilistic Method Noga Alon, Joel H. Spencer 4th edition, Wiley (B7) Geometric Approximation Algorithms Sariel Har-Peled American Mathematical Society (B8) Probabilistic Methods for Algorithmic Discrete Mathematics M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, B. Reed (eds.) Springer (B9) Proofs from THE BOOK Martin Aigner, Günter M. Ziegler Springer, 3rd edition (B10) Markov Chains and Mixing Times David Asher Levin, Yuval Peres, and Elizabeth Lee Wilmer American Mathematical Society (AMS) A draft of the book can be found here. (B11) Lectures on Discrete Geometry Jiri Matousek Springer (B12) Geometric Discrepancy Jiri Matousek Springer (B13) Computational Complexity: A Modern Approach Sanjeev Arora and Boaz Barak Cambridge University Pressa (B14) Stochastic Processes Sheldon Ross Wiley Student Edition (B15) Approximation Algorithms Vijay V. Vazirani Springer (B16) The Design of Approximation Algorithms David P. Williamson and David B. Shmoys Cambridge University Press |
| Web Resources |
(W1) Lecture Notes by Sariel Har Peled
(W2) Lecture Notes by David Mount (W3) Chapter on Random Graphs (Hopcroft and Kannan's draft) (W4) Lecture notes by Tim Roughgarden (W5) Probabilistic Combinatorics by Thomas Rothvoss (W6) Richard Weber's course on Probability for first year mathematicians at Cambridge (W7) The course web-page on Markov Chains by Richard Weber is here. The notes on Markov Chains are here. (W8) The Probabilistic Method Lecture Notes by J. Matousek and J. Vondrak |
| LECTURE DATES | TOPICS | EXERCISE |
| Lecture 1 (07-01-25) |
Introduction to the course;
Polynomial reductions and NP-Complete problems --
Read the subsection on NP-Complete problems in (B1);
Introduction to approximation algorithms and a 2-factor approximation algorithm for vertex cover --
Read from (B15) and (B16) |
-- |
| Lecture 2 (10-01-25) |
Max-SAT and MAX-CUT and its approximation: an application of first moment method Read Section 1.1 in (B8); or (W4); or Section 13.4 in (B1)
Introduction to LP and duality --
Read from (B15) and (B16)
Bin Packing --
Read from (B16)
Inapproximability result for TSP
Read from (B15) |
|
| Lecture 3 (14-01-25) |
Approximation algorithm for metric TSP
Read from (B15) and (B16)
Approximation algorithm for minimum makespan scheduling
Read from (B15) |
|
| Lecture 4 (17-01-25) |
Approximation algorithm for k-center
Read from (B15) and (B16)
Introduction to strongly polynomial reduction and strongly NP-Complete problems
Read from (B15) and the paper of Garey Johnson |
|
| Lecture 5 (21-01-25) |
An FPTAS for Knapsack; strongly NP-Complete problems and FPTAS;
Read from (B15) |
|
| Lecture 6 (24-01-25) |
Linear Programming, ILP, Primal and dual LP, Max-flow and min-cut, primal and dual slackness conditions
Read from (B15) |
|
| Lecture 7 (28-01-25) |
Set Cover -- O(log n) greedy approximation, ILP relaxation, Primal and dual LP and a f-factor approximation
Read from (B16) |
|
| Lecture 8 (31-01-25) |
Randomized rounding in set cover; O(log n)-approximation for Set Cover
Read from (B16) |
|
| Lecture 9 (04-02-25) |
LP in fixed dimesnion; Minimum enclosing ball
Read from (B4) and (W2) |
|
| Lecture 10 (07-02-25) |
LP in fixed dimension; Minimum enclosing ball;
Read from (B4) and (W2) |
|
| Lecture 11 (11-02-25) |
Tail inequalities -- Markov, Chebyshev and Chernoff and their applications
Read from (B2) |
|
| Lecture 12 (14-02-25) |
Number of global mincuts; Load balancing, balls and bins
Read from (B1) |
|
| Lecture 13 (18-02-25) |
Packet routing in network
Read from (B1) |
|
| Lecture 14 (20-02-25) |
Trapezoidal decomposition -- RIC and expected analysis
Read from (W2) and (B4) |
|
| Lecture 15 (04-03-25) |
Trapezoidal decomposition -- High probability bounds for search
Read from (W2) and (B4) |
|
| Lecture 16 (07-03-25) |
Read from () and () |
|
| Lecture 17 (18-03-25) |
Probabilistic Methods: Erdős-Ko-Rado Theorem;
Read from (B6)
Crossing Lemma and its applications
Read from (B9) |
|
| Lecture 18 (21-03-25) |
Alteration in Probabilistic Methods: Independent Set, Existence of graphs with high girth and number of edges;
Existence of graphs with high chromatic number and girth;
Read from (B9) |
|
| Lecture 18 (21-03-25) |
Alteration in Probabilistic Methods: Independent Set, Existence of graphs with high girth and number of edges;
Existence of graphs with high chromatic number and girth;
Read from (B9) |
|
| Lecture 19 (24-03-25) |
Random graphs: degree distribution, phase transition and threshold behaviour: existence of triangles, phase transition, isolated vertices.
Random graphs: clique. |
|
| Lecture 20 and 21 (01-04-25) and (05-04-25) |
Martingales, Doob Martingales, Lipschitz condition and Azuma Hoeffding inequalities; applications |
- |
| Lecture 22 (-04-25) |
Derandomization using conditional expectation |
- |
| Lecture (-04-25) |
Range spaces and VC dimension: |
- |
| Lecture (-04-25) |
VC dimension and epsilon-nets: epsilon-net theorem |
- | Lecture (17-04-25) |
Lovasz Local Lemma and its applications: k-SAT, list coloring, asymmetric LLL
Read from (B2), (B6) or (W5) |
| Lecture 19 (02-04-24) |
Range spaces and VC dimension: |
- |
| Lecture 21 (09-04-24) |
VC dimension and epsilon-nets: epsilon-net theorem |
- |