COM S 511
Offered during Fall and Spring Semesters each year.
- Credits: 3 credit hours
- Instructor's or course coordinator's name: Oliver Eulenstein
- Textbook, title, author, and year: Java for Everyone by Cay Horstmann, 2010
- Other supplemental materials: None
- 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.
- Prerequisites or co-requisites: COM S 311
- Express combinatorial problems as maximum flow/minimum cut problems, as linear programs, or as integer linear programs.
- Perform reductions to prove NP-completeness.
- Explain what NP-completeness means and does not mean.
- Devise algorithms that solve NP-complete problems on restricted classes of graphs.
- Use linear programming to obtain approximation algorithms for certain optimization problems.
- Basic concepts in combinatorial optimization including network flows, linear programming, and integer linear programming.
- Polynomial-time reductions among computational problems.
- Tractability, intractability, and the class NP.
- Identifying special tractable cases of NP-hard programs
- Approximation algorithms using linear programming, randomization, and specialized techniques.