CS60003 Algorithm Design and Analysis Autumn 2010, L-T-P: 4-0-0 
Schedule | Notices | Syllabus | Tests | References | 2009 | 2008 

Schedule

Instructor: Abhijit Das
Timing: Slot B (Monday 10:30-11:25, Tuesday 07:30-09:25, Thursday 11:30-12:25)
Venue: Room No 120, CSE Department
Teaching Assistants: Satrajit Ghosh and Pratyay Mukherjee.
Schedule | Notices | Syllabus | Tests | References | 2009 | 2008 

Notices and announcements

July 19, 2010
The first class will be on July 22, 2010 (Thursday).
July 07, 2010
All registrants for this course are required to have familiarity with the following data structures. If you do not have the requisite background and still you have to register for this course (for example, because this is a core for you), please consult any standard textbook on Data Structures (and Algorithms).
  • Arrays and linked lists
  • Stacks and queues
  • Graphs and trees, binary search trees, height balancing
  • Heaps and priority queues
July 07, 2010
UG students (from CSE) having completed two Algorithms courses will not be allowed to register for this course. Indeed, the coverage of this course is a strict subset of the coverages of our BTech cores Algorithms I and Algorithms II.
Schedule | Notices | Syllabus | Tests | References | 2009 | 2008 

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   7 hours
5. Algorithms on graphs   Traversal, topological sort, minimum spanning trees, shortest path, network flow   7 hours
6. Arithmetic algorithms   GCD, modular arithmetic, primality testing   0 hours
7. NP-completeness   Classes P and NP, reduction, NP-completeness, examples of NP-complete problems   8 hours
8. Approximation algorithms   PTAS and FPTAS, examples   6 hours
9. Randomized algorithms   Monte Carlo and Las Vegas algorithms, examples   4 hours
Schedule | Notices | Syllabus | Tests | References | 2009 | 2008 

Tests

Schedule | Notices | Syllabus | Tests | References | 2009 | 2008 

References

[1]     Thomas H Cormen, Charles E Lieserson, Ronald L Rivest and Clifford Stein, Introduction to Algorithms, Second Edition, MIT Press/McGraw-Hill, 2001.
[2]     Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005.
[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.
Schedule | Notices | Syllabus | Tests | References | 2009 | 2008