Science of Computer Programming, Vol. 35, pp. 3-27, 1999.

Authors: Oege de Moor and Jeremy Gibbons
>

Abstract

Naive algorithms for paragraph formatting take time (w*n), where w is the maximum width of a line, and n the length of the text. Better algorithms are known, but rarely implemented: we call this the algorithm gap. We demonstrate that even such nifty algorithms can be presented such that the paper itself is an executable implementation. The algorithm we use as an example also has applications in efficient DNA sequence alignment.

(PS, software)

BIBTEX:

           @article{scp99moor, 
           author = "Oege de Moor and Jeremy Gibbons", 
           title = "Bridging the algorithm gap: a linear-time functional program for paragraph formatting", 
           journal = "Science of Computer Programming",
           volume = "35",
           pages = "3--27",
           year = "1999"}