Date | Item | Relevant link |
W Jan 20th | Introduction to the course and Approximation algorithms. - 2 approx. Minimum Makespan sched. | Sec 11.1 KT |
M Jan 25th | Approximation algorithms - MMS contd. (1.5 approx), k-center clustering | Sec 11.1, Sec 11.2 KT |
W Jan 27th | Approximation algorithms - k-center clustering contd. | Sec 11.2 KT |
M Feb 1st | Approximation algorithms - Set Cover | Sec 11.3 KT |
W Feb 3rd | Approximation algorithms - Pricing Method (Vertex Cover) | Sec 11.4 KT |
M Feb 8th | Approximation algorithms - Pricing method contd. (Disjoint paths) | Sec 11.5 KT |
W Feb 10th | Approximation algorithms - LP and rounding (Vertex cover again) | Sec 11.6 KT |
M Feb 15th | LECTURE CANCELLED - SNOW STORM | |
W Feb 17th | LECTURE CANCELLED - SNOW STORM | |
M Feb 22nd | LECTURE CANCELLED - CAMPUS WATER PROBLEM , HW1 | HW1 |
W Feb 24th | LP rounding : Generalized Load Balancing | Sec 11.7 KT |
M Mar 1st | LP rounding wrap up and Local Search | Sec 11.7 KT and Sec 12.1 KT |
W Mar 3rd | Local Search contd. and HW1 due | Sec 12.2 KT and Sec 12.3 KT |
M Mar 8th | No Lecture | |
W Mar 10th | Randomized algorithms | Sec 13.1 |
M Mar 15th | Randomized algorithms | Sec 13.2 |
W Mar 17th | Randomized algorithms | Sec 13.3 |
M Mar 22nd | Randomized algorithms and HW2 | Sec 13.4, 13.9, and HW2 |
W Mar 24th | Randomized algorithms | Sec 13.10 and Sec 13.11 |
M Mar 29th | Randomized algorithms | Sec 13.11 wrap up |
W Mar 31st | FPT | Sec 10.1 and Sec 10.2 |
M Apr 5th | FPT and HW2 due and HW3 | Sec 10.2 contd. and Sec 10.3, HW3 |
W Apr 7th | FPT | Sec 10.3 wrap up |
M Apr 12th | Lecture postponed | |
W Apr 14th | Lecture postponed | |
F Apr 16th | Special lecture cancelled HW3 due and HW4 | HW4 |
M Apr 19th | Tree decomposition | Sec 10.4 |
W Apr 21st | Tree decomposition contd. | Sec 10.4 wrap up |
M Apr 26th | Tree decomposition contd. | Sec 10.5 |
F Apr 30th | 10 - 11:30 AM: Student presentations, and HW4 due | |