6.006 Introduction to Algorithms, Lecture 15: Recursive Algorithms

Introduction to Algorithms: 6.006 Massachusetts Institute of Technology Instructors: Erik Demaine, Jason Ku, and Justin Solomon Lecture 15: Recursive Algorithms Lecture 15: Recursive Algorithms How to Solve an Algorithms Problem (Review) • Reduce to a problem you already know (use data structure or algorithm) Search Data Structures Array Linked List Dynamic Array Sorted Array Direct-Access Array Hash Table AVL Tree Binary Heap Sort Algorithms Insertion Sort Selection Sort Merge Sort Counting Sort Radix Sort AVL Sort Heap Sort Graph Algorithms Breadth First Search DAG Relaxation (DFS + Topo) Dijkstra Bellman-Ford Johnson • Design your own recursive algorithm – Constant-sized program to solve arbitrary input – Need looping or recursion, analyze by induction – Recursive function call: vertex in a graph, directed edge from A → B if B calls A – Dependency graph of recursive calls must be acyclic (if can terminate) – Classify based on shape of graph Class Brute Force Decrease & Conquer Divide & Conquer Dynamic Programming Greedy/Incremental Graph Star Chain Tree DAG Subgraph – Hard part is thinking inductively to construct recurrence on subproblems – How to solve a problem recursively (SRT BOT) 1. 2. 3. 4. 5. 6. Subproblem definition Relate subproblem solutions recursively Topological order on subproblems (⇒ subproblem DAG) Base cases of relation Original problem solution via subproblem(s) Time analysis 2 Lecture 15: Recursive Algorithms Merge Sort in SRT BOT Framework • Merge sorting an array A of n elements can be expressed in SRT BOT as follows: – Subproblems: S(i, j) = sorted array on elements of A[i : j] for 0 ≤ i ≤ j ≤ n – Relation: S(i, j) = merge(S(i, m), S(m, j)) where m = b(i + j)/2c – Topo. order: Increasing j − i – Base cases: S(i, i + 1) = [A[i]] – Original: S(0, n) – Time: T (n) = 2 T (n/2) + O(n) = O(n lg n) • In this case, subproblem DAG is a tree (divide & conquer) Fibonacci Numbers • Suppose we want to compute the nth Fibonacci number Fn • Subproblems: F (i) = the ith Fibonacci number Fi for i ∈ {0, 1, . . . , n} • Relation: F (i) = F (i − 1) + F (i − 2) (definition of Fibonacci numbers) • Topo. order: Increasing i • Base cases: F (0) = 0, F (1) = 1 • Original prob.: F (n) 1 2 3 def fib(n): if n < 2: return n return fib(n - 1) + fib(n - 2) # base case # recurrence • Divide and conquer implies a tree of recursive calls (draw tree) • Time: T (n) = T (n − 1) + T (n − 2) + O(1) > 2T (n − 2), T (n) = Ω(2n/2 ) exponential... :( • Subproblem F (k) computed more than once! (F (n − k) times) • Can we avoid this waste? Lecture 15: Recursive Algorithms 3 Re-using Subproblem Solutions • Draw subproblem dependencies as a DAG • To solve, either: – Top down: record subproblem solutions in a memo and re-use (recursion + memoization) – Bottom up: solve subproblems in topological sort order (usually via loops) • For Fibonacci, n + 1 subproblems (vertices) and < 2n dependencies (edges) • Time to compute is then O(n) additions 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 # recursive solution (top down) def fib(n): memo = {} def F(i): if i < 2: return i if i not in memo: memo[i] = F(i - 1) + F(i - 2) return memo[i] return F(n) # iterative solution (bottom up) def fib(n): F = {} F[0], F[1] = 0, 1 for i in range(2, n + 1): F[i] = F[i - 1] + F[i - 2] return F[n] # base cases # check memo # relation # original # # # # base cases topological order relation original • A subtlety is that Fibonacci numbers grow to Θ(n) bits long, potentially  word size w • Each addition costs O(dn/we) time • So total cost is O(ndn/we) = O(n + n2 /w) time 4 Lecture 15: Recursive Algorithms Dynamic Programming • Weird name coined by Richard Bellman – Wanted government funding, needed cool name to disguise doing mathematics! – Updating (dynamic) a plan or schedule (program) • Existence of recursive solution implies decomposable subproblems1 • Recursive algorithm implies a graph of computation • Dynamic programming if subproblem dependencies overlap (DAG, in-degree > 1) • “Recurse but re-use” (Top down: record and lookup subproblem solutions) • “Careful brute force” (Bottom up: do each subproblem in order) • Often useful for counting/optimization problems: almost trivially correct recurrences How to Solve a Problem Recursively (SRT BOT) 1. Subproblem definition subproblem x ∈ X • Describe the meaning of a subproblem in words, in terms of parameters • Often subsets of input: prefixes, suffixes, contiguous substrings of a sequence • Often record partial state: add subproblems by incrementing some auxiliary variables 2. Relate subproblem solutions recursively x(i) = f (x(j), . . .) for one or more j < i 3. Topological order to argue relation is acyclic and subproblems form a DAG 4. Base cases • State solutions for all (reachable) independent subproblems where relation breaks down 5. Original problem • Show how to compute solution to original problem from solutions to subproblem(s) • Possibly use parent pointers to recover actual solution, not just objective function 6. Time analysis P • x∈X work(x), or if work(x) = O(W ) for all x ∈ X, then |X| · O(W ) • work(x) measures nonrecursive work in relation; treat recursions as taking O(1) time 1 This property often called optimal substructure. It is a property of recursion, not just dynamic programming Lecture 15: Recursive Algorithms 5 DAG Shortest Paths • Recall the DAG SSSP problem: given a DAG G and vertex s, compute δ(s, v) for all v ∈ V • Subproblems: δ(s, v) for all v ∈ V • Relation: δ(s, v) = min{δ(s, u) + w(u, v) | u ∈ Adj− (v)} ∪ {∞} • Topo. order: Topological order of G • Base cases: δ(s, s) = 0 • Original: All subproblems P − v∈V O(1 + | Adj (v)|) = O(|V | + |E|) • Time: • DAG Relaxation computes the same min values as this dynamic program, just – step-by-step (if new value < min, update min via edge relaxation), and – from the perspective of u and Adj+ (u) instead of v and Adj− (v) Bowling • Given n pins labeled 0, 1, . . . , n − 1 • Pin i has value vi • Ball of size similar to pin can hit either – 1 pin i, in which case we get vi points – 2 adjacent pins i and i + 1, in which case we get vi · vi+1 points • Once a pin is hit, it can’t be hit again (removed) • Problem: Throw zero or more balls to maximize total points • Example: [ −1, 1 , 1 , 1 , 9, 9 , 3 , −3, −5 , 2, 2 ] 6 Lecture 15: Recursive Algorithms Bowling Algorithms • Let’s start with a more familiar divide-and-conquer algorithm: – Subproblems: B(i, j) = maximum score starting with just pins i, i + 1, . . . , j − 1, for 0 ≤ i ≤ j ≤ n – Relation: ∗ m = b(i + j)/2c ∗ Either hit m and m + 1 together, or don’t ∗ B(i, j) = max{vm · vm+1 + B(i, m) + B(m + 2, j), B(i, m + 1) + B(m + 1, j)} – Topo. order: Increasing j − i – Base cases: B(i, i) = 0, B(i, i + 1) = max{vi , 0} – Original: B(0, n) – Time: T (n) = 4 T (n/2) + O(1) = O(n2 ) • This algorithm works but isn’t very fast, and doesn’t generalize well (e.g., to allow for a bigger ball that hits three balls at once) • Dynamic programming algorithm: use suffixes – Subproblems: B(i) = maximum score starting with just pins i, i + 1, . . . , n − 1, for 0 ≤ i ≤ n – Relation: ∗ Locally brute-force what could happen with first pin (original pin i): skip pin, hit one pin, hit two pins ∗ Reduce to smaller suffix and recurse, either B(i + 1) or B(i + 2) ∗ B(i) = max{B(i + 1), vi + B(i + 1), vi · vi+1 + B(i + 2)} – Topo. order: Decreasing i (for i = n, n − 1, . . . , 0) – Base cases: B(n) = B(n + 1) = 0 – Original: B(0) – Time: (assuming memoization) ∗ Θ(n) subproblems · Θ(1) work in each ∗ Θ(n) total time • Fast and easy to generalize! • Equivalent to maximum-weight path in Subproblem DAG: B0 max{v0 , 0} B1 v0 · v1 max{v1 , 0} B2 v1 · v2 max{v2 , 0} v2 · v3 B3 ··· Bn Lecture 15: Recursive Algorithms 7 Bowling Code • Converting a SRT BOT specification into code is automatic/straightforward • Here’s the result for the Bowling Dynamic Program above: 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 # recursive solution (top down) def bowl(v): memo = {} def B(i): if i >= len(v): return 0 if i not in memo: memo[i] = max(B(i+1), v[i] + B(i+1), v[i] * v[i+1] + B(i+2)) return memo[i] return B(0) # iterative solution (bottom up) def bowl(v): B = {} B[len(v)] = 0 B[len(v)+1] = 0 for i in reversed(range(len(v))): B[i] = max(B[i+1], v[i] + B(i+1), v[i] * v[i+1] + B(i+2)) return B[0] # # # # # base cases check memo relation: skip pin i OR bowl pin i separately OR bowl pins i and i+1 together # original # base cases # # # # # topological order relation: skip pin i OR bowl pin i separately OR bowl pins i and i+1 together original How to Relate Subproblem Solutions • The general approach we’re following to define a relation on subproblem solutions: – Identify a question about a subproblem solution that, if you knew the answer to, would reduce to “smaller” subproblem(s) ∗ In case of bowling, the question is “how do we bowl the first couple of pins?” – Then locally brute-force the question by trying all possible answers, and taking the best ∗ In case of bowling, we take the max because the problem asks to maximize – Alternatively, we can think of correctly guessing the answer to the question, and directly recursing; but then we actually check all possible guesses, and return the “best” • The key for efficiency is for the question to have a small (polynomial) number of possible answers, so brute forcing is not too expensive • Often (but not always) the nonrecursive work to compute the relation is equal to the number of answers we’re trying