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