CSE 417 Assignment #2
Winter 2002

Due: Friday, January 25, 2002.

Reading:

Chapters 1 and 3. Chapter 2 should be review of CSE 373 material; you should skim it, reading unfamiliar parts more carefully. I expect to start Chapter 4 the week of 1/28.

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 72 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. Skiena's text page 78, Problem 3-6. Assume d1=1.

  5. (Extra Credit) Skiena's text pages 78-79, Problem 3-7. Again assume d1=1.