6.006 Intro to Algorithms Recitation 19 April 15, 2011Dynamic Programming: 1D OptimizationFibonacci SequenceTo efficiently calculate F [x], the xth element of the Fibonacci sequence, we can construct the arrayF from left to right (or “bottom up”). We start with F [0] = 1 and F [1] = 1 and iteratively calculatethe next number in the sequence using F [i] = F [i − 1] + F [i − 2] until we get F [x].Crazy 8’sIn the game Crazy 8’s, we want to find the longest subsequence of cards where consecutive cardsmust have the same value, same suit, or contains at least one eight. If the cards are stored in arrayC, we want to keep an auxiliary score array S where S[i] represents the length of the longestsubsequence 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 carditself and has a length of 1. We iteratively calculate the next score S[i] by scanning all previousscores and set S[i] to be S[k] + 1 where S[k] represents the length of the longest subsequence thatcard C[i] can be appended to.Dynamic Programming: 2D OptimizationEdit DistanceIn the edit distance problem, we have two strings X and Y . Our goal is to find out the minimumcost of transforming string X into string Y using a set of editing operations. We will iterate throughthe 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 output2. Delete the current character of the source and go onto the next character3. Insert a new character into the output stringFor example, let’s look at how we can edit MAKER to DATE6.006 Intro to Algorithms Recitation 19 April 15, 2011Using a sequence of [Insert(D), Delete, Copy, Insert(T), Delete, Copy, Delete], we were ableto edit MAKER into DATE. Note that this sequence is not unique. We could have swapped thefirst Insert(D) and Delete with each other without changing the final result. A naive edit couldhave been deleting all of MAKER and then inserting all of DATE, making no copies in the editsequence.There are many ways we can edit X to Y , but we want to find which edit sequence has min-imum cost. Each of the editing operations has some cost associated to it. For instance, we canassign costs as such:• Copy - Cost 5• Delete - Cost 10• Insert - Cost 7Our editing sequence [Insert(D), Delete, Copy, Insert(T), Delete, Copy, Delete] has a totalcost of 54 according to our cost model. If we chose to delete all of MAKER and then insert all ofDATE, 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 bestoverall?Let X0and Y0be the strings X and Y without their last character (e.g. if X is DATE, X0isDAT). An important observation to make is that we can construct an editing sequence from X toY in at most three ways:1. Take the minimum cost editing sequence of X0to Y0. If the next characters are equal, thenwe can append a Copy to that editing sequence6.006 Intro to Algorithms Recitation 19 April 15, 20112. Take the minimum cost editing sequence of X to Y0and append an Insert(last character ofY ) to that editing sequence3. Take the minimum cost editing sequence of X0to Y and append a Delete to that editingsequenceHere, we are using optimal solutions to smaller problems to help us construct an optimal so-lution to the total problem. Using proof by contradiction, we can prove that the minimum costediting sequence of X to Y must be one of the three sequences resulting above. To figure outwhich sequence is the best, simply take the minimum of the three sequences’ costs and that will bethe minimum editing sequence for X to Y .Like the Fibonacci and Crazy 8’s examples, we want to construct the minimum editing se-quence from bottom up. We do NOT want to start at figuring out the sequence from X to Y andrecursively solving for the sequences from X0to Y0, X to Y0, and X0to Y . Instead, we can startwith 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 correspondsto the cost of a minimum cost editing sequence to transform a prefix of X to a prefix of Y . In theexample 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 trans-formation. Note that for each cell, based on our important observation above, we can constructan optimal editing sequence only if the above cell, left cell, and above left cell are filled (or non-existent in the case of border cells).6.006 Intro to Algorithms Recitation 19 April 15, 2011From here, we can now systematically fill out our matrix. For each cell, compare the cost ofappending a delete to the above cell, appending an insert to the left cell, and appending a copyto the above-left cell ONLY if the characters are the same. Take the minimum of those costs andappend 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 orderensures that every time we reach an empty cell, the cells above, left, and above-left will be filledand consequently the empty cell can be filled in as well. There are several orders that work in thiscase (left to right from top to down, diagonally, etc.) Also, note that we can only make a copyoperation when we’re in a cell whose row and column are the same (in this case the copy operationwas in an A row and an A column). The finished matrix looks like this:6.006 Intro to Algorithms Recitation 19 April 15, 2011The optimal solution for editing MAKER to DATE is found in the lower right cell and hasa cost of 54. We can trace the exact operations in this sequence by starting at a cell and thenbacktracing 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 toconstruct a n × n size matrix and filling each cell in the matrix takes constant time (assuming theprevious cells are already filled). Once we fill out each cell in the matrix, we have a solution to theedit distance problem.All Pairs Shortest Path: Floyd-WarshallBellman-Ford and Dijkstra’s algorithms both
View Full Document
Unlocking...