Midterm Review

1. Pseudo code and machine models.
2. Loop Invariants:
   • To define.
   • To state a loop invariant for a piece of code.
   • To demonstrate the method by proving an invaraitn
3. Order Notation:
   • The relative order of simple functions:
     • e.g. O(1), O(log n), O(n), O(n^k), O(n log n), O(2ⁿ), O(n!).
   • To identify the order class of a function using Θ notation:
     • e.g. 5n³ - 10n^{^2} + 14, n log n - n, n!, n¹⁰⁰
   • To provide the c and n_O for the definition of O or Ω.
   • To provide an theta order for a sample piece of code:
     • e.g. Linear scan of an array for the maximum element, a function which returns the sum of the first and last elements in an array.
4. Sums:
   • The formula for the sum of integers 1+2+...+k
   • The formula for the infinite and finite geometric series.
   • The formula for the series p + 2 p² + 3p³+ ..., for |p|<1.
5. Sorts: Insertion, Selection, Merge, Heap and Quick.
   • Example on small data set.
   • Run times, and notable runtime various (e.g.: Insertion sort linear on special inputs, Quicksort O(n²) or special inputs).
   • Other properties: e.g. inplace, recursive or not, extra storage required.
6. Linear time sorts: Counting, Radix and Bucket (no analysis for bucket)