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.