CS60035/CS60086 Selected Topics in Algorithms |
Autumn 2015, L-T-P: 3-0-0 |

## Schedule

Instructor Abhijit Das Timing Slot F [WED (09:30–10:25), ~~THU (08:30–09:25)~~[Reserve], FRI (10:30–12:25)]Venue Room No CSE–120 Teaching Assistants Not yet decided ## Notices and Announcements

22-Jul-2015Currently, this course is listed in ERP as a 10-th semester elective. A request has been sent to add this as a seventh and ninth semester elective. 22-Jul-2015There will be no other class in this week. The reserve hour (Thurrsday) will be utilized in the next two weeks to compensate for the loss of the class on this Friday. ## Syllabus

The syllabus is divided in two broad topics.

Randomized Algorithms:Models of randomized computation, avoiding worst-case inputs, fingerprinting, success amplification, witnesses.Approximation Algorithms:Basic concepts of approximation, applications to set covers, job scheduling, graph theory, and bin packing, hardness of approximation.This course has no official prerequisites. This is however an advanced course in algorithms. It is implicitly expected that the registrants have already gone through the basic courses on algorithms. For analyzing randomized algorithms, an introductory knowledge in probability (random variables, expectation) will be needed. Students from CS, IT, EC, EE and MA are expected to have this background. Students from other deartments may find this course too difficult and/or too irrelevant.

## Books and References

For randomized algorithms, I will mostly follow the book:

Juraj Hromkovič,For approximation algorithms, I will mostly follow the book:Design and Analysis of Randomized Algorithms: Introduction to Design Paradigms, Springer-Verlag, 2005, ISBN: 978-3-5402-3949-9.David P. Williamson and David B. Shmoys,Some other references are:The Design of Approximation Algorithms, Cambridge University Press, 2011.

- Noga Alon and Joel H. Spencer, The Probabilistic Method, third edition, John Wiley & Sons, 2008.
- Michael Mitzenmacher and Eli Upfal,
Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, 2005.- Rajeev Motwwani and Prabhakar Raghavan,
Randomized Algorithms, Cambridge University Press, 1995.

- Dorit S. Hochbaum (editor),
Approximation Algorithms for NP-Hard Problems, PWS Publishing Company, 1997.- Vijay V. Vazirani,
Approximation Algorithms, Springer-Verlag, 2001.## Tests

- Mid-Semester Test: 21-Sep-2015 [Questions and solutions]
- End-Semester Test: 26-Nov-2015 [Questions and solutions]