Schedule

Instructor		Abhijit Das
Timing		Slot F [WED (10:00–10:55), THU (09:00–10:00), FRI (11:00–11:55)]
Venue		Room No CSE–120
Teaching Assistants		Pritam Bhattacharya, Rajesh Basak

Syllabus

This course deals with solving computationally difficult problems. Three broad approaches will be covered.

• Deterministic Algorithms: Pseudo-polynomial-time algorithms, parameterized complexity, branch-and-bound, local search, relaxation to linear programming.
• Approximation Algorithms: Basic concepts of approximation, applications to set covers, job scheduling, graph theory, and bin packing, relaxation to linear programming, hardness of approximation.
• Randomized Algorithms: Models of randomized computation, design paradigms for randomized algorithms, derandomization.

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

I will mostly use the following book (Chapters 2–5):

Juraj Hromkovič, Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics, second edition, Springer-Verlag, 2004, ISBN: 978-3-540-44134-2.

Some other references are:

• Noga Alon and Joel H. Spencer, The Probabilistic Method, third edition, John Wiley & Sons, 2008.
• Juraj Hromkovič, Design and Analysis of Randomized Algorithms: Introduction to Design Paradigms, Springer-Verlag, 2005.
• 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.
• David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011.

Tests

• Class Test, 01–Sep–2016: Questions with solutions
• Quiz, 04–Nov–2016
• Mid-semester Test, 20–Sep–2016: Questions with solutions
• End-semester Test, 28–Nov–2016: Questions with solutions

---

Home  |  Autumn 2015