CS60003 Algorithm Design and Analysis Autumn 2009, L-T-P: 4-0-0

Note for MS/PhD students

For MS/PhD students who are unable to obtain a C grade (or better), a supplementary test will be conducted. The date for this test is January 07, 2010. The syllabus will include the last three chapters (Graph algorithms, NP-Completeness, solving difficult problems). The test will be closed-book, closed-notes and of duration exactly three hours. Students are requested to meet me at 2:45PM (14:45 Hrs) at my office. We will use an empty classroom to conduct the test.

Instructor: Abhijit Das
Timing: Slot F (Wednesday 09:30-10:25, Thursday 08:30-09:25, Friday 10:30-12:25)
Venue: Room No 107, CSE Department
TA: Vivek Sharma
Previous years: Autumn 2008

Tentative lecture schedule

1. Introduction   Order notations, induction, floor and ceiling functions, pigeon-hole principle, recurrence relations   3 hours
2. Algorithm design techniques   Greedy algorithms, divide-and-conquer algorithms, dynamic programming, amortization, optimal algorithms   9 hours
3. Algorithms on arrays   Selection and median-finding, counting, radix and bucket sorts, string matching (Rabin-Karp and Knuth-Morris-Pratt algorithms)   6 hours
4. Geometric algorithms   Convex hulls, sweep paradigm, Voronoi diagrams   8 hours
5. Algorithms on graphs   Traversal, topological sort, minimum spanning trees, shortest path, network flow   5 hours
6. Arithmetic algorithms   GCD, modular arithmetic, primality testing   5 hours
7. NP-completeness   Classes P and NP, reduction, NP-completeness, examples of NP-complete problems   6 hours
8. Approximation algorithms   PTAS and FPTAS, examples   4 hours
9. Randomized algorithms   Monte Carlo and Las Vegas algorithms, examples   4 hours


The students are required to have familiarity with the following data structures.



[1]     Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005.
[2]     Thomas H Cormen, Charles E Lieserson, Ronald L Rivest and Clifford Stein, Introduction to Algorithms, Second Edition, MIT Press/McGraw-Hill, 2001.
[3]     Michael T Goodrich and Roberto Tamassia, Algorithm Design: Foundations, Analysis, and Internet Examples, Second Edition, Wiley, 2006.
[4]     Udi Manber, Algorithms -- A Creative Approach, Addison-Wesley, Reading, MA, 1989.
[5]     Mark de Berg, Mark van Kreveld, Mark Overmars and Otfried Shwarzkopf (Cheong), Computational Geometry: Algorithms and Applications, Third edition, Springer-Verlag, 2008.
[6]     Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
[7]     Vijay V Vazirani, Approximation Algorithms, Springer-Verlag, 2001.
[8]     Dorit S Hochbaum (editor), Approximation Algorithms for NP-Hard Problems, PWS Publishing Co, 1997.