|CS60035/CS60086 Selected Topics in Algorithms||Autumn 2015, L-T-P: 3-0-0|
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.
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.