Assigned | 15 Oct 2003 |
Due | 28 Oct 2003 |
/afs/umbc.edu/users/o/a/oates/pub/CMSC341/Proj3/
/afs/umbc.edu/users/o/a/oates/pub/CMSC341/Proj3/341-Fall03-p3_questions.txt
to your own directory and edit it to provide your answers to the questions. Don't forget to submit the edited file; it's 10% of this project's grade.
There are two concepts that must be grasped before this project can be completed. The first is the nature of the FCNS representation of a tree. The second is the structure of a Trie. In an FCNS tree, each node contains a pointer to its first child and a pointer to its next sibling. Given the binary search tree below using the standard left/right child pointers:
10 / \ / \ 5 20 / \ / \ 3 7It would be represented as an FCNS tree as follows:
10 / / 5-----20 / / 3-----7Note the a node can have any number of children. For example, in the tree below, node 10 has children 5, 20, 30, and 40:
10 / / 5-----20-----30-----40 / / 3-----7A Trie is typically used to store strings, which are sequences of characters. Your implementation will be templated to store sequences of OBJECTs. Tries differ from BSTs in the way the strings are stored. A BST stores one string per node, whereas a Trie stores one character per node. An example might clarify things. Suppose you want to store the strings "bag", "ban", "bat", "bagel", "an", and "ant" in a Trie. It would look like this using an FCNS tree:
ROOT / / A-----B / / / / *N A / / / / *T *G-----*N-----*T / / E / / *LEvery path from the root of this tree to a node corresponds to a word or a prefix of a word. For example
A->N->Tcorresponds to the end of a word, but
B->A->G->Edoes not. It corresponds to a prefix of a word, i.e. "bagel". Nodes that correspond to ends of words are marked with a *. Note that the root does not contain any data, and it may have as many children as there are letters in the alphabet. Likewise, every other node may have as many children as there are letters in the alphabet. Your Trie must use an FCNS representation and it must support (at least) the following two public methods:
Trie < char > trie; char *word = "test"; trie.insert(word, 4);In the code above, the Trie contains characters in its nodes, and after the insert method returns the Trie will contain 5 nodes, one for the root and one for each character in the word "test". A Trie that contains sequences of integers rather than characters might be used like this:
Trie < int > trie; int nums[] = {1, 2, 3, 4}; trie.insert(nums, 4);
class Wrapper < OBJECT > { private: OBJECT x; boolean end_of_word; }When a sequence is inserted into the Trie, it will declare a sequence of Wrapper objects for which the end_of_word marker will be false for all but the last one.
The return types and other aspects of these methods, such as whether they and/or their arguments should be const, is left up to you. As usual, you can create any private data members or methods you need. You can write any public methods for which there is a good justification for why they are not private. When trying to determine if a method should be public, ask yourself whether it is reasonable for a programmer who is using your code as a package to call that method. Does it reveal or make accessible too much of the internals of the implementation? Fell free to submit a README file with your project to justify any public methods that you think need it. Any public methods in the author's BST code that you don't need do not need to be implemented.
Search in the Trie should be case insensitive. That is, if the text file contains "What" and "what", and the word "what" is in the dictionary, then both forms should be recognized as being spelled correctly. There will be no characters in the files other than upper and lower case letters and white space.
Note that you must check command line arguments to ensure that they
are valid, e.g. that the command file can be opened, and print an
appropriate message if an error is found.
If you don't submit a project correctly, you will not get credit
for it. Why throw away all that hard work you did to write the project?
Check your
submittals. Make sure they work. Do this before the due date.
Documentation for the submit program is on the web at http://www.gl.umbc.edu/submit/.
One of the tools provided by the submit program is
submitls. It lists the names of the files you have submitted.
Additionally, there are two programs for use only by CMSC-341 students
(not part of the UCS submit program). They are in the directory
/afs/umbc.edu/users/o/a/oates/pub/CMSC341/ and are
named submitmake and submitrun. You can
use these programs to
make or run your submitted projects.
The syntax is similar to that for submit:
submitmake <class> <project>
Example: submitmake cs341 Proj3
This makes the project, and shows you the report from the make utility.
It cleans up the directory after making the project (removes .o and ii_files),
but leaves the
executable in place.
submitrun <class> <project> [command-line args]
Example: submitrun cs341Proj3 checkers checkfile.dat
This runs the project, assuming there is an executable (i.e. submitmake
was run successfully).
Project grading is described in the Project Policy handout.
Your answers to 341-Fall03-proj3_questions.txt are worth 10% of your project grade.
Cheating in any form will not be tolerated. Please re-read the Project Policy handout for further details on honesty in doing projects for this course.
Remember, the due date is firm. Submittals made after midnight of the
due date will not be accepted. Do not submit any files after that time.