Dsgn&Analysis CS 3510
Popular in Course
Popular in ComputerScienence
This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 3510 at Georgia Institute of Technology - Main Campus taught by Staff in Fall. Since its upload, it has received 12 views. For similar materials see /class/234155/cs-3510-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.
Reviews for Dsgn&Analysis
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 11/02/15
UC BerkeleyicS 170 Ef cient Algorithms and lntractable Problems Handout 13 Lecturer Shyam Lakshmin October 14 2003 Notes 13 for CS 170 1 Introduction to Dynamic Programming Recall our rst algorithm for computing the n th Fibonacci number F it just recursively applied the de nition Fn Fn1 Fn72 so that a function call to compute Fn resulted in two functions calls to compute Fn1 and Fn2 and so on The problem with this approach was that it was very expensive because it ended up calling a function to compute for each j lt 71 possibly very many times even after had already been computed We improved this algorithm by building a table of values of Fibonacci numbers computing Fn by looking up Fn1 and an in the table and simply adding them This lowered the cost of computing Fn from exponential in n to just linear in n This worked because we could sort the problems of computing Fn simply by increasing n and compute and store the Fibonacci numbers with small 71 before computing those with large 71 Dynamic programming uses exactly the same idea 1 Express the solution to a problem in terms of solutions to smaller problems 2 Solve all the smallest problems rst and put their solutions in a table then solve the next larger problems putting their solutions into the table solve and store the next larger problems and so on up to the problem one originally wanted to solve Each problem should be easily solvable by looking up and combining solutions of smaller problems in the table For Fibonacci numbers how to compute Fn in terms of smaller problems Fn1 and an was obvious For more interesting problems guring out how to break big problems into smaller ones is the tricky part Once this is done the the rest of algorithm is usually straightforward to produce We will illustrate by a sequence of examples starting with onedimensional problems that are most analogous to Fibonacci 2 String Reconstruction Suppose that all blanks and punctuation marks have been inadvertently removed from a text le and its beginning was polluted with a few extraneous characters so the le looks faraway land You want to reconstruct the le using r r like 77lirmr eni a dictionary This is a typical problem solved by dynamic programming We must de ne what is an appropriate notion of subproblem Subproblems must be ordered by size and each subproblem must be easily solvable once we have the solutions to all smaller subproblems Once we have the right notion of a subproblem we write the appropriate recursive equation expressing how a subproblem is solved based on solutions to smaller subproblems and the Notes number 13 2 program is then trivial to write The complexity of the dynamic programming algorithm is precisely the total number of subproblems times the number of smaller subproblems we must examine in order to solve a subproblem In this and the next few examples we do dynamic programming on a onedimensional object7in this case a string next a sequence of matrices then a set of strings alphabetically ordered etc The basic observation is this A one dimensional object of length n has about it2 sub objects substrings etc where a sub object is de ned to span the range from i to j where ij n In the present case a subproblem is to tell whether the substring of the le from character i to j is the concatenation of words from the dictionary Concretely let the le be f1 n and consider a 2 D array of Boolean variables Tij where Tij is true if and only if the string i j is the concatenation of words from the dictionary The recursive equation is this T jmd njhv V HaiATw1J iSkltj In principle we could write this equation verbatim as a recursive function and execute it The problem is that there would be exponentially many recursive calls for each short string and 3 calls overall Dynamic programming can be seen as a technique of implementing such recursive pro grams that have heavy overlap between the recursion trees of the two recursive calls so that the recursive function is called once for each distinct argument indeed the recursion is usually unwound and disappears altogether This is done by modifying the recursive program so that in place of each recursive call a table is consulted To make sure the needed answer is in the table we note that the lengths of the strings on the right hand side of the equation above are k 7 i 1 and j 7 k a both of which are shorter than the string on the left of length j 7 i 1 This means we can ll the table in increasing order of string length for d 0 to n7 1 do d 1 is the size string length of the subproblem being solved for i 1 to n 7 1 do the start of the subproblem being solved jid if dictzi then Tij true else forkitoj71do if Ti k true and Tk 1j true then do Tij true The complexity of this program is 0n3 three nested loops ranging each roughly over n values Unfortunately this program just returns a meaningless Boolean and does not tell us how to reconstruct the text Here is how to reconstruct the text Just expand the innermost loop the last assignment statement to Tij true rstij k exit for where rst is an array of pointers initialized to nil Then if Tij is true so that the substring from i to j is indeed a concatenation of dictionary words then rstij points to a breaking point in the interval ij Notice that this improves the running time by exiting the for loop after the rst match more optimizations are possible This is typical of dynamic programming algorithms Once the basic algorithm has been derived using Notes number 13 3 dynamic programming clever modi cations that exploit the structure of the problem speed up its running time 3 Edit Distance 31 De nition When you run a spell checker on a text and it nds a word not in the dictionary it normally proposes a choice of possible corrections If it nds stell it might suggest tell swell stull still steel steal stall spell smell shell and sell As part of the heuristic used to propose alternatives words that are close to the misspelled word are proposed We will now see a formal de nition of distance between strings and a simple but ef cient algorithm to compute such distance The distance between two strings z 1 mn and y yl ym is the minimum number of errors edit operations needed to transform z into y where possible operations are 0 insert a character insertx i a m1z2miaxi1zn o delete a character deletemi i2quot39i1i1quot39n o modify a character modifym i a z1m2millami1xw For example if z aabab and y babb then one 3 steps way to go from x to y is a a b a b x b a a b a b x7 insertx0b b a b a b x77 delete x 2 b a b b y delete x 4 another sequence still in three steps is a a b a b x a b a b x7 delete x1 b a b x77 deletex 1 b a b b y insert x 3b Can you do better 32 Computing Edit Distance To transform ml zn into yl ym we have three choices 0 put ym at the end z a m1mnym and then transform z1zn into y1ym1 o delete zn z a 1 mnll and then transform ml mnll into yl gm 0 change zn into ym if they are different z a m1mnllym and then transform 951 39 39 39 n71 into y1quot39ym71 Notes number 13 4 This suggests a recursive scheme where the sub problems are of the form how many operations do we need to transform 1 z into yl yj Our dynamic programming solution will be to de ne a n 1 x m 1 matrix M that we will ll so that for every 0 g i g n and 0 g j g m Mij is the minimum number of operations to transform 1 m into yl yj The content of our matrix M can be formalized recursively as follows 0 MOj j because the only way to transform the empty string into yl yj is to add the j characters yl yj o Mi O i for similar reasons 0 Forij1 M j min Lil 1 17 M2 j7 1H1 Mi1j71 changei7 where changezi yj 1 if M 7 W and changemyj 0 otherwise As an example consider again z aabab and y babb Ababb What is then the edit distance between z and y The table has nm entries each one computable in constant time One can construct an auxiliary table Op such that Op speci es what is the rst operation to do in order to optimally transform 1 z into yl yj The full algorithm that lls the matrices can be speci ed in a few lines algorithm EdDist x y n lengthm m lengthy for i 0 to n Mi0i for j0 to m Ml07jlj for i1 to n for j1 to m if m yj then change 0 else change 1 Notes number 13 7 1j 1 Op deletez if Mij711ltMij then Mij711 Op insertziyj if 7 1j 7 1 change lt MB then Mi71j71change if change 0 then Opij none else Opij changeziyj 4 Longest Common Subsequence A subsequence of a string is obtained by taking a string and possibly deleting elements If ml mn is a string and 1 1 lt 2 lt lt ik n is a strictly increasing sequence of indices then zilziz mm is a subsequence of m For example art is a subsequence of algorithm In the longest common subsequence problem given strings z and y we want to nd the longest string that is a subsequence of both For example art is the longest common subsequence of algorithm and parachute As usual we need to nd a recursive solution to our problem and see how the problem on strings of a certain length can be reduced to the same problem on smaller strings The length of the lcs of z z1zn and y y1ym is either 0 The length of the lcs of 1 mn1 and y1ym or o The length of the lcs of 1 mn and y1ym1 or 0 1 the length of the lcs of 1 mkl and y1 ym1 if zn ym The above observation shows that the computation of the length of the lcs of z and y reduces to problems of the form what is the length of the lcs between z1mi and y1 Our dynamic programming solution uses an n 1 x m 1 matrix M such that for every 0 g i g n and 0 g j g m Mij contains the length of the lcs between z1m and y1 yj The matrix has the following formal recursive de nition M2 0 0 MOj 0 Mij max 7 1j W471 Mlit 1734 1l 5qivyj where eqmiyj 1 if z yj eqmi yj 0 otherwise
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'