Homework Assignment 3

SMS: A User Interface for a Short Messaging System
15-211 Spring 2003

Program Due: Monday February 10, 2003, 11:59pm


Short messaging (aka "chat") on cellular telephones is becoming extremely popular, especially in parts of Europe and Asia. One reason for its rise in popularity is the development of dictionary-based user interfaces that make it much easier to type words using only a small telephone keypad. Your task in this homework assignment is to implement just such a dictionary-based user interface for a telephone SMS system.

You must work on your own for this assignment, and what you hand in must be your own original Java code.


The goals for this assignment are as follows:

When you have successfully completed this assignment, you will be ready to start work on the upcoming homework assignments that involve much larger and more open-ended problems than we've seen thus far in the course.


Please create a private directory for your work and then download the file hw3.jar into it. If you want, you can unpack the jar file by using the command

    % jar xf hw3.jar

This will result in the creation of a directory called phone containing the Java source files and documentation for this assignment. Alternatively, some editors (such as GNU Emacs) will allow you to edit and navigate in the jar file directly.

To perform this assignment, please follow these instructions:

  1. The file phone/doc/index.html contains complete documentation for all of the source code we have provided for this assignment. You should use your favorite browser to read this and familiarize yourself with the entire Phone application program.
  2. You may compile and run the Phone program by using the commands:
            % cd phone
            % javac Phone.java
            % unzip sms/dictionary.zip
            % java Phone sms/dictionary.txt
    This should bring up a small window that has the appearance of a simple cellular telephone. You should play around with this in order to familiarize yourself with its operation. Note that there is a help button that will raise a window containing some simple instructions for use. You should try out the "abc mode" of entry, and try typing in a few short text messages this way.
  3. Undoubtedly you will have discovered by now that entering even very short messages is painfully slow and inconvenient when using the abc-mode of entry. Your job, then, is to implement a much nicer dictionary-based mode of entry, which we call the "word mode". In order to make your job easier, we have created a template for your implementation of the word-mode entry system, in the file sms/HW3.java. You should note that this class must extend the sms/AbstractWordMode.java abstract class, which you should study very carefully.
  4. Your task for this assignment is to complete an implementation of the word-mode entry system for the cellphone application. You must do this by implementing the sms/HW3.java class, without changing its interface. (In other words, your HW3 class is required to extend the AbstractWordMode abstract class.) You may add new Java source files to the sms/ directory if you want. The word-mode entry should work as shown in the lecture notes of January 30, 2003. As indicated in that lecture, we strongly recommend that you use a trie data structure to represent the dictionary in your implementation.

    The word-mode entry system translates sequences of digits into words found in the dictionary. When a sequence of digits corresponds to a complete word in the dictionary, the display is changed to display that word. If more than one word corresponds to the same sequence of digits, the most common word is displayed first. The remaining words are subsequently displayed (in frequency order) in response to successive presses of the "next" button. For additional details regarding the exact behavior expected in word-mode, see the documentation of the AbstractWordMode class.

    We have provided a sample implementation for you to try out. To run the sample solution use the command:

            % java Phone -samplesolution sms/dictionary.txt
    Note that although this sample solution prints out possibly useful debugging information to the terminal, your solution does not need to print anything to the terminal. Finally, here is a small example of the expected output given a series of key presses in word-mode.

    Key       Display       Comments
    4 i Neither g nor h is a word in the dictionary.
    # i The # key is used as a space.
    5 i j Neither j, k, nor l is a word, so the first letter on the key (j) is displayed by default.
    6 i jo The word jo is in our dictionary. Maybe it's a name?
    8 i lot The word lot is a lot more frequent than the word jot.
    0 i jot The 0 key is used to display the next valid word.
    3 i love love is more common than loud.
    # i love
    9 i love w
    6 i love yo
    8 i love you
    clr i love yo The clear key just removes the last character.
    0 i love wo The word wo is second most frequent after yo.
    6 i love won
    0 i love zoo
    clr i love zo zo isn't a word, but clear just removes the last character.
    0 i love yo The next word resets to the most frequent word after a backspace.
  5. To help you get started, we have provided a large plain text file containing dictionary words (dictionary.zip). This dictionary is sorted by word frequency: the most frequent word is listed first. Your constructor for the HW3 class should read in this text file and create your internal (trie-based) dictionary data structure.

