Overview
You should start this group activity by introducing each member of the group. One group member should be the scribe, this person is responsible for recording the group's endeavors.
For this assignment, your group will describe an algorithm and program for a task. You won't write code. You will write a description of an algorithm and program you might develop. You might have to implement the algorithm and program you describe, but not necessarily.
Input:
a file of words, one word per line
Output:
a sequence of lines with each line consisting of words that are anagrams of each other. All words that have an anagram in the input file must appear in the output. Words that do not have an anagram are not part of the output.
For example, the input file below on the left would generate the output shown on the right.
backbone caret cater computer crate esprit gory gyro iostropy lament mantle mental orgy iostropy porosity porosity caret cater crate trace priest gory gyro orgy recuse lament mantle mental rescue recuse rescue secure secure esprit priest sprite stripe sprite stripe trace vacuum
Summary
Turn in a written description of the algorithm, a brief outline of alternatives considered, and an estimate of coding and running times. In addition to describing the method, you should estimate how long it would take to implement the algorithm as a working C++ program and how long it would take to process a file of 20,000 words using a ``fast'' computer such as a Sparcstation, a Pentium, or a PowerPC.
Written Description
You must write a description of the method you'd use to solve this problem. Each group will turn in a single write-up, be sure that the name of each group member is on the write-up.
The method should be sufficiently detailed that it can be used as a plan in implementing a program that meets the specification of the problem above. The language used for implementing the program shouldn't be a concern; assume that you'll be using C++ (or Pascal if it helps with the write-up). The description should NOT be overly detailed. Sentences like ``I'd declare an integer variable here'' are at too low a level of detail. Something like ``use an array to do X'' is NOT (necessarily) at too low a level of detail.
You should note in your writeup any assumptions you've made about the specification of the problem. For example, if the number of words in the input file affects the method you propose you should mention this. You should then discuss how your method will deal with an input file that doesn't meet the specifications or your assumptions.
You should include in your writeup any alternatives you thought of/investigated and decided against. Reasons for your decisions should be given.
Your write-up must be sufficiently detailed and precise that its correctness is evident. You shouldn't need to come in to argue a point with the instructor or a TA. It might be useful to imagine someone else in the class reading your description and critiquing it. This is a hint.
In your writeup you should include an estimate of how long you think it would take you to implement a program (in C++) using the method you describe. A brief justification of your estimate should be included.
Finally, you should include an estimate of how long it will take your program to run. Assume that the input file has approximately 20,000 words in it. Again a brief justification of your reasoning is in order.
Don't worry if these estimates are off by a factor of 100, your justification and reasoning are what's important.