An advanced in-depth study in the design and analysis of algorithms. Topics include models of computation, sorting, data structures, graph algorithms, matrix multiplication, fast Fourier transform, polynomial arithmetic, pattern matching, and NP-complete problems. Goal All students should develop the ability to read and understand research papers that include a significant analysis of algorithms component, and to do a rough analysis of the running times of most algorithms they will encounter. They will also gain familiarity with several algorithm design techniques. Projects and Assignments Homework assignments will be given most weeks.
All assignments are due at class the week following the week in which they are given.
There will be a penalty for late assignments. There will be a term paper for this course. Students will choose a recent research paper from a computer science conference or journal to read. The paper should have a significant algorithm design and analysis component. The students will write a paper explaining the paper they have read in a way that would be easy for another student in the class to understand.