Difficulty: *
This test is based on the simple, brute force, approach to suffix tree construction, using moderately straightforward list processing functions that students were required to define in the earlier parts of the test.
The test appears here almost exactly as it was originally set, with only minor adjustments made to the formatting. Quite a few students completed the test in full within the three hours. The impression was that the final part was actually relatively easy once you’d mastered the tree construction. The average mark was around 75%.
Specification
Template File
More Information
The Wikipedia article on suffix trees provides a useful digest, including references to Ukkonen’s original paper. Of particular interest to Haskellers is the paper by Robert Giegerich and Stefan Kurtz, A comparison of imperative and purely functional suffix tree constructions, which builds the tree lazily, top down, rather than by repeated insertion of suffixes, as here. Data.SuffixTree, written by Bryan O’Sullivan, is based on an implementation of the lazy construction algorithm in Haskell.