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-2015	Currently, 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-2015	There 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č, Design and Analysis of Randomized Algorithms: Introduction to Design Paradigms, Springer-Verlag, 2005, ISBN: 978-3-5402-3949-9.

For approximation algorithms, I will mostly follow the book:

David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011.

Some other references are:

• 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]