1

First of all, this is not homework, so please don't tag it as homewrok

I did not understand this problem. Can anybody explain it to me? It is not the english that I do not understand, but rather the general gist of the problem.

alt text

7
  • Have you considered a descriptive title for your question?
    – Pieter
    Jun 5, 2010 at 7:09
  • 1
    Do you have a specific question about this problem? Jun 5, 2010 at 7:12
  • 7
    If it is not "homewrok", then what is it? Jun 5, 2010 at 7:17
  • question just question which i did not understand
    – user466534
    Jun 5, 2010 at 7:21
  • Its originally from a book "Introduction to algorithms By Thomas H. Cormen" and copied by many lazy teachers.
    – zaf
    Jun 5, 2010 at 7:24

2 Answers 2

5

My method for solving this problem ?...Sure babe....Here ya go..served up on a silver platter.

[1] Google search for say: Consider the problem of neatly printing a paragraph on a printer

[2] Pick say ~10 sites that are not obvious chaff.

[3] Have a quick look at the source code on the site...pick some code that is well structured and has plenty of comments.

[4] Pop it into visual studio..write some quciky code that excises the algorithm.

[5] Follow the flow of the code and compare it with the stated problem.

[6] Check a few of the results by hand. If they fail goto step 3.

[7] Run through the code until you understand how it works.

And there you go..How learn just about anything in 7 pain free steps.

Drinks all around...

Can I get you another cocktail ?

It's you lucky day... I'm in a good mood...So, here is a little pseudo code for you....from the first Google hit...even has line numbers so you can ask questions about specific lines...glory days...grrrr.

Lets assume that for all k s where 1 <= k <= n lk < M. PRINT_NEATLY is a bottom-up dynamic-proramming algorithm for the above recursive equation.
Lets create another array lineend[n] to record the end of line word number.


PRINT_NEATLY(n, M, l)
1   for i  <-- n to 1
2       p <-- i
3       CharsLeft <-- M - lp
4       while (CharsLeft - lp+1 -1) > 0 and p < n
5           do  CharsLeft <-- CharsLeft - lp+1 - 1
6                   p <-- p + 1
7       if p = n
8           then c[i] <-- 0
9                   lineend[i] <-- n
10          else
11              c[i] <-- a big number, probably the Maximum nuber for this type.
12              sum_lk <-- 0
13              for j <-- i to p
14                  sum_lk <-- sum_lk + lj 
15                  cost <-- ( M -j + i - sum_lk )3 + c[j+1]
16                   if  cost < c[i]
17                       then c[i] <-- cost
18                               lineend[i] <-- j 

19    // Print paragraph
20    start <-- 1
21    while start <= n
22        do
23            for word <-- start to lineend[start]
24                print  ln
25            print newline
26            start <-- lineend[start] + 1
1
3
  • The algorithm is supposed to print the paragraph "neatly"
  • Padding space at the end of lines (except at the end) is not "neat"
  • Thus, the algorithm should minimize such padding
  • The exact measure of "neatness" is the sum of the squares of the padding on each line (a very common measure of compound errors, that basically implies that it's more acceptable to have many small errors than a few large ones).
1
  • +1, but it actually calls for the sum of cubes of padding, not the sum of squares. (I guess it makes it even less likely to produce lines with big gaps.) Sep 22, 2012 at 5:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.