Lecture 11: Dynamic Programming: Typesetting
We studied more examples of dynamic programming, including the typesetting problem that LaTex solves when it processes your input files.
To view this video please enable JavaScript, and consider upgrading to a web browser that supports HTML5 video
A typesetting program
You can download typeset.java and a sample input file or inspect the code below to see how to transform an abstract description of a DP algorithm that we discussed in class into a program.
// Dynamic programming implementation of the typesetting algorithm described in lecture
// CS4102, Algorithms, U. of Virginia, Sep 26, 2013
// abhi shelat
// abhi@virginia.edu
//
// please send improvements of this example to me
public class typeset {
public static void main(String args[]) {
if (args.length<2) {
System.out.println("Usage: java typset <file> <M>");
System.exit(1);
}
// read input, parse into an array of words
try {
BufferedReader bin = new BufferedReader(new FileReader(args[0]));
String line = bin.readLine();
String words[] = line.split(" ");
int n = words.length;
int M = Integer.parseInt(args[1]);
int lens[] = new int[n+1];
for(int i=1;i<=n; i++) {
lens[i] = words[i-1].length();
if (lens[i]>M) {
System.out.println("word too long");
System.exit(1);
}
}
// value for S_ij when placing words i..j on a line causes overflow
int infty = M*M*2;
// compute S_ij
int S[][] = new int[n+1][n+1];
for(int i=1;i<=n;i++) {
S[i][i] = M - lens[i];
for(int j=i+1; j<=n; j++) {
S[i][j] = S[i][j-1] - lens[j] - 1;
if (S[i][j]<0) {
// once overflow occurs, set to infty
while(j<=n) { S[i][j++] = infty; }
}
}
}
// compute best_0,...,best_n
int best[] = new int[n+1];
int choice[] = new int[n+1];
best[0] = 0;
for(int i=1;i<=n;i++) {
int min = infty;
int ch = 0;
for(int j=0;j<i;j++) {
int t = best[j] + S[j+1][i]*S[j+1][i];
// keep track of min, and choice that lead to min
if (t<min) { min = t; ch = j; }
}
best[i] = min;
choice[i] = ch;
}
for(int i=0;i<=n;i++) {
System.out.println(i + " best: " + best[i] + " ch " + choice[i]);
}
// backtrack to output linebreaks.
// we backtrack in reverse order, so we store lines in an array
// and then print them out in the right order
int end = n;
int start = choice[end]+1;
String lines[] = new String[n];
int cnt = 0;
while (end>0) {
StringBuffer buf = new StringBuffer();
for(int j=start; j<=end; j++) {
buf.append(words[j-1] + " ");
}
lines[cnt++] = buf.toString();
end = start-1;
start = choice[end]+1;
}
// print lines in reverse order
for(int j=cnt-1; j>=0; j-- ) {
System.out.println(lines[j]);
}
} catch(Exception e) {
e.printStackTrace();
}
}To run this program use:
$ javac typeset.java
$ java typeset charly.txt 42
It will produce output like this:
0 best: 0 ch: 0
1 best:1600 ch: 0
2 best:1296 ch: 0
3 best:1024 ch: 0
4 best: 729 ch: 0
5 best: 576 ch: 0
6 best: 289 ch: 0
7 best: 196 ch: 0
8 best: 100 ch: 0
9 best: 36 ch: 0
10 best: 0 ch: 0
11 best: 818 ch: 6
12 best: 545 ch: 6
13 best: 452 ch: 7
14 best: 340 ch: 7
15 best: 244 ch: 8
16 best: 164 ch: 8
17 best: 117 ch: 9
18 best: 37 ch: 9
19 best: 16 ch: 10
20 best: 0 ch: 10
21 best: 509 ch: 14
22 best: 413 ch: 15
23 best: 344 ch: 15
24 best: 133 ch: 17
25 best: 118 ch: 17
26 best: 62 ch: 18
27 best: 32 ch: 19
28 best: 4 ch: 20
29 best: 444 ch: 23
30 best: 348 ch: 23
31 best: 277 ch: 24
32 best: 197 ch: 24
33 best: 149 ch: 24
34 best: 87 ch: 26
35 best: 66 ch: 26
36 best: 446 ch: 31
37 best: 377 ch: 31
38 best: 297 ch: 32
39 best: 233 ch: 32
40 best: 158 ch: 33
41 best: 123 ch: 34
42 best: 70 ch: 35
43 best: 590 ch: 36
44 best: 498 ch: 37
45 best: 418 ch: 38
46 best: 297 ch: 39
47 best: 258 ch: 39
48 best: 148 ch: 41
49 best: 127 ch: 41
50 best: 95 ch: 42
51 best: 71 ch: 42
52 best: 441 ch: 46
53 best: 378 ch: 46
54 best: 294 ch: 47
55 best: 267 ch: 47
56 best: 229 ch: 48
57 best: 173 ch: 48
58 best: 120 ch: 50
59 best: 99 ch: 50
60 best: 427 ch: 53
61 best: 394 ch: 53
62 best: 330 ch: 54
63 best: 209 ch: 57
64 best: 156 ch: 58
65 best: 124 ch: 58
66 best: 103 ch: 59
67 best: 476 ch: 60
68 best: 366 ch: 62
69 best: 309 ch: 63
70 best: 245 ch: 63
71 best: 218 ch: 63
72 best: 181 ch: 64
73 best: 149 ch: 65
74 best: 107 ch: 66
75 best: 415 ch: 68
76 best: 382 ch: 68
77 best: 294 ch: 70
78 best: 261 ch: 70
79 best: 222 ch: 71
80 best: 190 ch: 72
81 best: 150 ch: 73
82 best: 107 ch: 74
83 best: 418 ch: 76
84 best: 358 ch: 77
85 best: 310 ch: 77
86 best: 286 ch: 78
87 best: 265 ch: 78
88 best: 206 ch: 80
89 best: 186 ch: 81
90 best: 143 ch: 82
91 best: 111 ch: 82
92 best: 427 ch: 83
93 best: 383 ch: 84
94 best: 322 ch: 86
95 best: 290 ch: 86
96 best: 222 ch: 88
97 best: 186 ch: 89
98 best: 147 ch: 90
99 best: 112 ch: 91
100 best: 408 ch: 93
101 best: 358 ch: 94
102 best: 291 ch: 95
103 best: 211 ch: 97
104 best: 148 ch: 98
105 best: 121 ch: 99
106 best: 394 ch:101
107 best: 358 ch:101
108 best: 332 ch:103
109 best: 260 ch:103
110 best: 215 ch:103
111 best: 212 ch:104
112 best: 164 ch:104
113 best: 122 ch:105
114 best: 398 ch:106
115 best: 374 ch:107
116 best: 296 ch:109
117 best: 231 ch:110
118 best: 216 ch:110
119 best: 131 ch:113
120 best: 390 ch:115
It was the best of times, it was the
worst of times, it was the age of wisdom,
it was the age of foolishness, it was
the epoch of belief, it was the epoch
of incredulity, it was the season of
Light, it was the season of Darkness,
it was the spring of hope, it was the
winter of despair, we had everything
before us, we had nothing before us,
we were all going direct to heaven, we
were all going direct the other way -
in short, the period was so far like
the present period, that some of its
noisiest authorities insisted on its being
received, for good or for evil, in the
superlative degree of comparison only.
By commenting out some lines and replacing them with others, you can easily change the program to produce the intermediate typesetting results for each $n$ that I showed in class:
0 best: 0 ch: 0
1 best:1600 ch: 0 It\n
2 best:1296 ch: 0 It was\n
3 best:1024 ch: 0 It was the\n
4 best: 729 ch: 0 It was the best\n
5 best: 576 ch: 0 It was the best of\n
6 best: 289 ch: 0 It was the best of times,\n
7 best: 196 ch: 0 It was the best of times, it\n
8 best: 100 ch: 0 It was the best of times, it was\n
9 best: 36 ch: 0 It was the best of times, it was the\n
10 best: 0 ch: 0 It was the best of times, it was the worst\n
11 best: 818 ch: 6 It was the best of times,\nit was the worst of\n
12 best: 545 ch: 6 It was the best of times,\nit was the worst of times,\n
13 best: 452 ch: 7 It was the best of times, it\nwas the worst of times, it\n
14 best: 340 ch: 7 It was the best of times, it\nwas the worst of times, it was\n
15 best: 244 ch: 8 It was the best of times, it was\nthe worst of times, it was the\n
16 best: 164 ch: 8 It was the best of times, it was\nthe worst of times, it was the age\n
17 best: 117 ch: 9 It was the best of times, it was the\nworst of times, it was the age of\n
18 best: 37 ch: 9 It was the best of times, it was the\nworst of times, it was the age of wisdom,\n
19 best: 16 ch: 10 It was the best of times, it was the worst\nof times, it was the age of wisdom, it\n
20 best: 0 ch: 10 It was the best of times, it was the worst\nof times, it was the age of wisdom, it was\n
21 best: 509 ch: 14 It was the best of times, it\nwas the worst of times, it was\nthe age of wisdom, it was the\n
22 best: 413 ch: 15 It was the best of times, it was\nthe worst of times, it was the\nage of wisdom, it was the age\n
23 best: 344 ch: 15 It was the best of times, it was\nthe worst of times, it was the\nage of wisdom, it was the age of\n
24 best: 133 ch: 17 It was the best of times, it was the\nworst of times, it was the age of\nwisdom, it was the age of foolishness,\n
25 best: 118 ch: 17 It was the best of times, it was the\nworst of times, it was the age of\nwisdom, it was the age of foolishness, it\n
26 best: 62 ch: 18 It was the best of times, it was the\nworst of times, it was the age of wisdom,\nit was the age of foolishness, it was\n
27 best: 32 ch: 19 It was the best of times, it was the worst\nof times, it was the age of wisdom, it\nwas the age of foolishness, it was the\n
28 best: 4 ch: 20 It was the best of times, it was the worst\nof times, it was the age of wisdom, it was\nthe age of foolishness, it was the epoch\n
29 best: 444 ch: 23 It was the best of times, it was\nthe worst of times, it was the\nage of wisdom, it was the age of\nfoolishness, it was the epoch of\n