CSC B70 Assignment 4

Due: Wednesday April 8 at 10:00 am.
Worth: 10%.


Problem 1
=========

The ``string cutting'' problem is to break a string 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 
-------------+-------------------+----------+-------
abcdefghij   |  cut   abcdefghij |  abc     |  10 
	     |  after c          |  defghij | 
-------------+-------------------+----------+-------
abc  defghij |  cut   defghij    |  abc  de |   7
	     |  after e          |  fghij   |  


Part A. 
=======

Solve the string cutting problem in C using dynamic programming. 
Your program should receive as input a string S, its length n, 
and an array of m length for the fragments. You should check that 
such a cutting is possible; send an error message otherwise. 
The output must be the minimum cost cutting sequence and the 
fragments that produce such an optimal cut.



Part B. 
=======

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


fragment  |  f_1  f_2  f_3  f_4  f_5  f_6 
----------+--------------------------------
length    |   1    1    5    3    2    2
----------+--------------------------------
letters   |   p    e  rsuas ive   ne  ss 


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}. Note 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''.

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



What to hand in.
================

Submit your C program for part A. Test it with the example 
of part B and with another example of your choice. Use the
submit command:

    % submit -N a4 cscb70s *

Hand in copy of your source code, the output from the two 
tests and your manual solution of part B. For part B, 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 whose lengths w_1, ... , w_7 are:


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


Assume that each line can contain 12 characters.


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

COVER SHEET FOR ASSIGNMENT 4


   Account name:

   Surname:

   Given Name(s):

   Student Number:

   Tutorial:


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

     Correctness                                 / 15 
     Output                                      / 5 
     Manual computations                         / 10 
     Program style, including comments           / 5


Problem 2

     Correctness                                 / 10 
     Comments                                    / 5 

Total                                            / 50