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.