Department of
Computer Science

CS 420/520: Object-Oriented Programming

Assignment 3: Implement a Trie

Set: Monday 19^th October 2000

Code due: Thursday 29^th October 2009 at or before midnight

Summamary

In the class repository on SqueakSource you will find a unit test (class TrieTest) for a data structure called a Trie. Your assignment is to implement a class Trie so that the all tests pass.

Groups

It is best to do this assignment as a pair. I will also accept assignment form individuals. Groups of three or more are NOT PERMITTED.

What's a Trie

A trie, (pronounced "tree", from the word re-trie-val, or "try", for differentiation), is a prefix tree useful for implmenting sets of strings, or dictionaries whose keys are strings. There is a good description in Wikipedia. But in fact, the tests will tell you what to implement: if they all passs, and the structure that you built is a prefix tree, you can't have gone too far wrong.

What I'm looking For

Here is the grading rubric. As far as fucntionality goes, consider the tests to be a specification. For example, here is a test:

testAdd
    "Create a trie with 'hi'. add: x should be the same as at x put: nil."

     | t added |
     t := Trie new.
     self assert: [t size = 0].
     added := t add: 'hi' .
     self assert: [t includesKey: 'hi'].
     self assert: [(t at: 'hi') == nil].
     self assert: [added = 'hi'].
     self deny: [t includesKey: 'h']

This tells you that ties understand the size message, the includesKey: message, and the at: message, as well as the add: message. It tells you that a trie behaves like a dictionary, and that adding a key without an associated value implicitly associates nil withthe key. It aslso tells you that the result of adding a key is the key itself. If there are still ambiguities in th ebehavior of tries, ask me about them; I'll respond by adding more tests.

Getting the Tests

Visit the class repository

MCHttpRepository
location: 'http://www.squeaksource.com/PSUCS520'
user: '<your name>'
password: ''

and load the package 'Trie-Tests'

Hints

1. Don't try and make all of the tests pass at once. Start with the tests for some of the basic functionality, like testAdd and tetsAtPut. Once you have one test passing, add another. If you write helper methods (and you will need to do so), you may want to write unit tests for them too.
2. Don't write long methods. Use the composed method pattern, both because I'm grading on it, and because it will keep your code clean. If you are navigating and the driver has written more than 5 lines, warn the driver. My longest method was 9 lines, and most were 1 to 3 lines long.
3. Tries are a special kind of dictionary. That does not mean that they should be a subclass of Dictionary, though, becasue the implementation of Dictionary is completely different. So, think about what you should subclass. If you subclass the wrong class, you will find that you are having to re-implement many, many methods that you could have inherited.
4. As you learn more about the problem space, you will realize taht some of your early decisions were wrong. Don't be affraid to go back and change them. Software is soft!

Submitting your work

Submit your work as a Monticello version (a .mcz file) by email to cs520-hw, with a subject line like this:

Subject: [CS520 Assignment 3] Wilma Flintstone and Barny Rubble