![Top-down and Bottom-up ()
var m := map(0 0, 1 1)
function fib(n)
if key n is not in map m
m[n] := fib(n 1) + fib(n 2)
return m[n]
Top-down (Memoization) Bottom-up
function fib(n)
if n = 0
return 0
else
var previousFib := 0, currentFib := 1
repeat n 1 times // loop is skipped if n = 1
var nextFib := previousFib + currentFib
previousFib := currentFib
currentFib := nextFib
return currentFib](https://image.slidesharecdn.com/dynamicprogramming-161202185322/85/Dynamic-Programming-Laughlin-Lunch-and-Learn-5-320.jpg)
More Related Content
What's hot (20)
Similar to Dynamic Programming - Laughlin Lunch and Learn (20)
Recently uploaded (20)
Dynamic Programming - Laughlin Lunch and Learn
- 1. HOPEFULLY SORT OF INTERESTING ALGO TALK Lunch and Learn 12.01.2016
- 2. Big-O Big-O Operations for 10 things Operations for 100 things (1) 1 1 (log ) 3 7 () 10 100 ( log ) 30 700 (2) 100 10000 (2 ) 1024 2^100 (!) 3628800 100!
- 3. Dynamic Programming Break a problem down into sub-problems Store the results to avoid computing again Two main components Optimal substructure Overlapping sub-problems
- 4. Fibonacci Sequence (2 ) function fib(n) if n <= 1 return n return fib(n 1) + fib(n 2) How many statements do we need to compute ()? Prove that () can be solved in time, where > 1. Solve for using quadratic formula = + fib(1) = 1 fib(n) = fib(n-1) + fib(n-2) an a(n-1) + a(n-2) a2 a + 1 + 1.62, which satisfies a2 = 1 + 1
- 5. Top-down and Bottom-up () var m := map(0 0, 1 1) function fib(n) if key n is not in map m m[n] := fib(n 1) + fib(n 2) return m[n] Top-down (Memoization) Bottom-up function fib(n) if n = 0 return 0 else var previousFib := 0, currentFib := 1 repeat n 1 times // loop is skipped if n = 1 var nextFib := previousFib + currentFib previousFib := currentFib currentFib := nextFib return currentFib
- 6. Hyphenation and Justification ( ) If a paragraph contains possible breakpoints, the number of situations that must be evaluated naively is 2 since any two consecutive words may get split up by a break.
- 7. Knuth-Plass Algorithm Considers a paragraph to be a sequence 1, 2, . of items, where each item ヰ is either a box, a glue, or a penalty specification.
- 8. Knuth-Plass Algorithm (cont.) Box: Width of the box: i, some representing the space occupied by the box. Glue: Three of importance: ゐ is the ideal or normal width is the stretchability ю is the shrinkability Penalty: Potential places to end of line and begin another. Certain aesthetic cost High indicates poor place to break, negative indicates a good place to break Uses ゐ to represent width added to the line just before the break occurs
- 9. Knuth-Plass Algorithm (cont.) Demerits: measures the badness of fit Badness is the amount of stretching or shrinking.
- 10. Knuth-Plass Algorithm (cont.) Calculating demerits adjustment = available width - text width If adjustment <= 0 adj ratio = adj 歎 avl shk If adjustment > 0 adj ratio = adj 歎 avl str badness = |adj ratio|3 100 + 0揃5
- 11. Knuth-Plass Algorithm (cont.) Goals: Minimize ＄ of each line Dynamic programming comes into play 1) Scan line for breaking opportunities 2) At each opportunity, look at prior opportunities 3) Consider a candidate line between these two opportunities 4) Compute the demerits of this line candidate 5) Select the line candidate with the minimum demerits
- 12. Knuth-Plass Algorithm (cont.) https://github.com/bramstein/typeset/blob/mast er/src/linebreak.js
- 13. Greedy Algorithm The Knuth-Plass algorithm will almost always be more pleasing to look at, because the Greedy Algorithm may leave too much whitespace at the end of a line. Still, the lighter runtime cost of running Greedy () vs Knuth-Plasss (2) is why most modern browsers will use the Greedy algorithm. SpaceLeft := LineWidth for each Word in Text if (Width(Word) + SpaceWidth) > SpaceLeft insert line break before Word in Text SpaceLeft := LineWidth - Width(Word) else SpaceLeft := SpaceLeft - (Width(Word) + SpaceWidth)
- 14. P vs NP The general class of questions for which some algorithm can provide an answer in polynomial time is called "class P" or just "P The class of questions for which an answer can be verified in polynomial time is called NP, which stands for "nondeterministic polynomial time. An answer to the P = NP question would determine whether problems that can be verified in polynomial time can also be solved in polynomial time.
- 15. Turing Machines A Turing Machine can do everything that a real computer can do. The Turing Machine model contains these things: an infinite tape as its unlimited memory a tape head that can read and write symbols and move around the tape M1 = On input string w: 1. Sweep left to right across the tape, crossing off every other 0. 2. If in stage 1 the tape contained a single 0, accept. 3. If in stage 1 the tape contained more than a single 0 and the number of 0s was odd, reject 4. Return the head to the left-hand end of the tape. 5. Go to stage 1.
- 16. Turing Machines (cont.) M1 = On input string w: 1. Sweep left to right across the tape, crossing off every other 0. 2. If in stage 1 the tape contained a single 0, accept. 3. If in stage 1 the tape contained more than a single 0 and the number of 0s was odd, reject 4. Return the head to the left-hand end of the tape. 5. Go to stage 1. M1 decides = {02 | 0}, the language consisting of all strings of 0s whose length is a power of 2.
- 17. Turing Machines and Big-O M2 = On input string w: 1. Scan across the tape and reject if a 0 is found to the right of a 1. 2. Repeat if both 0s and 1s remain on the tape: 3. Scan across the tape, crossing off a single 0 and a single 1. 4. If 0s still remain after all the 1st have been crossed off, or if 1s still remain after all the 0s have been crossed off, reject. Else, if neither 0s nor 1s remain on the tape, accept. M2 decides = {0 1 | 0}, the language consisting of all strings of 0s followed by 1s.
- 18. Thank you