C M S C     2 1 4
C o m p u t e r   S c i e n c e   I I
S p r i n g   2 0 0 2


Project #3

Due Sunday, April 7th, by 11pm

Early Due Date Friday, April 5th, by 11pm (5 points bonus)


Fourth Posting: April 2, 2002
(BNF posted)

Third Posting: March 22, 2002
(Tutorials added)

Second Posting: March 20, 2002
(Task 10 modified--distribution of proposals changed)

Originally Posted: March 18, 2002
(BNF and tutorials posted soon)

Corrections/Clarifications

These corrections are also listed below in the section associated with the BNF. Also, check MovieBstSortedList specifications. They also have corrections section.

Purpose

  1. To write a BstSortedList template class, which implements a binary search tree with nodes which have pointers to left and right children as well as predecessors and successors. This class has the same functionality as SortedList but is implemented using BSTs.
  2. To write recursive functions. In particular, many of the BstSortedList methods will be recursive.
  3. To evaluate other student's proposals, and give them feedback, as well as provide us feedback.
  4. To implement at least one class for Project 4, and, for a second class, write the header files, implement ONLY the runTestDriver() methods, and produce a sample output file for Project 4
  5. To extend the features of the tester classes, and write a BstMovieTester class.
  6. (EXTRA CREDIT) To write a BstMap class. You will be provided a Pair class and a PairComparator class. BstMap is similar to STL's implementation of its map class (it uses a BST of pair objects).
  7. To debug code from previous project, so that it doesn't give you problems on this one.

Academic Integrity Statement

Please note that *all* programming projects in this course (including this one) are to be done independently or with the assistance of the instructional staff of this course only.

Please review the policies outlined on the class syllabus concerning the use of class computer accounts and concerning the University's Code of Academic Integrity. The instructors of this course will review the programs submitted by students for potential violations of the Code of Academic Integrity and if it is believed that a violation has occurred it will be referred to the Office of Judicial Programs and the Student Honor Council.

Hardcoding is considered a violation of academic integrity

Checklist

Click here before submitting.

Project 3 Checklist

Background

Start project early! The binary search tree project often requires lots of time.

Background Reading

Please read the following as you do the project.

Note: "How Locate Works" has been updated as of March 21, 2002. There's a simpler way to write locate().

Files Provided

In addition to the primary input and primary output, the following files are in the posting account under Projects/P3.

Note: Implementing BstMap will be worth up to 7 points of the project. If you find yourself pressed for time, you may wish to skip the implementation of this class.

Files Submitted

Use Project 3 Checklist (above) as final check for project submission

Class Specifications

Tasks

The following is a suggested way to approach the project.

Task 0: Minor Stuff

  1. Make sure you have nameed your makefile Makefile.
  2. Make sure your Makefile uses constants such as OBJS, CC, FLAGS (as done in Project 1). See the "Makefile Tutorial" in the Tutorial section for details.
  3. Copy main.cpp into a file called run.cpp (you may wish to define a run.h with the prototype void run() in it). Rename the function int main() to void run().
  4. Create a new main.cpp where main() calls run() as its only line of useful code. The purpose of this is to allow us to replace your main() with our own. This becomes a little more difficult if you have written a main().

Task 1: Answer questions from TreeExercise.questions

Answers should be typed in TreeExercise.answers. The purpose of this is to help you understand BSTs before writing any code. This is often a good exercise. Once you understand the "theory", you have a much better chance at implementing the code.

Task 2: Finish up any code you didn't write, and documentation from Project 2.

If there's anything left you need to work on (comments, documentation, etc), please finish that.

Task 3: Add new commands to tester classes

Movie

 No additional commands for Movie. As in Project 2, recall that contains() and remove() now take Movie variables as arguments.

MovieSortedListTester

 Here are the list of new commands. (BNF to be added later)

Also when printing or reverse printing a list, print the message: 

EMPTY LIST
if the list is empty (this is to replace the phrase "THERE ARE NO MOVIES IN THIS LIST").

If you are printing using two ConstIterator and the two iterators point to the same node, then print: 

NO OBJECTS IN THIS RANGE
instead of the previous phrase ("NO MOVIES IN THIS RANGE").

This will make it more general.

BNF

Input BNF 

  <msl_in1>  :=  "SORTED" <seps> RUN <seps> <var> <seps> "=" <seps> <var>
  <msl_in2>  :=  "SORTED" <seps> VERIFY <seps> <var> <seps> "." <seps> 
                    [ "add" | "remove" | "contains" | "update" ]
                    <seps> "(" <seps> "*" <seps> <var> <seps> ")"
where <msl_in1> the two variables are ConstIterator objects, and where the first variable in <msl_in2> is a SortedList<Movie, MovieComparator> object, and the second variable is a ConstIterator object.

