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