Ilya Feldshteyn
Csci5241
Prof. Sturtivant
2/08/08
ASSIGNMENT 1
15.4-2
I want to mention that reconstructing an LCS in only O(M+N) time will result in a single outpu string. From experience, large and complex input strings result in multiple LCS which have to be computed recursively. This is due to the fact that reading back the LCS will result in either going left, up, or diagonally until the top most square in the matrix (composed of two-dimensional arrays) is reached.
The initial set-up. The matrix table is built from the lengths of two strings: one of length X and one of length Y. The table has X and Y indexes with a value of the LCS string length at the X-Y intersections. Each index points to a character in the words from which an LCS is extracted. So if you have a 5 by 6 matrix the 5-letter string would be the vertical index and the 6 letter string would be the horizontal. And at the intersection of the X and Y indexes you could get a character from one of the two strings. In our case we will use the vertical string, although both can be used in this algorithm. The matrix itself is size (X+1)(Y+1) due to an extra row and column needed to compute the algorithm. This does not affect the running time.
Here is how I propose that a solution can be obtained. First thing we do is let the program recurse through the formula (on page 352) until the table is filled up with values. Then we look at the last element in the bottom-right end of the matrix. At this point there is an option in the algorithm where you can look at the element above and the element to the left of the current one (both are correct).
For this example let’s look at the Left elements first. If the Left element is the same in value as your current one, then you would move to the element on the Left in the matrix and repeat the procedure. If the element on the Left is not the same as your current one, the algorithm would look at the element above. If the element above is the same, then you would move up in the matrix and repeat the process. You would continue checking Left and then Upper elements until both of them do not equal your current value. In this case you would print (or store in an array) the letter at the current index of the vertical word-string.
So if the current index is [5,6] you would print out the 5th letter of the vertical word, whatever it may be. Once the character is printed, the algorithm now jumps Left AND Up, that is, in a diagonal manner in the matrix and repeats the procedure. Note the value that is diagonal from the current one would be one less than the current value. This value corresponds to the LCS length up to that point.
The algorithm would continue following this pattern, checking Left and Upper values until it cannot move in any of these directions. It would print or store the letter, move diagonally to the Upper-Left and continue. Eventually it will reach the top-left corner of the matrix and halt. The letters printed (or stored) will now contain the LCS in reverse. This is because the algorithm reads the solution from smallest subproblems (i.e. the end of both strings).
Now lets analyze the complexity of this algorithm. At every juncture the algorithm looks at the Left and Upper elements until it reaches the top-left of the matrix. It doesn't need check the diagonal element (the algorithm heads there automatically). This algorithm is analogous to an O(X+Y) running time since the matrix has X length and Y height. The use of the B table simplifies this problem because it tells exactly which path to take during LCS construction. While the arrows planted in the B table speed up the algorithm the table itself takes up storage space. In the end (like most algorithms) this is a battle between speed and storage, and depending on the requirements each can be an issue with long input strings.
15.4-5
This problem is really a differently-worded LCS problem. What you really want to know is what the longest amount of increasing characters is in a given string. To learn this, one needs a key of all the increasing letters in the string. This key is simply a sort of the original string. The algorithm would refer to this key to ensure that the current substring is monotonically increasing. To do this one needs a sorted character string to compare with the original word. So the first step of this algorithm is to create a secondary string with exactly the same amount of letters but only in sorted order.
So given X-lengthed strings we would receive Y (X in sorted order). Once both strings are computed, they are then plugged into the LCS algorithm on page 352. The result is a longest monotonically increasing substring. I am attaching a link to an LCS program I wrote that takes an input a textfile with 2 lines. The first line is the first string and the second the second string. The program will output a file titled " textfile:answers.txt " with all the LCS enumerated (my program finds all the LCS it finds). To make it work with the monotonically increasing substring (MIS) just sort the second line and look at the output. The command example is.
lcs textfile.txt
and the output will be stored in a file
textfile:answers.txt
In regards to complexity, the algorithm is going to be O(N+K) if we use radix sort to sort the input string and O(N^2) the normal complexity of an LCS algorithm. The total will be O(N+K+N^2) = O(N^2). This is slightly worse than a normal LCS algorithm and would be substantially worse if a poor sort is chosen (such as Bubble, Insertion etc...). It is imperative that the sort is run in near-constant time (ie: use non-comparison sorting) to minimize the overall complexity of the MIS algorithm.
15-2:
(Note: I am under assumption that words 1-N are in a specific order, so if I choose words 1-5 to be on line 1, then line 2 will have words 6 through 10, line 3 words 11 through 19 etc... . If this is not the case I am afraid the complexity will be too big to be viable in real life...well at least with older computers.)
Fortunately the problem gives us a way to calculate the cost of each single line given by M - j + i - sum(words i through j where i <= j). However, (and I almost missed this fact) each blank space gives a penalty of a cube of the number. This is similar to the Least Squares problem, where you want to minimize certain distances to an approximation by giving a penalty of a square of that distance. So the goal here is to minimize the number of the blank spaces, not on a single line, but over the course of the entire paragraph. That is, we sum up the blanks on line 1 and cube them, blanks on line 2 and cube them and up until the last line which we ignore. So we need a function, lets call it sum_line(start word, end word) which would return the numerical value of the white spaces cubed.
One way to solve this is by trying to fit words P through Q where sum_line(P,Q) returns a number less than M and greater than 0 and never P,Q+1 if sum_line(P,Q+1) returns a number a number less than M and less than 0. That is, the extra word on the end went over the line and has characters hanging off the edge which results in failure. This would mean that there are no white spaces. Then I would start a new line with Q+1 and continue until the end. Unfortunately (for me), this is just a greedy solution to the problem and not a dynamic programming solution. So this is not the way I will go to solve the question.
Now every DPA algorithm needs some kind of table matrix to keep track of previously-solved subproblems. In our case, we want to minimize the amount of white spaces by checking sum_line(i,j) for each index i through j. Our initial value for i is 1 and j to be n. So our matrix will be n by n and upper triangular because we never calculate the cost of words that do not follow each other (ie: Cannot do cost of sum_line(j,i)). The vertical part of the matrix would be the line count while the horizontal would mean words 1 through N per line. So an intersection of [7,3] would be the cost of words 3 through 7 on a single line.
Obviously, at a certain point in the rows the sum_line(i,j) will return negative results which we do not want. I should also mention that there is no such thing as sum_line(0) because that is the same as putting no words on a line. In this case I'll return some symbol like "-1" stating that this function does not help in calculating the total cost of the line and will be ignored by the algorithm.
At first I thought I would start filling out this table with the diagonal which would be value of sum_line(i,i) from 1 to N. This is the same as putting a single word on each line. However, I realized that every single word needs the minimum cost of previous words in the list. So word i+1 would need the minimum cost of i and the current cost. Also this cost can never go below 0 because that means we would have characters hanging off the end of the line.
Because we need to access the minimum values of previous words per line we have to recurse through all the possibilities starting from the end (this is the BOTTOM RIGHT corner of the matrix). This is similar to the LCS problem which starts from the end and builds up the output backwards. So if we are at index Current we would then have to see how many words we can fit without this Current word plus the Current's cost. There are a total of Current-1 words before the Current word and every single one has to be tested to see which words go on each line.
We then have a function that is called check_previous(start) + sum_line(start, Current). The 'start' location of the sum_line() function could be ANY word before the Current word. So we calculate the sum_line() 1 through Current in the matrix. So if you are at check_previous(5) you would look at check_previous(1) + sum_line() costs 1 through 5, check_previous(2) + sum_line(2,5) ... check_previous(4) + sum_line(4,5). This part is similar to the matrix parenthesization where you check 1 through current in a specific order (you do not jump over matrixes and you do not jump over words in this problem).
Now if this was not a DPA problem we would have a lot of repeat calculations to do. Fortunately, on a closer look we can see that due to overlapping problems we can reuse previous solutions. So in our example of check_previous(5) we have to calculate check_previous(4) and check_previous(3) both of which have the check_previous(2) function. We do not have to calculate sum_line(1,2) both times. After the sum_line(1,2) is calculated once, the second time is simply an O(1) dereferencing operation of the two-dimensional array. So after the upper triangular part of matrix is filled in with sum_line() values the lookup becomes O(1) constant time!
Going back to our location at Current we have calculated check_previous(1) plus sum_line(1, Current), check_previous(2) plus sum_line(2, Current) ... check_previous(Current-1) plus sum_line(Current-1, Current). (As a side note it is obvious that we would stop calculating check_previous at (Current-1) because if we went to check_previous(Current) again, we would end up in an infinite loop.) After the check_previous() calculation we now choose the lowest sum of all words up to the Current point. This is accomplished with a function like Lowest() that has to be applied to every check_previous() and sum_line() output. The function would check the integer values of the matrix and see which is really the smallest cost.
After the Lowest(check_previous(start) + sum_line(start,Current) ... check_previous(start+1) + sum_line(Current-1,Current)) figures out the lowest value on that line you would have a start+n and Current values that fit best on a line. This 'n' could be any number between start and Current. So Lowest would return a range from start+n to Current which would show which is the Lowest cost per line. If n is 5 and Current is 10 then words 6 (because Start begins with 1 and Start + n = 6) through 10 will appear on the line. This range needs to be recorded somehow. You could either print it out like " Line 6: beginword: 6 endword: 10 " or (probably a better idea) store it in an array. So at index 6, the value would be 10 signifying that the line goes from words 6 through 10.
It is important to note that as the check_previous() command builds off the previous subproblems and the results of 'beginword' and 'endword' may change as smaller Lowest() values are found. So not until the algorithm is complete will the actual 'beginword' and 'endword' values per line are calculated and throughout the algorithm runtime they will change frequently.
Once the algorithm is finished, you would go to Line 1: in the printout (or index 1 of the array) and print out words 1 through the endword. You would then begin a new line and print out words from Line (1+endword) or the [*endword+1] in the array. When you hit the endword that equals the total number of words (N) then you know you are on the last line and have finished printing out all the words requried. At this point the algorithm would end the printout and halt.
The running time would be equal to the calculation of all the sum_line() of the upper-triangular matrix, finding Lowest() value of the check_previous() functions and printing(writing) and reading(dereferencing) the 'beginword' and 'endword' values. To calculate the sum_line() function it would take 3 (- + -) operations + (# of words) * avg(word length). According to wikipedia http://en.wikipedia.org/wiki/Wikipedia:Size_comparisons (I couldn't find a better source) the average wordlength is 5. So the total ops for sum_line() is (3+5*N). The sum_line() function is performed Upper-Triangular times of an N by N matrix. Upper-triangular means (N*N)/2 + N/2(and the single N/2 references the diagonal). So now the calculation is at (3+5*N)(3+5*N)/2 + (3+5*N)/2 which becomes O((N/2)*N) runtime. Finally we add the cost of printing (or writing to an array) which is size N (because you can never have more lines than words) which brings the final total to O((N/2)*N) +O(N) which still is O((N/2)*N). The final runtime is O(NlogN) which (if you ignore some constants and lower level complexities) is like Quicksort!
The space required would be an N by N matrix (although it can be theoretically simplified because we do not use the lower-triangular part of it) made from a two-dimensional array. We also could use an N-sized array to store the ranges with 'beginword' and 'endword' locations for each line. So the total space becomes O(N^2 + N) which isn't too bad.