Output BNF 

  <msl_out1> := "SORTED RUN " <var> " = " <var>
  <msl_out2> := "SORTED VERIFY " <var> "."
                    [ "add" | "remove" | "contains" | "update" ]
                    "( * " <var> " ) "
                    [ "IS SUCCESSFUL" | "FAILS" ]
where <msl_out1> the two variables are ConstIterator objects, and where the first variable in <msl_out2> is a SortedList<Movie, MovieComparator> object, and the second variable is a ConstIterator object.

Notice the output for this "echoes" (mimics) the input.

MovieArrayListTester

BNF

Input BNF 

  <mal_in1>  :=  "ARRAY" <seps> "RUN" <seps> 
                    [ <mal_in1a> | <mal_in1b> ]
  <msl_in1a>  :=  <var> <seps> "=" <seps> <var>
  <msl_in1b>  :=  <var> <seps> "." <seps> "pushBack" <seps> "(" <seps> 
                    [ <var> <seps> "[" <seps> <udigits> <seps> "]" |
                      "*" <seps> <var> ]
                    <seps> ")"
where the two variables in <msl_in1a> are both Iterator or both ConstIterator objects. For <msl_in1b>, the first variable is an ArrayList<Movie> object, and in the first option, the second variable is a ArrayList<Movie> object, and the variable in the second option is a Iterator or ConstIterator object.

