Search Google Appliance

CS 584/684 Algorithm Design & Analysis

Credit Hours: 3
Course Coordinator:
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 course 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.
Major Topics:
Laboratory Exercises:


CAC Category Credits Core Advanced
Data Structures
Software Design
Computer Architecture
Programming Languages


Oral and Written Communications:  
Social and Ethical Issues:  
Theoretical Content:  
Problem Analysis:  
Solution Design: