Search for tag: "algorithms"

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

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…

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…

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,…

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…

Minimum-cost circulations Cycle cancelling Minimum-cost flows Feasible then balanced then locally optimal Successive shortest paths: feasible and locally optimal then balanced

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

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

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

Edge-disjoint paths Undirected graphs Vertex capacities and vertex-disjoint paths Maximum bipartite matching The Jacobi-Berge alternating path algorithm (aka Ford-Fulkerson)

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

Definition of maximum flows Definition of minimum cuts The maxflow-mincut theorem Easy direction: follow the inequalities Harder direction: Residual graphs Ford-Fulkerson

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…

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…

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)…

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…

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 ]…

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…

Review session for Midterm 1

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…

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

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…

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

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