Output BNF 

  <mal_out1>  :=  "ARRAY RUN " [ <mal_out1a> | <mal_out1b> ]
  <msl_out1a>  :=  <var> " = " <var>
  <msl_out1b>  :=  <var>  ".pushBack( " <seps> 
                    [ <var> [ " <udigits> " ]" | "* "  <var> ]
                    " )"
The output pretty much echoes the input. Notice the output BNF looks very similar to the input BNF.

Note: You should convert "NO MOVIES IN THIS RANGE" to "NO OBJECTS IN THIS RANGE" for the corresponding spot.

Task 4: Implement MovieBstSortedList

Here is the MovieBstSortedList Specifications.

You will be provided a MovieBstSortedList.h file. You may wish to use a shorter name when writing this code, as you won't submit this (however, it's easier to write and debug non-templatized code, which is why you're asked to implement this).

Implementing remove()

When implementing remove(), you should use one of the following techniques:

If you use left standard or right standard, you may either choose to copy the data of the replacement node (i.e., the predecessor or successor) and overwrite the node that's being removed, or actually remove and delete the node to be removed, and put the replacement node in its place. (This technique has been discussed in class and lab, and should be in the book).

Remember to handle pred and succ pointers.

Also, one variation when removing a node with one subtree is to always "pull" up the remaining subtree. Otherwise, if you are using, say, left predecessor, you can still use that technique provided there's a left subtree, and pull up the right subtree, if there's not.

In the README, you will describe which remove() method you used.

As you implement each function, document this in BstSortedList.doc. You will find that it's less painful to document if you do it after (or before) each function.

Task 5: Templatize MovieBstSortedList into BstSortedList

You will be given a partial BstSortedList.h and BstSortedList.cpp. The rest should be filled out by you using MovieBstSortedList as a guide.

Task 6: Create MBSLTester which is the tester class for BstSortedList

This class should support all of the operations from MovieSortedListTester from Project 1 and 2 (and 3). Notice that BstSortedList supports the same operations as SortedList (plus a few more).

BstSortedListTester

Task 7: Implement one class from your proposal

Pick a simple class. Create a header file and an implementation file (a .h and a .cpp file). The documentation for this class should be in a file called Foo.myclass.doc where Foo is replaced by the name of your class. Make sure you have implemented a static method called runTestDriver() that tests your class.

Task 8: Write the header, test driver, and sample output for a second class.

Pick a different simple class. This time, write a header file. Leave the data members blank (although you can write it in a comment). Write public methods only. One of the public methods should be runTestDriver().

In the implementation file (the .cpp file), place the implementation of runTestDriver() at the top. For at least two other functions, write pseudocode using comments only. For example: 

int Foo::bar( int x )
{
#ifdef FOO_bar
//    Set temp to x
//    Search through array for x
//    if ( x is found )
//       return index
//    else
//       return -1
#endif
   x++;      // Dummy modification to make compiler happy
   return 0; // Dummy return value to keep compiler happy
}
Also, include the documentation for the class in a file called Foo.myclass.doc where Foo is replaced by the name of your class. This file can leave the data members empty, and not have any private methods.

Finally, write a file called Foo.driver.output where Foo is replaced by the second class name, and represents the output your class should produce, if the runTestDriver() were running. Thus, you are attempting to predict what behavior your class will have, without implementing it.

The purpose of this exercise is to get your to (a) get you to think about how a class behaves, without worrying about the implementation, and (b) forcing that behavior to be "concrete" by writing a test driver for that class.

You don't have to make the output "perfect". It is merely an exercise to get you to think about the class. Finally, the output should be non-empty. Your test driver should (theoretically) produce some output.

REMEMBER: don't implement this class. Just have a header file, the documentation, a simple implementation file.

The implementation file MUST be called Second.cpp. However, the class inside this file should be something reasonable (for example, you might define a Name class inside). The header file (the .h file) should be named Foo.h where Foo is replaced by the name of your class. Second.cpp will #include the header file with the name you've given.

Make sure the implementation file compiles (this may require returning dummy values in functions). Fortunately, you do not need to implement the entire code for the file to compile.

To test your code, we will simply compile Second.cpp to see if it produces a .o file. Clearly, this code won't run, but it's done to make sure you have some meaningful code in your test driver. You should make the same check.

Task 9: Put old code in a file called Review.txt

This file should contain: These should be briefly commented as in: 
// locate() without recursion
 .... code here
// locate() with recursion
 .... code here
// add() without recursion
 .... code here
// copy() without recursion
 .... code here
This will be used to see how your code changed since Project 1.

Task 10: Evaluate three Proposal.two.doc documents

We will post up Proposal.two.doc by sections soon. You should write evaluations on the proposals. To make sure everyone who submitted a proposal gets one, we will come up with a scheme to assign you to two other proposals. This will be posted by end of Spring Break, so wait until then before doing this.

In a file called Proposal.critique, place the following information: 

// Project 3 -- Proposal Critique
//
// Name:     < your name>
// Login ID: < your login>
// Section:  < your section>
//

    I evaluated the following proposals:
       -- AAA
       -- BBB

    I received the following critiques:
       -- bt14299
       -- bt14302
       -- ch14100

Self Critique
-------------
   // comments on what I received

(1) bt14302
------------
   // critique

(2) bt14299
------------
   // critique

(3) ch14123
------------
   // critique

In your self-critique, write comments about what others sent you, if you have time. For example, you might say that you plan to follow the student's suggestions or that you are confused as to what they liked or disliked, etc. It may be that students didn't get time to send it to you. If they did, wonderful, if not, that's OK.

In your critique of other student's proposals, answer the following questions:

You may wish to copy the questions above into the text file and answer them so the person gets the response.

Some final comments

The goal of this task is twofold. You may get ideas about what classes to implement by reading other people's ideas. Also, the other students learn something from your comments. You may, of course, feel free to read everyone else's proposal.

Make sure you identify yourself when sending the proposal.

Task 11: Implement BstMap class. (Extra Credit: +7 points)

This is extra credit. Given a BstSortedList template class and a Pair class, create a BstMap class. This class behaves like the SimpleMap class, but is implemented using pairs and BSTs, which is similar to how map classes are implemented in STL.

Here is the BstMap Specifications.

Debugging Hints

When you write the code, obviously, use a test driver. You need to submit it anyway, so use it.

Also, for ArrayList, it's a good idea to print a message indicating you've gone out-of-bounds, if the index is out-of-bounds. Notice that regular arrays won't tell you such things.

README

The README has been posted in the posting account (and README.directions). (POSTED SOON)

How to Submit Your Project

In order to successfully submit your project, it must pass the primary input and produce the primary output. The primary input will be sent to your project using input redirection. 

   p3 < primary.input
Your program MUST produce the executable p3, EXACTLY, when the command "make" is run with no arguments. Thus, you must use a makefile named exactly "Makefile".

Your program must use cxx with the options -w0 -std strict_ansi. Unfortunately, while we have aliased this for you, it doesn't always work with Makefile, so use the full name in your makefiles.

We will use "diff -bwi" to test your code. This ignores case, treats N blanks as 1 blank, treats N blank lines as 1 blank line. We will also strip all blank lines from your input when matching to ours. However, diff is sensitive to punctuation, number of dashes, etc. so you should attempt to make your output match ours as closely as possible otherwise you may not be able to submit your program. If this is the case (that your program does not submit) you must fix your code until the output it produces matches that of the primary output. Note: "hardcoding" output is a violation of the University's Code of Academic Integrity.

To submit your project you must first combine the following files (and only these files) into a single tar file using the Unix tar command:

You may name your tarfile anything you want, but p3.tar is the suggested name.

NOTE! You should make a backup copy of all your files BEFORE attempting to create your tarfile!!!! You have been warned.

After creating the tar file you should submit that one file using the following command: 

submit p3.tar 3
where p3.tar can be replaced by whichever tar file you have created, and 3 refers to the current project,
See the class syllabus for policies concerning email
Last Modified: Mon Mar 18 20:39:55 EST 2002 		left up down right home

Web Accessibility