CS 412 - Applied Algorithms, Fall 2026
Image 1
Course Overview
Your employer is facing the challenge of an application that exhibits poor performance and occasionally returns incorrect results. These factors are plaguing your company’s image and reputation. You have been assigned the task of redesigning the solution so that it is more efficient and to resolve the correctness issues. Your boss also wants an explanation and presentation on the efficiency of your solution, and how it might scale if the size of the input were to double every 6 months. You wonder:
- Is it possible to make it go faster?
- What should I present to show that my solution is of high quality and will provide enough detail to allow others to provide constructive feedback?
Where would you begin? This course provides the foundation for addressing these questions.
CS 412 is a practical study of algorithms and their use in problem solving. The main learning objectives include:
- Analyze and develop recursive algorithms for solving computational problems.
- Interpret and explain proofs of correctness for algorithms.
- Design greedy algorithms and prove their correctness using exchange arguments.
- Apply and analyze fundamental graph algorithms, including algorithms for shortest paths,
- Minimum spanning trees, and network flows.
- Explain the distinction between P, NP, and NP-complete.
- Use polynomial-time reductions to prove that problems are NP-complete.
- Develop and analyze approximation algorithms for selected NP-complete problems.
- Work as part of a team to present algorithms and critique other groups’ presentations.
This course will explore both theoretical concepts (running time and proofs of correctness) and practical problem solving by constructing programs in Python.
