Things to Know
--------------
- will be updated as the quarter goes on
- disclaimer: not necessarily comprehensive
1. Counting
a. Rule of sum
b. Inclusion-exclusion principle
c. Rule of product
d. Counting with categories (division rule)
e. Complement trick
f. Sample k from n, where
fa. Order matters, replacement
fb. Order matters, no replacement
fc. Order doesn't matter, replacement
fd. Order doesn't matter, no replacement
g. Counting with recurrences
ga. Formulating recurrences
gb. Solving recurrences w/ guess & check
gc. Solving recurrences w/ unraveling
h. Bijective counting
ha. Stars and bars
haa. Soldiers in castles
hab. >= 1 soldier in every castle
hb. Identifying bijections
2. Proofs
a. Direct proof
b. Proof by cases
c. Proof by induction
d. Proof by strong induction
e. Combinatorial proofs
3. Asymptotic analysis
a. Big-omega notation
b. Big-theta notation
c. Big-O notation
d. Proving each of these cases
e. Best, worst, and average case
4. Sorting
a. Selection sort
b. Bubble sort
c. Insertion sort
d. Bucket sort
e. Merge sort
5. Loop invariants
a. Identifying loop invariants
b. Proving existence of loop invariants
c. Proving correctness via loop invariants
6. Searching
a. Linear search
b. Binary search
7. Divide and conquer
a. Designing/analyzing algorithms
b. Master theorem
8. Encoding
a. Encoding fixed-density strings
b. Lower and upper bounds for encoding
c. Theoretically optimal encodings
d. Algorithms for encoding and decoding