At the time of the Midterm Exam, a student should be able to:

• Apply asymptotic time complexity analysis to choose amoung competing algorithms. In particular:
  • Determine the worst/best-case time complexity for a given algorithm.
  • Describe the limitations of big-oh notation.
  • Provide definitions for and describe the differences between big-oh, Omega, and Theta notation.
  • Be able to compare the time complexity of two alternate algorithms.
• Construct and solve recurrence equations describing the asymptotic time complexity of a given algorithm. In particular:
  • Use iteration to solve a given recurrence equation.
  • Use substitution to prove/disprove the solution to a recurrence via mathematical induction.
  • Regurgitate the Master Method.
  • Identify when application of the Master Method is appropriate and, when appropriate, apply the Master Method to solve a specified recurrence equation.
  • Apply mathematic techniques to simplify recurrence equations.
  • Make use of approximations to determine upper and lower asymptotic bounds.
• Implement sorting algorithms such as heapsort, mergesort, insertion sort, quicksort.
• Analyze modifications to sorting algorithms such as heapsort, mergesort, insertion sort, quicksort.
• Modify the sorting algorithms listed above so that they efficiently find the i^th order statistic.
• Define the defining characteristic of a stable sorting algorithm and determine whether or not a given sorting algorithm is stable.
• Develop algorithms to solve given problems within specified asymptotic time constraints.
• List at least three engineering applications of algorithmic design and analysis.

At the time of the Final Exam, a student should, in addition to the above, be able to:

• Understand and explain the purpose, time complexity, inner workings of the following graphing algorithms:
  • Depth First Search
  • Breadth First Search
  • Kruskal
  • Prim
  • Dijkstra
• Define and use graph theory terminology such as:
  • Directed/Undirected graphs
  • Cyclic/Acyclic graphs
  • Weighted/Unweighted edges
  • Adjacency list/Adjacency matrix graph representations
• Choose appropriate graphing algorithms in order to perform:
  • Topological Sort
  • Minimum Spanning Trees
  • Single-Source Shortest Paths
• Construct a greedy algorithm for a given problem
• Determine whether or not a greedy algorithm will provide an optimized solution
• List the key components of a dynamic programming algorithm
• Identify whether or not an algorithm makes use of dynamic programming
• Distinguish between the following sets of problems: P, NP, NP Hard, NP Complete
• Explain the role of polynomial reductions in NP Complete problems
• Develop simple polynomial reductions
• Explain the significance of proving that an NP Complete problem cannot be solved in polynomial time
• Explain the significance of finding a polynomial time solution to an NP Complete problem