Things to Know
--------------
- will be updated as the quarter goes on
- disclaimer: not necessarily comprehensive
0. 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
1. Proofs
a. Direct proof
b. Proof by cases
c. Proof by induction
d. Proof by strong induction
e. Combinatorial proofs
2. 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
3. Sorting
a. Selection sort
b. Bubble sort
c. Insertion sort
d. Bucket sort
e. Merge sort
4. Loop invariants
a. Identifying loop invariants
b. Proving existence of loop invariants
c. Proving correctness via loop invariants
5. Searching
a. Linear search
b. Binary search
6. Divide and conquer
a. Designing/analyzing algorithms
b. Master theorem
7. Encoding
a. Encoding fixed-density strings
b. Lower and upper bounds for encoding
c. Theoretically optimal encodings
d. Algorithms for encoding and decoding
8. Probability
a. Basic probability principles
aa. Defining the sample space
ab. Defining events in the sample space
ac. Probability distribution properties
ad. Independence
b. Common distributions
ba. Uniform distribution
bb. Binomial distribution
c. Conditional probability
ca. Bayes' rule
d. Expectation and variance
da. Definitions
db. Conditional expectation
dc. Linearity of expectation
e. Analysis of hashing
9. Graphs
a. Lingo
aa. Types of graphs
aaa. Directed
aab. Undirected
aac. Simple
aad. Multigraph
aae. Directed acyclic
aaf. Complete
aag. Edgeless
aah. Complement
aai. Bipartite
aaj. Hypercube
aak. Tree (directed)
aal. Tree (undirected)
aam. Rooted tree
aan. Binary tree
aao. Full binary tree
ab. Degree
ac. Connectedness
aca. Connected components
acb. Weakly connected components
acc. Strongly connected components
acd. Bridges
b. Graph representations
ba. Adjacency list
bb. Adjacency matrix
c. Handshaking lemma
d. Paths and cycles
da. Eulerian paths/cycles
db. Hamiltonian paths/cycles
dc. Fleury's algorithm
e. Using graphs to model problems
f. Graph search
fa. Reachability