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.