Design and Analysis of Algorithms

Last Updated: Spring 2025

Offered during Fall and Spring Semesters each year.

1. Credits: 3 credit hours
2. Textbook, title, author, and year: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms (fourth edition), The MIT Press, 2022
3. Other supplemental materials: None

Course Information

1. Brief description of the content of the course: A study of algorithm design and analysis techniques, network flows, linear programming, randomized algorithms, NP-completeness, approximation algorithms, and mixed-parameter algorithms.
2. Prerequisites or co-requisites: COM S 3110 or equivalent; a strong background in programming, data structures, discrete mathematics, and elementary probability theory is also essential

Course Outcomes

1. Ability to formulate and define problems. 
2. Ability to design algorithms using standard techniques. 
3. Ability to implement algorithms in a programming language. 
4. Ability to determine the running time of an algorithm. 
5. Ability to solve combinatorial optimization problems. 
6. Ability to prove that some problems are NP-complete. 
7. Ability to design approximation algorithms using common techniques.

Topics

1. Running Time Analysis
2. Algorithm Design Techniques
3. Combinatorial Optimization
4. Polynomial Time Reduction
5. NP-Completeness
6. Approximation Algorithms