CS60003 Algorithm Design and Analysis |
Autumn 2009, L-T-P: 4-0-0 |

Note for MS/PhD studentsFor MS/PhD students who are unable to obtain a C grade (or better), a

supplementary testwill be conducted. The date for this test isJanuary 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. IntroductionOrder notations, induction, floor and ceiling functions, pigeon-hole principle, recurrence relations 3 hours 2. Algorithm design techniquesGreedy algorithms, divide-and-conquer algorithms, dynamic programming, amortization, optimal algorithms 9 hours 3. Algorithms on arraysSelection and median-finding, counting, radix and bucket sorts, string matching (Rabin-Karp and Knuth-Morris-Pratt algorithms) 6 hours 4. Geometric algorithmsConvex hulls, sweep paradigm, Voronoi diagrams 8 hours 5. Algorithms on graphsTraversal, topological sort, minimum spanning trees, shortest path, network flow 5 hours 6. Arithmetic algorithmsGCD, modular arithmetic, primality testing 5 hours 7. NP-completenessClasses P and NP, reduction, NP-completeness, examples of NP-complete problems 6 hours 8. Approximation algorithmsPTAS and FPTAS, examples 4 hours 9. Randomized algorithmsMonte 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.