Extra Credit

The assignment specifies that in word mode the most frequent word is always displayed first. However, better predictions can be made by taking the context of the word into account. For example, map is a more common word than nap, but after the word quick we would expect to see nap more often map. After the word Pittsburgh, however, we would be more likely to see map. For five points extra credit, use your n-gram generating code from the previous assignment to make the word selection more context-sensitive. Words which correspond to the same sequence of digits should be ordered according to their likelihood given the previous n-1 words.

Before you can submit the extra credit you must complete the basic functionality described above and submit that code as HW3.java. We have created a file sms/HW3ExtraCredit.java for the extra credit version of the word-mode class. You only need to handin this file if you are submitting the extra credit. This file will be tested in the same way as HW3.java except that the input file will no longer be a dictionary but an input file with the following format:

The input file will contain the following, on separate lines:

The data file will be a text file with complete sentences, such as the Shakespeare text provided for the previous assignment. Please note that if you choose to complete the extra credit, you are on your own. TAs are not allowed to help with any problems implementing the extra credit.

Provided, Deliverable Code

We have provided the complete code for the graphical user interface for the telephone application. Furthermore, we have provided documented Java interfaces for the classes you are required to implement, in the sms/AbstractWordMode.java file. Finally, we have also provided a skeleton source file in the sms/HW3.java file. Your task is simply to write the code for this HW3.java file, adding additional source files as you deem necessary or convenient.

Complete web-based "javadoc" documentation for all of the code we have provided can be found in the doc subdirectory. Simply use your favorite web browser to open the doc/index.html file to view it.

Before Monday, February 10, 11:59pm, you must hand in a Java archive file called hw3.jar, using the handin system. This Java archive file must contain a single directory called sms that contains all of the Java code that you have written for this assignment. We will be linking your HW3.class with a special test harness that will perform some automatic grading of your program. In order for this to work, it is important that your HW3 class extends the AbstractWordMode interface that we have supplied to you.


Your assignment will be graded first by compiling and testing it. Since this testing process is automatic, it is very important that your hw3.jar file unpacks into a directory called "sms". We will unpack and compile your code by using the command:

% jar xf hw3.jar
% javac -classpath "." sms/*.java

We will do this in a directory that already contains a gui/ subdirectory that in turn contains the TextDisplay class. Prior to testing, we will copy our KeyPressHandler, Help, WordMode, AbstractWordMode, and dictionary.txt files into your sms directory. Obviously, if you hand in additional files other than HW3, you must not use these file names.

We recommend that you make sure that this command succeeds before you hand in your assignment. If unpacking and compilation succeeds, we will link your HW3 class into a testing program in order to exercise your code.

After the automatic testing, we will read your code to determine whether appropriate data structures and algorithms were used, as well as judge the overall style of your code.

Each part of this assignment will be graded independently, with the following point breakdown:

Correctness testing 30 points
Appropriate data structures 15 points
Coding style 5 points
Total 50 points

Programs will be graded both on correctness as well as their ability to deal with so-called edge cases, like empty dictionaries, dictionaries with only one element, and so on. The more cases you can deal with, the more likely that you will receive complete credit. Points will be deducted for poor design decisions and un-commented, or un-readable code as determined by your TA.

This should go without saying...

...but just to be 100% clear, you are expected to implement your own dictionary data structure for this assignment. You can use java.util.* dictionary or collections classes as auxiliary data structures, but overuse will very likely lead to a significant loss of points. All of your code must be original.