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 Prerequisites
The students are required to have familiarity with the following data structures.
- Arrays and linked lists
- Stacks and queues
- Graphs and trees, binary search trees, height balancing
- Heaps and priority queues
Tests
- Class Test 1: September 08, 2009 [Questions] [Solutions]
- Mid-Semester Test: September 20, 2009 [Questions] [Solutions]
- End-Semester Test: November 24, 2009 [Questions] [Solutions]
References
[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.