CS 381: Learning Outcomes
Students who
complete the course, will have demonstrated the ability to do the following:
1.
Perform basic algorithm analysis including:
Use big
O-notation formally to give asymptotic upper bounds on time and space
complexity of algorithms. Explain the use of big-Omega, big-Theta, and
little-o notations to describe the amount of work done by an algorithm. Use
recurrence relations to determine the time complexity of recursive algorithms.
Solve elementary recurrence relations, e.g., using some form of a Master
Theorem. Give examples that illustrate time-space trade-offs of algorithms.
2. Apply
and modify algorithmic strategies and approaches including:
Describe and
use major algorithmic techniques (brute-force, greedy, divide-and-conquer,
dynamic programming, and graph explorations). Use a greedy approach to
solve an appropriate problem and determine if the greedy rule chosen leads to
an optimal solution. Use a divide-and-conquer algorithm to solve an
appropriate problem. Use recursive backtracking to solve a problem such as
navigating a maze. Use dynamic programming to develop the recurrence relations
and to solve an appropriate problem. Determine appropriate algorithmic
approaches to apply to a given problem. Describe heuristic problem-solving
methods. Understand the mapping of real-world problems to algorithmic
solutions. Explain the major graph algorithms and their analysis and
employ graphs to model application problems. Evaluate and compare different
algorithms using worst-, average-, and best-case analysis. Demonstrate the
ability to evaluate algorithms, to select from a range of possible options, to
provide justification for that selection, and explain an implementation of the
algorithm in a particular context.
3.
Explain and apply foundational computational complexity concepts
including:
Define the
classes P and NP. Explain the significance of NP-completeness.
Provide examples of NP-complete problems. Explain the impact pf
NP-complete problems to different application domains. Explain the
difference between NP-complete and NP-hard. Prove that a problem is
NP-complete. Use reduction techniques between problems. Demonstrate the
use of approximation algorithms for NP-hard problems. Explain the Halting
problem and other undecidable problems.