CSC270 Data Structures and Techniques, Spring 1998

Assignment 4: Dynamic programming

Due Wednesday April 8 at start of class


Problem 1
=========

The ``string cutting'' problem is to break a character into several
strings. The only allowable operation is to cut a string into two
substrings. For a string of length n, a single cut takes n time units
since it makes a copy of the string before cutting it. The running
time does NOT depend upon the position of the cut.

Consider a string ``abcdefghij''. Here are costs for two cuts which
occur one after the other:

	Strings      |  Action           |  Result  |  Cost 
	-------------+-------------------+----------+-------
Cut 1   abcdefghij   |  cut   abcdefghij |  abc     |  10 
		     |  after c          |  defghij | 
	-------------+-------------------+----------+-------
Cut 2   abc  defghij |  cut   defghij    |  abc  de |   7
		     |  after e          |  fghij   |  

Suppose we want to cut the string ``abcdefghij'' into six fragments:
f_1, f_2, f_3, f_4, f_5, f_6. The fragments have the following
lengths:


fragment  |  f_1  f_2  f_3  f_4  f_5  f_6 
----------+--------------------------------
length    |   1    1    3    1    2    2
----------+--------------------------------
letters   |   a    b   cde   f    gh   ij

You will use dynamic programming (by hand) to find the sequence of
cuts that has minimal total cost.  For that, you will fill in two
tables with your intermediate results.

In the first table, the element in column c, row r contains the
minimum total cost of cutting the subsequence f_c, f_{c+1}, ... ,
f_{c+r}.  Make your table so that row numbers increase upward.

In the second table, the element in column c, row r contains the index
of the subsequence f_c, f_{c+1}, ... , f_{c+r} after which the first
cut should be done.  For example, if the first cut of f_3 f_4 f_5
should be made after f_4, then the column 3, row 2 entry in the second
table will contain a ``4''.  Again, make your table so that row
numbers increase upward.

For the optimal sequence of cuts, give its cost and the cutting order.

Hand in the two tables, the optimal cost, and the optimal cutting
order.  Show all your work, including all the values that you tested
in determining each table element.


Problem 2
=========

Consider the problem of neatly printing a paragraph of text on a
printer with fixed-width fonts.  The input text is a sequence of n
words containing w_1, w_2, ... , w_n characters, respectively.  Each
line on the printer can hold up to M characters.  If a printed line
contains words i through j, then the number of blanks left at the end
of the line (given that there is one blank between each pair of words)
is

      M + (i - j) - (w_i + w_{i+1} + ... + w_j).

We want to minimize the sum, over all lines except the last, of the
cubes of the number of blanks at the end of each line.  For instance,
if there are k lines with b_1, b_2, ... , b_k blanks at the end,
respectively, then we want to minimize (b_1)^3 + (b_2)^3 + ... +
(b_{k-1})^3.

Using dynamic programming, compute the arrangement of words on lines
that minimizes the sum of the cubes.  You have a paragraph with words
w_1, ... w_7, with lengths

  word    | w_1  w_2  w_3  w_4  w_5  w_6  w_7
  --------+----------------------------------
  length  |  6    7    2    3    5    5    9

Assume that each line can contain 13 characters.

Hand in the two tables, the minimum sum, and the optimal arrangement
of words on lines.  Show all your work, including all the values that
you tested in determining each table element.


------------------------------------------------------------------------

COVER SHEET FOR ASSIGNMENT 4


    CDF account name:

    Surname:

    Given Name(s):

    Student Number:

    TA's name:

    Tutorial location:

 
I declare that this assignment is my own work and is submitted in
accordance with the University of Toronto Code of Behavior on Academic
Matters, the Code of Student Conduct, and the guidelines for avoiding
plagiarism described in the course syllabus.
 
I discussed this assignment with the following people:





 
Signature

------------------------------------------------------------------------


GRADING
 
Problem 1                                              / 15

Problem 2                                              / 15
 
                                                ----------- 

Total                                                  / 30