Algorithms and Data, Summer 1 Problem Set 4
Due Wednesday June 15, 9PM
For this problem set, turn in PS4.pdf, Amortized.java, and Edit.java, all in the top level of a zipped folder (no “src” folders and such, please). If Edit.java requires additional java code, turn that in as well (again, in the top level). Remember to write solutions and pseudocode in your own words for Part I and II, and include your partner’s name on all files.
Part I – Algorithm Design: Dynamic Programming and Network Flow
1. Suppose you run a business where you need to ship a large number of goods to customers, and there are three different companies, A, B, and, C, that can do this for you. The prices of using these companies are different on a week-to-week basis; one of the companies charges more around the holidays, another charges more during the summer, and so on. So each company has varying cost Ai, Bi, or Ci that depends on the week number i. These companies all offer their best rates only if you enter into exclusive contracts with them that you can’t get out of without paying a penalty P (for simplicity, we’ll assume this is the same across the companies). If penalty P is high, it is in your best interest to stick with one company the whole time. If the penalty P is low, it is in your interests to continually switch to the cheapest provider, week-by- week. But if the penalty is right in the middle, then sometimes it won’t make sense to switch providers just for a week or two.
a.) Give an example where the greedy approach of choosing the minimal cost decision week- by-week fails to be optimal. (Specify the costs involved.)
b.) Give commented pseudocode for a dynamic programming algorithm that will take the weekly costs Ai, Bi, and Ci (all of which vary by week) and the penalty P, and return a schedule of which company to use for all 52 weeks of the year. (Assume you can start with any company without penalty. Don’t worry about memory efficiency; in fact, you may find it useful for the brevity of your pseudocode to copy the costs into a 2D array.)
c.) Analyze the worst-case running time of the generalization of your algorithm that works for a W week schedule and S companies.
2. In class, we discussed the Viterbi algorithm, which is a way of turning audio data into the most likely sequence of phonemes that a person was trying to say. After this conversion to phonemes, we still would not necessarily know where the boundaries between different words are. When people speak quickly, words can run together, and it may be difficult for an automated algorithm to determine what words are being said.
For our purposes, we’ll treat phonemes just like letters of the alphabet. Given a sequence of such letters without obvious spaces, we are looking for a grouping into words that is most likely — segmenting “amanaplanPanama” into “a/man/a/plan/Panama” for example. Assume that we can call a function wordQuality(W) that, given a substring of letters, gives a higher score to real words (“man”) than to fake ones (“napl”) and higher scores to common words (“plan”) than uncommon ones (“anam”, a language of Papua New Guinea).
a.) Give pseudocode for a dynamic programming algorithm that, given a string of letters, returns a list of strings that concatenate to form the original string and have the highest possible sum of
Σi wordQuality(Wi). (You need not give pseudocode for the quality functions.)
b.) Give the recurrence that is implicit in your dynamic programming approach, and explain why it is correct. How do you know you are analyzing all the relevant segmentations?
c.) Analyze the worst-case running time of your algorithm, assuming wordQuality() works in constant time.
3. Suppose there is a natural disaster, and N injured people are scattered around a small island nation with H hospitals. Each hospital has reported a maximum number hi of injured people it can successfully take in. Each person can only reasonably go to some subset of the hospitals because the other hospitals are too far away.
a.) Describe how to set up the graph that would allow this problem to be solved by max flow, and explain how the results of the max flow algorithm could be interpreted to solve our problem.
b.) Give the running time in terms of the number of injured people N and number of hospitals H if we use Ford-Fulkerson versus Push-Relabel. (Assume it may be possible for every injured person to go to every hospital.) Which running time seems most reasonable here?
4. An army encampment sends out a group of soldiers out every day to patrol the area around the base. This patrol group is always gone for some time, so someone in the group always needs to carry a backpack of supplies. Nobody wants to be this person carrying the supplies, but somebody has to do it. If the group of people headed out every day were always the same, they could all just round-robin the duty. But some people go out on patrol quite a bit, and others don’t go out much at all.
The soldiers going out on patrol convince their superiors that the most fair thing to do would be to pick someone at random on each outing and have that person carry the pack. But the army hates randomness and loves hiring contractor programmers. Design an efficient deterministic flow-based algorithm that, given the lists of people going out on days 1 … D, returns a schedule of who will carry the pack on each day, with no person receiving the pack more than the ceiling of the expected number of times they would have received the pack with a random allocation. (Hint: Recall linearity of expectation.)
Part II – Amortized Analysis
1. Suppose I have a doubly-linked list that I keep sorted in the following manner. If I push a new element onto the front of the list that is smaller than or equal to the previous head of the list, the new element simply becomes the new head of the list, pointing to the old head. But if the new element is greater than the previous head of the list, I iterate through the list dropping elements from the list until the next element is greater than or equal to my pushed element.
For example, Push(2, [3, 4, 5]) results in [2, 3, 4, 5], but Push (4, [3, 4, 5]) results in [4, 4, 5].
Analyze the big-Θ worst-case and amortized costs of this Push method in terms of the number of elements in the list, N. For the amortized cost, use the potential method.
2. Let’s see what “amortized constant time” means in practice. For the following problem, you and your partner can turn in identical graphs, but your analysis should be in your own words.
In a Java file called Amortized.java, create an ArrayList
a.) Plot the amount of time taken for each call as a function of N. You need not plot all 3 million values, but you should try to plot all the “spikes” plus some values evenly spaced apart between spikes. What is going on during the spikes? Is there a pattern to their increasing or decreasing? If any spikes break that pattern, why do you think that happened?
b.) Calculate the total time spent for N add() calls over time, and plot the average time per call for N calls against N. (You can plot every kth point for some k if you wish.) Does the empirical roughly result match what theory would predict? What explains the shape of the graph you see?
Part III – Dynamic Programming and Memoization
Write a program Edit.java which takes two strings as command-line arguments and displays to System.out the sequence of edits that are necessary to transform the first string into the second, with one intermediate string per line. For example,
java Edit dungeon dragon
should display something like
dungeon drngeon drageon dragon
Use a gap penalty of 1 and a change cost of 0.5 for different characters. Identical characters have a change cost of 0; moreover, you should not include the repeated strings that these “no- ops” produce in your final list of strings.
There is a catch to this programming assignment: do not use the iterative version of the algorithm shown in class. Instead, make your algorithm recursive, and have it memoize the best moves for smaller versions of the problem. The top level of the algorithm should not consist of nested for loops, but of a recursive call that asks for solutions to subproblems. (This is not particularly a better way to do things — this is just to help you see the relationship between these approaches.) You should still use the basic implicit recursion that the iterative version uses to efficiently get an optimal solution (an optimal distance consists of a change, or a deletion, or an insertion, on top of another optimal distance…)
Your recursive function should return a data structure that includes both the edit distance and some representation of the optimal edit sequence. Use static 2D arrays in your Edit class to hold the results of memoized calls. (No, you can’t use ArrayLists of ArrayLists. You know how big the strings are, and that you need to fill the whole subproblem table, so there is no sense in using a growable array when you can allocate the memory all at once.)
You do not need to worry about using linear space. Use as much space as you need.
To aid us in testing, please name your file Edit.java, name your class Edit, and create a method that returns the final sequence of strings with the following name and signature:
List
(Both ArrayLists and LinkedLists count as Lists, but use the List
Please submit PS4.pdf, Amortized.java, and Edit.java in a zipped folder with no other folders and no other files besides any java files you wrote as helpers to Edit.java.