-
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
From Jeff Erickson
159 plays 0 -
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…
From Jeff Erickson
67 plays 0 -
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
From Jeff Erickson
72 plays 0 -
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
From Jeff Erickson
110 plays 0 -
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
From Jeff Erickson
173 plays 0 -
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
From Jeff Erickson
127 plays 0 -
Minimum vertex cover Project selection Non-zero balances Lower bounds on edges
21. More applications and extensions
From Jeff Erickson
121 plays 0 -
General strategy Scheduling final exams Tuple selection Disjoint path cover in dags Cycle cover in directed graphs
20. More applications of maximum flow
From Jeff Erickson
182 plays 0 -
hashing collisions leaves in treaps Thomas the Tank Engine gets COVID cyclic shifts of strings
19. Midterm 2 review
From Jeff Erickson
144 plays 0 -
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
From Jeff Erickson
226 plays 0 -
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
From Jeff Erickson
175 plays 0 -
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
From Jeff Erickson
219 plays 0 -
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
From Jeff Erickson
124 plays 0 -
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
From Jeff Erickson
105 plays 0 -
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
From Jeff Erickson
115 plays 0 -
Hash table definitions and standard fiction Deterministic hash functions are stupid. Families of hash functions Uniform (yawn), universal, and strongly universal…
13. Hashing
From Jeff Erickson
191 plays 0 -
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
From Jeff Erickson
156 plays 0 -
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
From Jeff Erickson
108 plays 0 -
Review session for Midterm 1
10. Midterm review session
From Jeff Erickson
132 plays 0 -
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
From Jeff Erickson
174 plays 0 -
Reflections|Projections! Randomized algorithms: what and why? Discrete sample spaces, good old rock, events, probability, conditional probability Random variables:…
8. Discrete probability review
From Jeff Erickson
177 plays 0 -
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
From Jeff Erickson
163 plays 0 -
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
From Jeff Erickson
189 plays 0 -
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
From Jeff Erickson
198 plays 0 -
Longest increasing subsequence, take 2 Tree-shaped DP: The woodcutter's problem
4. More dynamic programming
From Jeff Erickson
231 plays 0 -
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
From Jeff Erickson
371 plays 0 -
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
From Jeff Erickson
395 plays 0 -
Technical difficulties Welcome, introduction, about this class, important course policies Recursion: Tower of Hanoi Recursion: Karatsuba multiplication
1. Administrivia, recursion
From Jeff Erickson
729 plays 0
Search for ""