Advanced Algorithms
AY 2024-25, Sem II
co-taught with Prof Manoj Gupta
A link to the materials from the second half of the course will be shared here shortly.
Mondays and Thursdays, 11.30AM, 11/206
Please register as usual through IMS. This course will have materials posted to this website, but assessments will be managed through Gradescope and announcements will be made over Google Classroom.
All assessments will be processed through Gradescope, and will use the enrolment code 3RVXNG. You will be able to add yourself as a student.
New users: If you don’t have a Gradescope account yet, go to the Gradescope website, click Sign Up in the upper right corner, select Student, and put in your entry code in the sign-up form. If the entry code doesn’t work, please email me for details on how to access the course.
Existing users: If you already have a Gradescope account, log into that account and navigate to your Account Dashboard by clicking the Gradescope logo in the top left, and click Add Course in the bottom right corner. Then enter your course code. you will be able to add yourself as a student.
For announcements, please enroll on Google Classroom via this link or via code qrquvxi.
The first part of the course accounts for 50% of your total marks in the course.
There will be 12 worksheets in this course, each associated with a lecture. Each worksheet will be released at 7PM on the day of the lecture (on Gradescope), and will be due within 24 hours, i.e, 7PM on the next day. Exceptions may be made for circumstances that are beyond your control, please email me if you need an extension.
Each worksheet is worth 5 marks. Your total marks from worksheets will be scaled to 40% of your total marks (note that this is not capping: for example, if you score 30/60
from the worksheets, your total marks will be 20/40
, and your final score from the worksheets will be 40/40
if and only if you earn a total of 60
points across all worksheets).
There will also be a mid-term exam worth 10 points. The format of the exam will be shared shortly.
Course Plan:
Lec # | Date | Topic | Slides | Lecture |
---|---|---|---|---|
1 | 6 Jan | Introduction to Approximation Algorithms Example: Load Balancing |
YT | |
2 | 9 Jan | Introduction to Linear Programming Example: Vertex Cover |
YT[1] | |
3 | 13 Jan | Adaptive rounding Example: Bin Packing |
Part 1 Part 2 |
|
NA | 16 Jan | Worksheet Discussion Remark: we spent most of this class concluding our discussion of adaptive rounding. |
||
4 | 20 Jan | Randomized Rounding Example: Set Cover |
YT | |
5 | 23 Jan | General Techniques Multiway Cut via Isolating Cuts |
NA | |
6 | 27 Jan | Randomized Rounding Multiway Cut |
(same) | NA |
NA | 30 Jan | Worksheet Discussion Remark: we spent most of this class concluding our discussion of multiway cut. |
||
7 | 3 Feb | Primal-Dual Approximation Vertex Cover |
NA | |
NA | 6 Feb | Remark: this class is canceled. | ||
8a | 10 Feb | Primal-Dual Approximation Steiner Forest |
YT | |
8b | 13 Feb | Primal-Dual Approximation Steiner Forest (contd) |
(same) | YT |
9 | 14 Feb | Note: this is an extra makeup class Primal-Dual Approximation Facility Location |
||
NA | 17 Feb | Worksheet Discussion | ||
10 | 20 Feb | Semi-Definite Programming Maximum Cut |
||
11 | 24 Feb | Semi-Definite Programming Maximum Cut (contd) |
||
12 | 27 Feb | Approximation Schemes Knapsack |
Sorry about choppy audio! ↩︎