CS60001 Advances in Algorithms Autumn 2008, L-T-P: 4-0-0
Instructor: Abhijit Das, CSE Department
Timing: Slot U (Monday 14:30-16:25, Tuesday 13:30-15:25)
Venue: Room No 108, CSE Department
Syllabus: Official site

Lecture schedule

1. Introduction   Order notations, induction, floor and ceiling functions, pigeon-hole principle, recurrence relations   4 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)   7 hours
4. Geometric algorithms   Convex hulls, sweep paradigm, Voronoi diagrams   9 hours
5. Algorithms on graphs   Traversal, topological sort, minimum spanning trees, shortest path, network flow   6 hours
6. Arithmetic algorithms   GCD, modular arithmetic, primality testing   6 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   5 hours
9. Randomized algorithms   Monte Carlo and Las Vegas algorithms, examples   5 hours

Covered, not covered

Textbooks

[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]     Udi Manber, Algorithms -- A Creative Approach, Addison-Wesley, Reading, MA, 1989.
[4]     Mark de Berg, Mark van Kreveld, Mark Overmars and Otfried Shwarzkopf (Cheong), Computational Geometry: Algorithms and Applications, Third edition, Springer-Verlag, 2008.
[5]     Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
[6]     Vijay V Vazirani, Approximation Algorithms, Springer-Verlag, 2001.
[7]     Dorit S Hochbaum (editor), Approximation Algorithms for NP-Hard Problems, PWS Publishing Co, 1997.

Tests

Class test
Date: September 12, 2008 (Friday)
Time: 1830-1930
Venue: CSE 119 (MTech, MS, PhD), CSE 120 (BTech and Dual-degree)
Rules: Open-notes, open-CLRS, semi-open-time
Questions: PDF
Solutions: PDF

Mid-semester test
Date: September 26, 2008 (Friday)
Time: 0900-1100
Venue: CSE 119 (MTech, MS, PhD), CSE 120 (BTech and Dual-degree)
Rules: Open-notes, open-CLRS, semi-open-time
Questions: PDF
Solutions: PDF

End-semester test
Date: November 22, 2008 (Saturday)
Time: 1400-1700
Venue: CSE 119 (MTech, MS, PhD), CSE 120 (BTech and Dual-degree)
Rules: Open-notes, closed-book, semi-open-time
Questions: PDF
Solutions: PDF