Search for tag: "algorithms"

∞. Final Exam Review

Logistics 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 133 plays 0  

26. Splay trees and the dynamic optimality conjecture

Splay 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 49 plays 0  

25. Online algorithms

What 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 56 plays 0  

24. LP duality and the simplex algorithm

LP 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 96 plays 0  

23. Linear programming

Definition 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 145 plays 0  

22. Minimum cost flows

Minimum-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 119 plays 0  

21. More applications and extensions

Minimum vertex cover Project selection Non-zero balances Lower bounds on edges

From  Jeff Erickson 107 plays 0  

20. More applications of maximum flow

General strategy Scheduling final exams Tuple selection Disjoint path cover in dags Cycle cover in directed graphs

From  Jeff Erickson 134 plays 0  

19. Midterm 2 review

hashing collisions leaves in treaps Thomas the Tank Engine gets COVID cyclic shifts of strings

From  Jeff Erickson 135 plays 0  

18. Applications/extensions of maximum flow

Edge-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 162 plays 0  

17. Maximum flow structure and algorithms

Definition 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 150 plays 0  

16. Maximum flows and minimum cuts

Definition 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 195 plays 0  

15. String matching via careful failure

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 suffix of P fail[j] - 1 is the…

From  Jeff Erickson 115 plays 0  

15. String matching via rolling hash

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 Use modular arithmetic, but…

From  Jeff Erickson 102 plays 0  

14. More Hashing

Open 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 93 plays 0  

13. Hashing

Hash 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 169 plays 0  

12. Tail inequalities

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 variables: E[ (X–μ)^2 ]…

From  Jeff Erickson 140 plays 0  

11. Treaps

Binary 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 91 plays 0  

10. Midterm review session

Review session for Midterm 1

From  Jeff Erickson 110 plays 0  

9. Matching nuts and bolts

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 envelope analysis via good and…

From  Jeff Erickson 147 plays 0  

8. Discrete probability review

Reflections|Projections! Randomized algorithms: what and why? Discrete sample spaces, good old rock, events, probability, conditional probability Random variables: expectation, conditional…

From  Jeff Erickson 145 plays 0  

7. Speeding up dynamic programming

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 rows Filtering: row minima in…

From  Jeff Erickson 143 plays 0  

6. Revenge of the son of dynamic programming

Dynamic programming over directed acyclic graphs: longest path Saving space: Sliding windows Reconstructing structure by walking through memorized data Choudhury and Ramachandran's algorithm:…

From  Jeff Erickson 158 plays 0  

5. Even more dynamic programming

Intuitive sketches of common recursion patterns Dynamic programming in trees: Maximum independent set Memoization is depth-first search; dynamic programming is postorder traversal

From  Jeff Erickson 162 plays 0