Due 9:50AM Wednesday, Feb 18. Hand in the program via HSP or the hand-in folder. Hand in the rest on paper.
Consider the minimum edit distance program min_edit.py that I demonstrated in class. Once the full chart is built, we read off the minimum edit distance from the chart's bottom right entry. For many purposes, this is all we need to know. But what if we want to know not just the distance between two words, but also the sequence of editing operations that will transform the first word to the second? Can the completed chart give us this information?
The answer is yes, and it is your job to modify
min_edit.py to enable us to see the
minimum edit distance computation in action. Specifically, you should
implement the methods printTransformation and
printChartWithPath that are described in the
MinEditDistanceChart class.
Consider this slightly edited version of the SELECT algorithm from page 190 of Introduction to Algorithms by Cormen, Leiserson, and Rivest. The goal of this algorithm is to find the kth-smallest element of an n-element input array.
Step 1. Divide the n elements of the input array into floor(n/5) groups of 5 elements each and at most one group made up of the remaining n mod 5 elements.
Step 2. Find the median of each of the ceiling(n/5) groups by insertion sorting the elements of each group and taking its middle element. (If the group has an even number of elements, take the larger of the two medians.
Step 3. Use SELECT recursively to find the median x of the medians.
Step 4. Partition the array into the set L of items that are less than x, and the set G of items that are greater than x.
Step 5. If |L| = k - 1, return x. If |L| < k - 1, use SELECT recursively to return the kth-smallest item of L. Otherwise, use SELECT recursively to return the (k - |L| - 1)th-smallest item of G.
As we discussed in class (and will finish discussing on Monday), the recurrence relation T(n) ≤ T(ceiling(n/5)) + T(7n/10 + 6) + O(n) leads us to a linear running time for this algorithm.
Here's the question: why did we have to divide the array into groups of five, when groups of three seem like they would work similarly but slightly more simply? To answer this question, you should construct the recurrence relation we would get from the groups-of-3 version of this algorithm, and show why the resulting T(n) fails to be O(n).
Knapsacks.
Show the steps of the knapsack algorithm developed in Section 6.4 of your textbook for the following items, assuming a knapsack capacity of 7.
| object | 1 | 2 | 3 | 4 | 5 |
| value | 4 | 7 | 3 | 5 | 4 |
| weight | 5 | 3 | 2 | 2 | 1 |
For many algorithms, it is easy to describe both the best case arrangement of input data, and the worst case. For example, for insertion sort, "already in order" and "in reverse order" describe the best and worst cases, respectively.
Describe the best and worst cases for the input for the knapsack algorithm of section 6.4. Include a discussion of the running-time complexity of the best case.