Files
Take the packet with you. The page below it is the morning-of sheet.
The PDF is about 22 pages: the notes, worked proofs, eight practice problems with a full answer key, and this crib typeset as the last page. The .tex file is the same document, if you want to edit or recompile it.
Morning-of crib
Order of work
What is true before. What the code does. What is true after. Then the growth rate.
Cases
Best is the friendliest input. Worst is the guarantee. If the loop bounds ignore the data, say there is no separate best case and mean it.
Counting
Cost times times, then sum. While-tests = bodies + 1. Nested shrinking loops usually pay \(N(N-1)/2\).
Sums
\(\sum_{i=1}^{n} i = n(n+1)/2\)
\(\sum_{i=1}^{n} i^{2} = n(n+1)(2n+1)/6\)
\(\sum_{i=0}^{n} 2^{i} = 2^{n+1}-1\)
Symbols
\(O\) no faster, \(\Omega\) no slower, \(\Theta\) tied. \(o\) strictly slower. \(\omega\) strictly faster. Loose \(O\) can be true. Drop constants only at the end. Log bases do not matter inside \(\Theta\).
Doubling
\(N \to 2N\) multiplies \(\Theta(N)\) by 2, \(\Theta(N^2)\) by 4, \(\Theta(N^3)\) by 8. \(\Theta(2^N)\) squares.
Notation
\([\,P\,]\) is a predicate. \(\{\texttt{code}\}\) is code. \(x_0\) is a frozen value. Stronger means more restrictive.
Direction
Forward from a given start: strongest postcondition. Backward from a goal: weakest precondition. Branches: fold the test into each side, join with \(\lor\).
Invariant
Init, often empty or one cell. Maintenance: assume, then one pass, then the counter moves. Termination: exact exit value plus the invariant gives the goal.
Insertion, 1-indexed
Invariant: \(A[1..j-1]\) is the original prefix, sorted. Best: \(t_j = 1\), sum \(n-1\), \(\Theta(n)\). Worst: \(t_j = j\), sum \(n(n+1)/2 - 1\), \(\Theta(n^2)\). Exit: \(j = n+1\).
Selection, 0-indexed
Invariant: the first \(k\) cells are the \(k\) smallest, sorted, and \(\le\) the suffix; the array is a permutation. Comparisons always \(N(N-1)/2\). Class always \(\Theta(N^2)\). Ties use <=, so the later index wins. Exit: \(k = N-1\). No last pass.
Before you hand it in
Does the first counter make the invariant obvious? Does maintenance say “assume”? Is the exit value a number? Did you give both cases, or a sentence explaining why there is only one? Did branch results get joined with \(\lor\)?