Advanced Design and Analysis of Algorithms

Offered during Fall and Spring Semesters each year.

1. Credits: 3 credit hours
2. Instructor's or course coordinator's name: Oliver Eulenstein
3. Textbook, title, author, and year: Java for Everyone by Cay Horstmann, 2010
4. 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 311

Course Outcomes

1. Express combinatorial problems as maximum flow/minimum cut problems, as linear programs, or as integer linear programs.
2. Perform reductions to prove NP-completeness.
3. Explain what NP-completeness means and does not mean.
4. Devise algorithms that solve NP-complete problems on restricted classes of graphs.
5. Use linear programming to obtain approximation algorithms for certain optimization problems.

Topics

1. Basic concepts in combinatorial optimization including network flows, linear programming, and integer linear programming.
2. Polynomial-time reductions among computational problems.
3. Tractability, intractability, and the class NP.
4. Identifying special tractable cases of NP-hard programs
5. Approximation algorithms using linear programming, randomization, and specialized techniques.