CS 584/684 Algorithm Design & Analysis

Credit Hours:

3

Course Coordinator:

Sayan Bandyapadhyay and Shravas Rao

Course Description:

An advanced in-depth study of 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.

Prerequisites:

CS 350 or equivalent.

Goals:

Upon the successful completion of this class, students will be able to:

1. Analyze most algorithms encountered in practice (at least roughly).
2. Find a good algorithm to solve a problem.
3. Use and understand asymptotic notation.
4. Follow a correctness proof for an algorithm.
5. Understand divide and conquer methods and dynamic programming.
6. Understand the concept of amortized analysis.
7. Describe the major sorting and searching algorithms and know their time complexity.
8. Describe the meaning of NP-completeness.
9. Know the process of proving a problem is NP-complete.
10. Understand the idea of NP-approximation.
11. Read papers describing algorithms in the computing literature.
12. Write a paper clearly explaining a complex algorithm, using proper style and citations.