CS60003 Algorithm Design and Analysis

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.

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

[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.