4
$\begingroup$

If you do a quick search for suffix trees on Google, you'll find a bunch of sources saying that Don Knuth called them the "Algorithm of the Year 1973." However, I can't seem to find a source on this.

Is there a reference to a paper, communication, etc. where Knuth specifically says this about suffix trees?

Improve this question
$\endgroup$
7
$\begingroup$

The source of the quote seems to be From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction by Giegerich and Kurtz.

On page 347, at the start of Section 6 (An Explanation of Weiner's Algorithm), they write

In this section we go back to the roots and take a look at the “Algorithm of the Year 1973” (D. E. Knuth according to [19]).

Reference [19] is an unpublished manuscript:

[19] V.R. Pratt. Improvements and Applications of the Weiner Repetition Finder. Unpublished manuscript, Cambridge, MA, 1973.

Apparently these are lecture notes (this is how they are referred to in the monograph Image and Text Compression by Storer).

Improve this answer
$\endgroup$
1
  • $\begingroup$ For context, note also that Vaughan Pratt was a PhD student of Knuth, later colleague at Stanford. (E.g. “Knuth–Morris–Pratt”.) So it makes sense that he'd have personal communication with Knuth about algorithms. And Knuth had conjectured something that turned out to be false with the discovery of suffix trees, so he had special reason to be excited as well. $\endgroup$ – ShreevatsaR Apr 12 '18 at 6:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.