image University of Washington Computer Science & Engineering
 CSE 417, Wi '05: Assignment #2, Due: Monday, January 24, 2005
  CSE Home   About Us    Search    Contact Info 

Reading:

Chapters 1 and 3. Chapter 2 should be review of CSE 373 material; you should skim it, reading unfamiliar parts more carefully.

Problems:

  1. 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?

  2. Here's a variation on the List Partition problem (section 3.1.2). Instead of looking at the sum of the sj in each segment of the partition, and trying to minimize the largest such sum, suppose we want to look at the max sj 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 big-O sense.)

  3. 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?

  4. Suppose you are given a sequence (s1, r1), (s2, r2), ..., (sn, rn) of pairs of positive integers. Think or the ri paired with each si as a "reward" for choosing si. 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 sij so that si1 ≤ si2 ≤ ... ≤ sik and i1 < i2 < ... < ik. 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 ri1 + ri2 + ... + rik subject to the constraint above that the corresponding si'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 big-O sense.)

    Simulate execution of your algorithm on the following input:

    si: 90 33 41 70 66 25 13 30 68 31
    ri: 10 10 20 10 10 30 20 30 30 40
    What is the best increasing subsequence?

  5. Skiena's text page 78, Problem 3-6. Assume d1=1.

  6. (Extra Credit) Skiena's text pages 78-79, Problem 3-7. Again assume d1=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).

CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to cse417-webmaster@cs.washington.edu]