- 
    Logistics Read the questions Pareto-optimal points Separating points with parallel lines Rooted subtree search Nesting boxes Escape wiring Elmo and Daisy play cards…∞. Final Exam Review 
- 
    Splay trees Amortized time via potential function Access Lemma ⇒ O(log n) amortized time per splay Generalized Access Lemma ⇒ static optimality What is a…26. Splay trees and the dynamic optimality… 
- 
    What are online algorithms? Example: paging The lost cow problem Exponential search is 9-competitive Randomizing first step direction: expected competitive ratio 7 [Kao,…25. Online algorithms 
- 
    LP duality: swap roles of matrix constraints and variables Weak duality theorem: cx ≤ yAx ≤ yb Physical interpretation of optimal dual solution Vocabulary: basis,…24. LP duality and the simplex algorithm 
- 
    Definition of linear programming Example: Maximum flows Geometry: Lowest point in a convex polyhedron Infeasible and unbounded LPs Canonical (standard inequality) form…23. Linear programming 
- 
    Minimum-cost circulations Cycle cancelling Minimum-cost flows Feasible then balanced then locally optimal Successive shortest paths: feasible and locally optimal then…22. Minimum cost flows 
- 
    Minimum vertex cover Project selection Non-zero balances Lower bounds on edges21. More applications and extensions 
- 
    General strategy Scheduling final exams Tuple selection Disjoint path cover in dags Cycle cover in directed graphs20. More applications of maximum flow 
- 
    hashing collisions leaves in treaps Thomas the Tank Engine gets COVID cyclic shifts of strings19. Midterm 2 review 
- 
    Edge-disjoint paths Undirected graphs Vertex capacities and vertex-disjoint paths Maximum bipartite matching The Jacobi-Berge alternating path algorithm (aka…18. Applications/extensions of maximum flow 
- 
    Definition review Ford-Fulkerson Bad example with integer capacities Really bad example with irrational capacities Decomposing flows into paths and cycles Good…17. Maximum flow structure and algorithms 
- 
    Definition of maximum flows Definition of minimum cuts The maxflow-mincut theorem Easy direction: follow the inequalities Harder direction: Residual graphs…16. Maximum flows and minimum cuts 
- 
    Avoiding redundant comparisons The fail function and finite-state machine Knuth-Morris-Pratt: O(n) worst-case time Border of P = any proper prefix of P that is also a…15. String matching via careful failure 
- 
    The string matching problem Almost brute force -> O(mn) worst-case time but usually good in practice unless you are a potato Intuition: interpret strings as numbers…15. String matching via rolling hash 
- 
    Open addressed hashing Fictional analysis: Strongly universal hashing Linear probing and binary probing Analysis of binary probing: full versus popular 2-uniformity and…14. More Hashing 
- 
    Hash table definitions and standard fiction Deterministic hash functions are stupid. Families of hash functions Uniform (yawn), universal, and strongly universal…13. Hashing 
- 
    What are tail inequalities? Markov's inequality: Pr[ X > x ] ≤ E[X} / x Independent random variables Chebyshev: If X is sum of pairwise-independent 0/1…12. Tail inequalities 
- 
    Binary search tree (ordered dictionary) operations Treaps: BST with respect to keys + min-heap with respect to priorities Insert, delete, split, and join algorithms;…11. Treaps 
- 
    Review session for Midterm 110. Midterm review session 
- 
    Midterm 1 logistics Rawlins’ nuts and bolts problem Reductions to and from sorting nuts and/or bolts Randomized quicksort! Full-history recurrence Back of the…9. Matching nuts and bolts 
- 
    Reflections|Projections! Randomized algorithms: what and why? Discrete sample spaces, good old rock, events, probability, conditional probability Random variables:…8. Discrete probability review 
- 
    Finding minimum elements in every row of an array No other information: Brute force O(mn) is optimal Monotone: Minima in higher rows are above/left of minima in later…7. Speeding up dynamic programming 
- 
    Dynamic programming over directed acyclic graphs: longest path Saving space: Sliding windows Reconstructing structure by walking through memorized data Choudhury and…6. Revenge of the son of dynamic programming 
- 
    Intuitive sketches of common recursion patterns Dynamic programming in trees: Maximum independent set Memoization is depth-first search; dynamic programming is postorder…5. Even more dynamic programming 
- 
    Longest increasing subsequence, take 2 Tree-shaped DP: The woodcutter's problem4. More dynamic programming 
- 
    Example 1: Text segmentation (Interpunctio verborum) A sequence of X's is either nothing or an X followed by a sequence of X's Where does the first word end?…3. Backtracking and dynamic programming 
- 
    Representing polynomials as coefficients, roots, or sample values Converting from coefficients to samples is a linear transformation Divide-and-conquer via collapsible…2. Fast Fourier transforms 
- 
    Technical difficulties Welcome, introduction, about this class, important course policies Recursion: Tower of Hanoi Recursion: Karatsuba multiplication1. Administrivia, recursion 
Search for ""
