DAA Cheat Sheet

Foundations

Algorithm: unambiguous steps; input, output, definiteness, finiteness, effectiveness.
3 gcd methods: Euclid gcd(m,n)=gcd(n,m mod n); consecutive integer; middle-school.
Problem solving: understand, device, exact/approx, structures, technique, specify, prove, analyse, code.
Pseudocode: natural + programming language; no standard syntax.
Techniques: brute force, D&C, greedy, decrease & conquer, DP, transform & conquer, backtracking.

Space: S(P)=c+Sp. Time: T(n)~cop x C(n).
Cases: worst, best, average (not mean of worst/best), amortized.
Framework: input size -> units -> growth -> cases.
Examples: largest n-1; uniqueness n^2/2; matrix n^3; binary digits log n; factorial n; Hanoi 2^n-1.

O upper, Omega lower, Theta tight; little-oh strict.
O(g1)+O(g2)=O(max{g1,g2}).
Order: 1<log n<n<n log n<n^2<n^3<2^n<n!.
Master: compare f(n) with n^(log_b a): smaller -> n^(log_b a); equal -> +log n; larger -> f(n).

Array vs linked list; stack LIFO; queue FIFO; priority queue via heap.
Sorts: bubble/selection/insertion O(n^2); merge/quick/heap O(n log n); counting (n+k); radix d(n+k).
Merge stable not in-place; quick/selection/heap not stable; bubble/insertion stable.
Hash: chaining vs open addressing; rehash doubles.
BST in-order = sorted; RB-tree height O(log n).
DP: overlapping subproblems + optimal substructure; MCM O(n^3); LCS O(mn).