The Algorithm Design Manual Second Edition

310

8 .

D Y N A M I C P R O G R A M M I N G

Chapter Notes

Bellman

[Bel58]

is credited with developing the technique of dynamic programming.

The edit distance algorithm is originally due to Wagner and Fischer

[WF74

]. A

faster algorithm for the book partition problem appears in

[KMS97

].

The computational complexity of finding the minimum weight triangulation of

disconnected point sets (as opposed to polygons) was a longstanding open problem

that finally fell to Mulzer and Rote

[MR06

].

Techniques such as dynamic programming and backtracking searches can be

used to generate worst-case efficient (although still non-polynomial) algorithms for

many NP-complete problems. See Woeginger

[Woe03]

for a nice survey of such

techniques.

The morphing system that was the subject of the war story in Section

8.4

(page

291

) is described in

[HWK94]

. See our paper

[DRR

+

95]

for more on the Prolog trie

minimization problem, subject of the war story of Section

8.8

(page

304

). Two-

dimensional bar codes, subject of the war story in Section

8.9

(page

307

), were

developed largely through the efforts of Theo Pavlidis and Ynjiun Wang at Stony

Brook

[PSW92]

.

The dynamic programming algorithm presented for parsing is known as the

CKY algorithm after its three independent inventors (Cocke, Kasami, and Younger)

[You67]

. The generalization of parsing to edit distance is due to Aho and Peterson

[AP72]

.