CSci 433: Algorithm & Data Structure Analysis
Spring Semester 1999

Program #1 (Word Unscrambling)
Due Thursday, 4 February, Midnight

Note: The due date has been changed. See above.

Note: This is modified version of one of the six programming problems given during the (five-hour long) ACM Mid-Central Regional programming contest last November.

Note: I have a few comments on the class bulletin board page concerning file I/O that you may find helpful.

In newspapers across the United States there is a word game called Jumble. The object of this game is to solve a riddle, but in order to find the letters that appear in the answer it is necessary to unscramble four words. Your task is to write a program named Unscramble that can unscramble words.

This program has two input files. Both files are text files that contain lists of "words". For our purpose here assume that a "word" is any nonempty sequence of lowercase, alphabetic Ascii characters ('a' thru 'z') without any embedded space characters or punctuation. Each word is written by itself on a line of the file. Assume there are no errors in the input file.

1. The first input file is a vocabulary list, a list of English words that your program will recognize. The words are not necessarily in alphabetically sorted order and are not necessarily unique within the list. (The second copy of a words should be ignored by your program, however.)

2. The second input file is a scrambled word list, supposedly a list of English words that have been scrambled. By "scrambled", we mean that all letters appear, but their order has probably been changed. (That is, the scrambled word may be a permutation of the letters in an English word.)

For each scrambled word in the input, output to a third file an alphabetical list of all vocabulary words that can be formed by rearranging the letters in the scrambled word. Each word in this list must appear on a line by itself. If the list is empty (because no vocabulary words can be formed), output the left-justified line

INVALID WORD:  xxx

**********

The file names should be taken as command line arguments of the program. They must be given in the order described above, vocabulary list, scrambled word list, and output file.

Example vocabulary list:

tarp
given
score
refund
only
trap
work
earn
course
pepper
part

Example scrambled word list:

resco
nfudre
aptr
sett
oresuc

Example output file:

score
**********
refund
**********
part
tarp
trap
**********
INVALID WORD:  sett
**********
course
**********

Other instructions:

• Please make the program name, command line arguments, and output file format exactly match the descriptions given above. In the grading process, we may compare your program's output file and a solution file with a file comparison program.

• Test your program appropriately and thoroughly with test data of your own construction. You will not have access to the test data used by the instructor in grading your program!

• Use good program design techniques. For example, you should define an appropriate abstract data type (i.e., class) to store and manipulate the vocabulary list so that its representation can be easily changed. Similarly, you might want to implement the unscrambling-process using an iterator (enumerator).

• Please format and document your program source code appropriately.

• When this assignment is complete, submit a paper listing of your program source code. Be sure all items submitted are clearly labeled with your name and the assignment number.

• Also submit your program source code using EASE, the Electronic Assignment Submission Environment, at URL http://www.cs.olemiss.edu/submit/. I'll give you the username and password for this system later. Your username for that system is your sunset account name in most cases.

UP to CSCI 433 assignments document?