6 006 Intro to Algorithms Recitation 19 April 15 2011 Dynamic Programming 1D Optimization Fibonacci Sequence To efficiently calculate F x the xth element of the Fibonacci sequence we can construct the array F from left to right or bottom up We start with F 0 1 and F 1 1 and iteratively calculate the next number in the sequence using F i F i 1 F i 2 until we get F x Crazy 8 s In the game Crazy 8 s we want to find the longest subsequence of cards where consecutive cards must have the same value same suit or contains at least one eight If the cards are stored in array C we want to keep an auxiliary score array S where S i represents the length of the longest subsequence ending with card C i Again we will construct the array C from left to right or bottom up We start with S 0 1 since the longest subsequence ending with the first card is that card itself and has a length of 1 We iteratively calculate the next score S i by scanning all previous scores and set S i to be S k 1 where S k represents the length of the longest subsequence that card C i can be appended to Dynamic Programming 2D Optimization Edit Distance In the edit distance problem we have two strings X and Y Our goal is to find out the minimum cost of transforming string X into string Y using a set of editing operations We will iterate through the characters of X and at each character we have three editing operations that we can make 1 Copy the current character of the source into the output 2 Delete the current character of the source and go onto the next character 3 Insert a new character into the output string For example let s look at how we can edit MAKER to DATE 6 006 Intro to Algorithms Recitation 19 April 15 2011 Using a sequence of Insert D Delete Copy Insert T Delete Copy Delete we were able to edit MAKER into DATE Note that this sequence is not unique We could have swapped the first Insert D and Delete with each other without changing the final result A naive edit could have been deleting all of MAKER and then inserting all of DATE making no copies in the edit sequence There are many ways we can edit X to Y but we want to find which edit sequence has minimum cost Each of the editing operations has some cost associated to it For instance we can assign costs as such Copy Cost 5 Delete Cost 10 Insert Cost 7 Our editing sequence Insert D Delete Copy Insert T Delete Copy Delete has a total cost of 54 according to our cost model If we chose to delete all of MAKER and then insert all of DATE we could have made 5 deletions and 4 insertions resulting in a total cost of 78 Clearly our first editing sequence is better than this naive edit but how can we figure out what s the best overall Let X 0 and Y 0 be the strings X and Y without their last character e g if X is DATE X 0 is DAT An important observation to make is that we can construct an editing sequence from X to Y in at most three ways 1 Take the minimum cost editing sequence of X 0 to Y 0 If the next characters are equal then we can append a Copy to that editing sequence 6 006 Intro to Algorithms Recitation 19 April 15 2011 2 Take the minimum cost editing sequence of X to Y 0 and append an Insert last character of Y to that editing sequence 3 Take the minimum cost editing sequence of X 0 to Y and append a Delete to that editing sequence Here we are using optimal solutions to smaller problems to help us construct an optimal solution to the total problem Using proof by contradiction we can prove that the minimum cost editing sequence of X to Y must be one of the three sequences resulting above To figure out which sequence is the best simply take the minimum of the three sequences costs and that will be the minimum editing sequence for X to Y Like the Fibonacci and Crazy 8 s examples we want to construct the minimum editing sequence from bottom up We do NOT want to start at figuring out the sequence from X to Y and recursively solving for the sequences from X 0 to Y 0 X to Y 0 and X 0 to Y Instead we can start with the smallest sequences and construct larger sequences from optimal solutions that we run into To solve this problem we are going to use a 2D matrix Each cell in the matrix corresponds to the cost of a minimum cost editing sequence to transform a prefix of X to a prefix of Y In the example below the shaded cell will contain the cost of editing MAKE into D Each cell will also contain the last operation of the editing sequence for that particular transformation Note that for each cell based on our important observation above we can construct an optimal editing sequence only if the above cell left cell and above left cell are filled or nonexistent in the case of border cells 6 006 Intro to Algorithms Recitation 19 April 15 2011 From here we can now systematically fill out our matrix For each cell compare the cost of appending a delete to the above cell appending an insert to the left cell and appending a copy to the above left cell ONLY if the characters are the same Take the minimum of those costs and append the corresponding operation We get something like this Note the order of the cells that we re filling in top to down from left to right This order ensures that every time we reach an empty cell the cells above left and above left will be filled and consequently the empty cell can be filled in as well There are several orders that work in this case left to right from top to down diagonally etc Also note that we can only make a copy operation when we re in a cell whose row and column are the same in this case the copy operation was in an A row and an A column The finished matrix looks like this 6 006 Intro to Algorithms Recitation 19 April 15 2011 The optimal solution for editing MAKER to DATE is found in the lower right cell and has a cost of 54 We can trace the exact operations in this sequence by starting at a cell and then backtracing all the way to the first cell We move up on Insert left on Delete and up left on Copy The running time of this algorithm is O n2 where n is the length of the strings We need to construct a n n size matrix and filling …
View Full Document
Unlocking...