
CSE Home  About Us  Search  Contact Info 
Simulate the execution of the List Partition algorithm (section 3.1.2) on the input
90 30 40 70 60 20 10 30.Show both the M and D matrices. What is the best partition of that list into 3 segments? Into 2 segments?
Here's a variation on the List Partition problem (section 3.1.2). Instead of looking at the sum of the s_{j} in each segment of the partition, and trying to minimize the largest such sum, suppose we want to look at the max s_{j} in each segment of the partition, and that we want to minimize the sum of these maxima. To avoid the degenerate solution that places all objects into one segment of the partition, suppose you are also given an integer p which is the maximum number of objects allowed in any one segment of the partition. (Note that no solution is possible if kp < n, where k is the maximum number of segments allowed and n is the number of objects.) Give an algorithm solving this problem, argue that it is correct, and analyze its running time. (Faster algorithms are better than slow ones, of course, so try to make yours fast, at least in the bigO sense.)
Simulate the execution of the Longest Increasing Subsequence algorithm (Section 3.1.4) on the sequence
90 33 41 70 66 25 13 30 68 31.(Give a table as shown on page 63. Note that the predecessor row indicates the position of the predecessor, not its value.) What is the longest increasing subsequence ending with 66? 31? Overall?
Suppose you are given a sequence (s_{1}, r_{1}), (s_{2}, r_{2}), ..., (s_{n}, r_{n}) of pairs of positive integers. Think or the r_{i} paired with each s_{i} as a "reward" for choosing s_{i}. As in the Longest Increasing Subsequence problem, your goal is to choose a subsequence of the s's that increases from left to right, i.e., choose s_{ij} so that s_{i1} ≤ s_{i2} ≤ ... ≤ s_{ik} and i_{1} < i_{2} < ... < i_{k}. In the LIS problem, the goal was to make the subsequence as long as possible, i.e. to maximize k. In this problem, called the "Best Increasing Subsequence" problem, your goal is to maximize the total reward for the selected elements. In other words, maximize r_{i1} + r_{i2} + ... + r_{ik} subject to the constraint above that the corresponding s_{i}'s are increasing. [The LIS problem is the special case of this problem in which all the rewards are equal.]
Again, give an algorithm solving this problem, argue that it is correct, and analyze its running time. (Faster algorithms are better than slow ones, of course, so try to make yours fast, at least in the bigO sense.)
Simulate execution of your algorithm on the following input:
s_{i}: 90 33 41 70 66 25 13 30 68 31What is the best increasing subsequence?
r_{i}: 10 10 20 10 10 30 20 30 30 40
Skiena's text page 78, Problem 36. Assume d_{1}=1.
(Extra Credit) Skiena's text pages 7879, Problem 37. Again assume d_{1}=1. The order of coins in a solution is ignored; e.g. if you had 1 and 2 cent coins, there are two different way to give 3 cents change: 1+1+1 and 1+2 (which is the same as 2+1).
Computer Science & Engineering University of Washington Box 352350 Seattle, WA 981952350 (206) 5431695 voice, (206) 5432969 FAX [comments to cse417webmaster@cs.washington.edu] 