Search for tag: "algorithms"
∞. Final Exam ReviewLogistics Read the questions Pareto-optimal points Separating points with parallel lines Rooted subtree search Nesting boxes Escape wiring Elmo and Daisy play cards badly
From Jeff Erickson
147 plays
0
|
|
26. Splay trees and the dynamic optimality conjectureSplay trees Amortized time via potential function Access Lemma ⇒ O(log n) amortized time per splay Generalized Access Lemma ⇒ static optimality What is a "dynamic BST"? Geometric…
From Jeff Erickson
56 plays
0
|
|
25. Online algorithmsWhat are online algorithms? Example: paging The lost cow problem Exponential search is 9-competitive Randomizing first step direction: expected competitive ratio 7 [Kao, Reif, Tate}: Randomizing…
From Jeff Erickson
67 plays
0
|
|
24. LP duality and the simplex algorithmLP duality: swap roles of matrix constraints and variables Weak duality theorem: cx ≤ yAx ≤ yb Physical interpretation of optimal dual solution Vocabulary: basis, location, value, feasible,…
From Jeff Erickson
104 plays
0
|
|
23. Linear programmingDefinition of linear programming Example: Maximum flows Geometry: Lowest point in a convex polyhedron Infeasible and unbounded LPs Canonical (standard inequality) form Example: Shortest paths as a…
From Jeff Erickson
164 plays
0
|
|
22. Minimum cost flowsMinimum-cost circulations Cycle cancelling Minimum-cost flows Feasible then balanced then locally optimal Successive shortest paths: feasible and locally optimal then balanced
From Jeff Erickson
126 plays
0
|
|
21. More applications and extensionsMinimum vertex cover Project selection Non-zero balances Lower bounds on edges
From Jeff Erickson
116 plays
0
|
|
20. More applications of maximum flowGeneral strategy Scheduling final exams Tuple selection Disjoint path cover in dags Cycle cover in directed graphs
From Jeff Erickson
163 plays
0
|
|
19. Midterm 2 reviewhashing collisions leaves in treaps Thomas the Tank Engine gets COVID cyclic shifts of strings
From Jeff Erickson
140 plays
0
|
|
18. Applications/extensions of maximum flowEdge-disjoint paths Undirected graphs Vertex capacities and vertex-disjoint paths Maximum bipartite matching The Jacobi-Berge alternating path algorithm (aka Ford-Fulkerson)
From Jeff Erickson
207 plays
0
|
|
17. Maximum flow structure and algorithmsDefinition review Ford-Fulkerson Bad example with integer capacities Really bad example with irrational capacities Decomposing flows into paths and cycles Good augmenting paths: fattest and shortest
From Jeff Erickson
161 plays
0
|
|
16. Maximum flows and minimum cutsDefinition of maximum flows Definition of minimum cuts The maxflow-mincut theorem Easy direction: follow the inequalities Harder direction: Residual graphs Ford-Fulkerson
From Jeff Erickson
209 plays
0
|
|
15. String matching via careful failureAvoiding 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 suffix of P fail[j] - 1 is the…
From Jeff Erickson
123 plays
0
|
|
15. String matching via rolling hashThe 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 Use modular arithmetic, but…
From Jeff Erickson
105 plays
0
|
|
14. More HashingOpen addressed hashing Fictional analysis: Strongly universal hashing Linear probing and binary probing Analysis of binary probing: full versus popular 2-uniformity and Chebyshev imply O(log n)…
From Jeff Erickson
113 plays
0
|
|
13. HashingHash table definitions and standard fiction Deterministic hash functions are stupid. Families of hash functions Uniform (yawn), universal, and strongly universal (2-uniform) families of hash…
From Jeff Erickson
181 plays
0
|
|
12. Tail inequalitiesWhat 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 variables: E[ (X–μ)^2 ]…
From Jeff Erickson
152 plays
0
|
|
11. TreapsBinary search tree (ordered dictionary) operations Treaps: BST with respect to keys + min-heap with respect to priorities Insert, delete, split, and join algorithms; time bounded by node depth…
From Jeff Erickson
106 plays
0
|
|
9. Matching nuts and boltsMidterm 1 logistics Rawlins’ nuts and bolts problem Reductions to and from sorting nuts and/or bolts Randomized quicksort! Full-history recurrence Back of the envelope analysis via good and…
From Jeff Erickson
168 plays
0
|
|
8. Discrete probability reviewReflections|Projections! Randomized algorithms: what and why? Discrete sample spaces, good old rock, events, probability, conditional probability Random variables: expectation, conditional…
From Jeff Erickson
164 plays
0
|
|
7. Speeding up dynamic programmingFinding 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 rows Filtering: row minima in…
From Jeff Erickson
154 plays
0
|