Assignment 3

Question 1

Consider the following problem that has arisen at the Avalon Intelligence Agency (AIA): The AIA has recently bought and installed a set of one-way transponders that relay coded messages from agents in the field to the top-secret AIA headquarters under Leo's Fish and Chips on Freshwater Road. To the chagrin of the Communications Division, these transponders randomly perform sequences of zero or more scramble operations on incoming codewords. The Communications Division has determined that the only scramble operations that the transponders inadvertently perform are the following:
• Change a vowel-symbol in the codeword to another vowel-symbol, e.g., bat => bit.
• Change a consonant-symbol in the codeword to another consonant-symbol, e.g., bat => tat.
• Insert a symbol somewhere in the codeword, e.g., bt => bat.
• Delete a symbol from the codeword, e.g., e.g., bat => at.
• Repeat a symbol in the codeword two or more times, e.g., bat => baaaaat.
• Collapse two or more repeats of a symbol in the codeword to a single symbol, e.g., baaat => bat.

Fortunately, all standard codewords are listed in the AIA codebook. The question then becomes, given a scrambled codeword, what was the most likely original codeword, i.e., which of the standard codewords can be converted into the scrambled codeword using a minimum number of scrambling operations over the set of standard codewords? Note that there may be several standard codewords that are related to a scrambled codeword by the minimum number of scrambling operations.

Write and document a Java program that uses a dynamic programming algorithm to solve the problem described above. This program will take as command-line input a scrambled codeword and the filename of a codebook. An example codebook file cb1.txt is as follows:

4
abaaa
abaaaa
cabaaa
dcabaaa

Each such file of n codewords consists of n + 1 lines, where the first line contains the integer n and the remaining lines contain the codewords, one per line. You may assume that all codewords consist of lowercase letters without embedded spaces and that all input files are formatted correctly. Examples of several program runs relative to the codebook files cb1.txt and cb2.txt are given in script file out.script.

Hints

You may find the standard dynamic programming algorithm for computing the length of the longest common subsequence of two given strings a convenient starting point for developing your operation-counting algorithm.

Questions 2 -- 4

The text of these questions is available in PostScript and PDF format.

Assignment Submission

Please hand in printed copies of all of your Java source code files for Question #1 along with your answers for Questions #2 -- 6. You must also submit the files for Question #1 electronically using the submit-assignment command. Note that each such file must have the following comment block at the top, where the X's are replaced with the appropriate information. For instance, my code for this assignment would begin with the following comment block:

/////////////////////////////////////////////////////////////////
//  CS 3711 (Fall 2005), Assignment #3, Question #1            //
//  Program File Name: DCW.java                                //
//       Student Name: Todd Wareham                            //
//         Login Name: harold                                  //
//              MUN #: 8008765                                 //
/////////////////////////////////////////////////////////////////

You do not have to develop your code on our CS departmental systems. However, as your code will be compiled and tested on our CS departmental systems as part of the assignment marking process, you should ensure that your code compiles and runs correctly on at least one of these systems.

Additional Notes:

• Oct 25, 11:00am
  Assignment due date revised to Oct 28.

• Oct 11, 11:55am
  Assignment #3 posted.

Created: September 23, 2005
Last Modified: October 25, 2005