►
C211/ H211: Introduction to Computer Science
▼
Problem sets
Problem set 1: Paint a date in Dr Racket
Problem set 2: Moving rockets
Problem set 3: Composing functions
Problem set 4: Structures and enumerations
Problem set 5: Unions and recursion
Problem set 6: Packs and lists
Problem set 7: Similarities
Problem set 8: Abstraction
Problem set 9: Plotting functions
Problem set 10: Prefix trees
►
Problem set 10: Prefix trees
On this page:
1 Prefix trees
2 Building prefix trees
3 Challenge
7.9.0.4
← prev up next →
Problem set 10: Prefix trees
This assignment is due on Wednesday, November 11 at 7:59pm. Submit it using Handin as assignment ps10.
Remember to follow the design recipe for each function, even if defined locally. In particular, every type mentioned in a signature must be introduced by a data definition, except for these well-known types: Number, Image, String, Boolean, KeyEvent, MouseEvent, Anything, Posn, NaturalNumber, [ListOf X], [Maybe X], [NEListOf X], IWorld, 1String.
Use the “Intermediate Student with lambda” language on this and further assignments in this course.
1 Prefix trees
When data is organized in an unstructured list and we want to search for an element, our last resort is to inspect every item until we find what we’re looking for. This search can be slow if there are many items. For example, count-word in Problem Set 6 is slow, so counting the words in Hamlet took a long time.
Prefix trees are one way to organize data to help search for an element. An example of a prefix tree is all of the entries in a printed dictionary whose headwords start with the same letter. When you are looking for the definition of a word in such a dictionary, it suffices to go letter by letter in alphabetical order.
; A PrefixForest is a [NEListOf PrefixTree]
; A PrefixTree is one of:
; – (make-end)
; – (make-initial 1String PrefixForest)
(define-struct end [])
(define-struct initial [letter forest])
The data definition above refers to a 1String, which is a String of length 1.
An example of a PrefixForest is:
(define forest1
(list
(make-initial “n”
(list
(make-end)
(make-initial “e” (list (make-end)))))
(make-initial “f”
(list
(make-end)
(make-initial “f” (list (make-end)))
(make-initial “t” (list (make-end)))))
(make-initial “r” (list (make-end)))))
This forest stores the strings “n”, “ne”, “f”, “ff”, “ft”, and “r”. It does not store any other string, such as the empty string “”.
An example of a PrefixTree is:
(define tree1 (make-initial “o” forest1))
This tree is displayed visually as:

This tree stores the strings “on”, “one”, “of”, “off”, “oft”, and “or”. It does not store any other string, such as the string “o”, the string “f”, or the empty string “”.
A PrefixForest should never contain multiple initials with the same letter. You can make this assumption when your code receives a PrefixForest in its input, and you must maintain this guarantee when your code produces a PrefixForest in its output. For example, in tree1 above, the letters “n” “f” “r” near the top have to be all different, but it is ok that there is one “f” above another “f”.
Exercise 1. Define two different examples of PrefixTrees (called tree2 and tree3) and two different examples of PrefixForests (called forest2 and forest3).
Exercise 2. Write the templates process-tree and process-forest for functions that process a PrefixTree and a PrefixForest.
Exercise 3. Design functions tree-size and forest-size which report how many strings are stored in a given PrefixTree or PrefixForest. This count is the number of ends in the input. For example, tree1 above stores 6 strings. Hint: Write plenty of examples with all kinds of inputs, including forest1 and tree1 above. Then, follow the template for processing the input.
Exercise 4. Design functions tree->list and forest->list which take a PrefixTree or PrefixForest and returns a [NEListOf String] containing all of the strings stored in the input tree or forest. An end stores just the empty string “”, whereas an initial stores strings that begin with its letter. Hint: Write plenty of examples with all kinds of inputs, including forest1 and tree1 above. Then, follow the template for processing the input!
2 Building prefix trees
We write Word to mean a list of 1Strings.
; a Word is a [ListOf 1String]
Feel free to use explode in your tests to easily convert a string to a Word.
Exercise 5. Design a function word->tree which takes a Word and returns a PrefixTree which stores just that word.
Exercise 6. Design functions word-in-tree? and word-in-forest? which determine whether or not a given Word is stored in a given PrefixTree or PrefixForest.
Note: Do not use tree->list or forest->list from earlier (except possibly for testing). Instead, follow the template for processing the input.
Exercise 7. Design functions add-to-tree and add-to-forest.
add-to-forest takes a Word and a PrefixForest and adds the word to the forest, returning a new forest. Again, a PrefixForest should never contain multiple initials with the same letter.
add-to-tree takes a Word and a PrefixTree and adds the word to the tree, returning a new tree. The given word must be non-empty, and the given tree must be an initial whose letter matches the first letter of the given word.
Exercise 8. Design a function list->forest which takes a [NEListOf String] and returns a PrefixForest that stores the given words (given as strings this time). Hint: follow the template for processing [NEListOf String] and use explode, word->tree, and add-to-forest.
3 Challenge
Exercise 9. Design a function alphabetize which sorts all of the initials in a PrefixForest in alphabetical order according to their letter and which puts all of the ends first. (In other words, for the comparison function, a tree which is an end is less than any initial.) alphabetize should also sort the forest associated to any initial in the input forest. Feel free to use sort and string comparison functions such as stringforest, then alphabetize, then forest->list?
← prev up next →