CMSC-341 Fall 2004
Project 3
Assigned |
20 Oct 2004 |
Due |
2 Nov 2004 at 11:59PM |
Updates
|
Background
This project will give you practice working with binary search trees
and with writing recursive functions.
Description
In this project you will write code to manipulate and compute
properties of binary search trees.
Here are your tasks:
- Obtain the files BinarySearchTree.h, BinarySearchTree.cpp, and
dsexceptions.h from the following location:
/afs/umbc.edu/users/o/a/oates/pub/CMSC341/Proj3/
These files do not adhere to CS341 coding standards. You can use them
"as is". That is, you do not need to edit them to bring them up to
CS341 standards.
- Write Proj3.cpp and any supporting files required to process
command files.
- Implement new BinarySearchTree methods required to process
commands contained in command files.
-
Answer the questions posed in 341-Fall04-proj3_questions.txt. Copy the
file
/afs/umbc.edu/users/o/a/oates/pub/CMSC341/Proj3/341-Fall04-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.
Definition of the ADT
This project simply requires that you be able to process the commands
contained in a command file. Those commands load trees, manipulate
trees (e.g., creating a tree that contains the union of the elements
in two other trees), and compute properties of trees (e.g., whether a
given tree is a complete tree). You may implement any new classes
that you need to complete the project. Most of the code for this
project, however, will revolve around opening, reading, and closing
the command file, and manipulating and computing properties of trees.
Most of the commands will require that you implement a recursive
BinarySearchTree method. As with many of the existing BST methods,
you will probably want a public method that simply calls a private
method, where the private method is recursive and the public method is
not. See the author's implementation of insert for an example
of this. Your recursive methods can call helper functions and take as
many arguments as you deem necessary.
The Command Line
Project 3 will be invoked with a command line that consists of one
argument - the name of a file that contains a set of operations that
must be performed. The format of this file is described in the command file section below.
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.
The Command File
Commands in the file specify operations to be performed. Each line in
the file represents one command. Blank lines may appear anywhere in
the file and should be ignored. Otherwise, you can assume that any
line containing a command is syntactically well-formed. We make this
assumption so you don't have to spend lots of time making the command
file parser bullet proof.
Echo each command as it is read.
All of the commands below refer to trees by names that are strings.
When creating a tree, you must ensure that a tree with the same name
does not already exist. If it does, print an error message and
proceed to the next command. When a command refers to an existing
tree by name, you must ensure that a tree with that name does in fact
exist. If not, print an error message and proceed to the next
command.
You cannot add a NAME data member to the BinarySearchTree
class.
The command file format follows:
- TREE NAME N V1 V2 ... VN - This command asks you to create a
binary search tree named NAME (a string without any white space). The
tree contains N nodes, and the N integer values to be stored in the
tree are given as part of the command (V1 V2 ... VN). Read each value
and insert it into the tree in the order in which it was read. The
value -1 will never be specified as one of the Vi.
- SAME_SHAPE NAME1 NAME2 - Print a message indicating whether the
trees named NAME1 and NAME2 have the same shape. That is, ignoring
node values, are they identical to one another? Your solution for
this command must involve recursion, and there must be a public
BinarySearchTree method, i.e., same_shape, that takes another
binary search tree as an argument and returns a boolean value.
- PERFECT NAME - Print a message indicating whether the tree named
NAME is a perfect tree. Your solution must involve recursion.
- COMPLETE NAME - Print a message indicating whether the tree named
NAME is a complete tree. Your solution must involve recursion.
- IPL NAME - Print a message indicating the internal path length of
the tree named NAME. Your solution must involve recursion.
- EPL NAME - Print a message indicating the external path length of
the tree named NAME. Your solution must involve recursion.
- UNION NEW_NAME NAME1 NAME2 - Create a tree named NEW_NAME that
contains the union of the elements in the trees named NAME1 and
NAME2. It is OK if both trees contain the same value, but it should
only occur once in the newly created tree. Your solution must
involve a public BST method that takes another tree as an argument.
Neither of the trees that are unioned should be modified.
- INTERSECTION NEW_NAME NAME1 NAME2 - Create a tree named NEW_NAME
that contains only those values that are in the tree named NAME1 and
the tree named NAME2.Your solution must involve a public BST method
that takes another tree as an argument. Neither of the trees that are
interesected should be modified.
- PRINT NAME - Print the contents of the tree named NAME using an
inorder traversal.
Sample Output
The following input file:
TREE amy 3 20 10 30
TREE bob 3 10 5 15
PERFECT amy
PERFECT bob
UNION carl amy bob
PRINT carl
creates the following output:
Command: TREE amy 3 20 10 30
Command: TREE bob 3 10 5 15
Command: PERFECT amy
amy is perfect
Command: PERFECT bob
bob is perfect
Command: UNION carl amy bob
Command: PRINT carl
5 10 15 20 30
Files To Be Submitted
Submit all files required to build an executable named Proj3 by
running make.
Submit the files using the procedure given to you for your section of
the course.
If your makefile is set up correctly, you should be able to execute
the command make submit.
Submit Tools
There are a number of tools available to you to check on your submittal.
It is your responsibility to ensure that the submittal is correct and will
result in a successful
compilation of your project. Do not wait till the last minute to submit
your files. Give yourself enough time to check that your submittal is correct.
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 Proj1
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 cs341Proj1 checkers checkfile.dat
This runs the project, assuming there is an executable (i.e. submitmake
was run successfully).
Grading and Academic Integrity
Your project will be tested using a variety of command lines, some of which
will be invalid.
Your project will also be tested using a variety of command files which
will test various conditions which your code should handle.
Project grading is described in the Project
Policy handout.
Your answers to 341-Fall04-proj1_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.