computer science II
c m s c 214  
f a l l   2 0 0 1  

Project 3

Due Thursday, Nov. 1, 11:59 PM

Project 3 FAQ

Latest Posting

This was posted October 25, 2001.

Checklist

A link to a checklist will be provided. You should read the checklist several times, but especially before submitting your project. (To be posted soon)

Project 3 Checklist

Purpose

The purpose of the Project 3

  1. To get practice using recursion.
  2. To write a binary search tree with predecessor/successor nodes using nested classes.
  3. To finally see minor CMSC 214 Style Specifications.

Hardcoding is a Violation of Academic Integrity

If you "hardcode" the output, i.e., attempt to produce the primary output by using print statements or other similar techniques, or use simplified data structures (for example, using an array when you've been asked to use a binary search tree), you may be receive a 0 on the project, and be brought up on charges of academic dishonesty.

Academic Integrity Statement

Any evidence of unauthorized use of computer accounts or cooperation on projects will be submitted to the Student Honor Council, which could result in an XF for the course, suspension, or expulsion from the University. Projects are to be written INDIVIDUALLY. For academic honesty purposes, projects are to be considered comparable to a take-home exam. Any cooperation or exchange of ideas which would be prohibited on an exam is prohibited on a project assignment, and WILL BE REPORTED to the Honor Council.

VIOLATIONS OF ACADEMIC HONESTY INCLUDE:

  1. failing to do all or any of the work on a project by yourself, other than assistance from the instructional staff.

  2. using any ideas or any part of another student's project, or copying any other individual's work in any way.

  3. giving any parts or ideas from your project, including test data, to another student.

  4. having programs on an open account or on a PC that other students can access.

  5. transferring any part of a project to or from another student or individual by any means, electronic or otherwise.

  6. publishing any of your code publicly (e.g., via a webpage) which other students can access, even if the project is already due.

IT IS THE RESPONSIBILITY, UNDER THE UNIVERSITY HONOR POLICY, OF ANY STUDENT WHO LEARNS OF AN INCIDENT OF ACADEMIC DISHONESTY TO REPORT IT TO THEIR INSTRUCTOR.

Style Guide

Here it is

FAQ

We will provide corrections and announcements, as well as "frequently asked questions" on the Project 3 FAQ page.

Project Overview

You will create a binary search tree template class.

The program you write will support commands for printing out information of the tree, to verify a tree has been constructed.

As with previous projects, this project will be released in parts.

  1. You will be provided Movie.h, Movie.cpp, and MovieBstSortedList.h.
  2. Implement MovieBstSortedList.cpp. This is NOT a template class. You can use MovieBstSortedListDriver.cpp to test the code. This is a minimal driver. You should add more to test the class fully. The more you can test, the fewer bugs you should have.
  3. You will be provided a minimal ObjBstSortedList.h, which will be a template class version of MovieBstSortedList.h, where Movie will be replaced by Data and string (which is the movie's title), will be replaced Key. Both Data and Key are template type parameters.
  4. Data should contain a key, and a getKey() method to retrive that key. The BST will be sorted based on that key. You should also define relational operators such as < and ==. This will allow you to compare objects by keys using two different methods.
  5. Implement ObjBstSortedList.cpp, a template class, by converting MovieSortedList.cpp to a template. (One reason to write a non-template class and convert it, is that it's easier to debug non-template classes). Make sure that it works with the ObjBstSortedListDriver.cpp, the driver. This should produce the same output as MovieBstSortedListDriver.cpp.
  6. Finally, write a BstSortedList.cpp, which you will use in BstSortedList.h to replace SortedList.h. You can make this version handle pointers.
  7. The ArrayList class should remain the same. (Of course, debug it as needed).
  8. Replace the SortedList object with the BstSortedList object in Team. Make sure your code still works with the P2 primary.

NOTE: It's a good idea to test the BstSortedList classes thoroughly, before incorporating it into your other classes. Don't implement new commands until the changes have been made.

Files Provided

Files That Aren't Needed in Project 3

You shouldn't need the following files:

You shouldn't need to submit it. However, these files may be used in Project 4.

Files You Still Need from Project 2

Pretty much everything else used to create p2, the executable.

Files Provided

Files You Write

Background Reading

Background readings may be provided.

Commands

There are the additional commands. You may need to refer to P1 and P2 project descriptions for other definitions of BNF not mentioned here.

No STL

In this project, you won't use any STL. If you do, you will lose 100 points. The only exception is strings. You can use strings, since they technically part of STL. (Avoid using vectors, algorithms, etc).

Assumptions

  1. The only new assumption is that robots can't join any team.
  2. Of course, just as last time, if there are no relevant error messages, you can assume that the error won't occur. However, this doesn't mean you shouldn't produce error messages of your own (which indicate when something has gone wrong). You should do that for debugging purposes.
  3. You can assume a Robot can't drop any items if it's not in a room. The same can be said of a Player. Appropriate error messages will be provided in the BNF.

Description of Files

Movie.h/Movie.cpp

Same as last time.

MovieBstSortedList.h

This stores a BST containing BstMovieSortedList::Node objects. Each of these objects contains a Movie object stored by value.

Node nested class

Most of these operators should be familiar to you now, so they won't be explained.

The important parts to note:

Iterator nested class

The iterators are nearly identical to the Iterators of SortedList. However, instead of using next and prev pointers, you use succ and pred pointers. There's also an overloaded -> operator.

MovieBstSortedList main class

Most of the methods are the same as before. However, because this is a BST, the implementation is different. locate() should be implemented using recursion.

In general, you should have private helper functions to implement recursive functions.

Special Methods

For each class you write, you must determine whether to write the following methods: Recall that all three methods should be written as a group or not at all. You should use these methods if the class allocates dynamic memory via "new" and deallocates via "delete".

If it is NOT necessary to implement these methods, then do NOT implement. By necessary, this means the class would behave incorrectly (especially, if, say, only the destructor were defined).

If you do choose to write these three methods, you should write the following helper methods.

and use these methods to help implement the default constructor, destructor, operator=, and copy constructor.

Recursive Functions

A recursive function is defined as follows.

Requirements/Restrictions

The following requirements/restrictions are specific to this project.

  1. The following functions should be recursive:
    • locate()
    • add() (using locate())
    • remove() (using locate())
    • contains() (using locate())
    • clear() (using freeMem)
    • freeMem() (using freeMemRec, a recursive helper function)
    • height()
    • first() and cfirst() (using findMin)
    • last() and clast() (using findMax)
    • findMin(), findMax()
    • visitPreorder(), visitInorder(), visitPostorder()
  2. You must NOT use a separate doubly linked list for handling predecessor/successor. The node is both part of a tree (using left/right pointers) and a doubly linked list (using pred/succ).
  3. You should use predecessor/successors to implement iterators.
  4. end() and cend() should set "curr" to NULL.

The following requirements/restrictions should be observed.

  1. The program should compile with g++ with the -Wall option. You may use cxx to test, but make sure it runs with g++ as well.
  2. You should comment code. You will be given instructions on how to do this later on.
  3. You should use namespaces. In particular, in your .h files (ONLY), all of objects should
  4. You should use namespaces. In particular, in your .cpp files, you should write "using namespace std".
  5. Hardcoded outputs will be severely penalized.
  6. Write helper functions. You will gain more credit if you do. They should be clearly labelled as helper functions.
  7. Your program must create an executable called exactly p3. If you create other executables, the "main()" must be in a file with the name "Driver" at the end. For example, if you wish to create a "BstSortedListDriver.o" that has a "main()", that is fine. However, a file such as "test.cpp" should not have a "main()". This will allow us to test your files.

README

Submit a README with your files. Add the usual stuff:

Extra Credit

For 5 points extra credit, reimplement sort214 using quicksort. You may need to find an implementation of this algorithm from some book. You are permitted to search on the web to do this. However, you are not permitted to post your solutions (or read other's posted solutions). Of course, the actual version uses array elements. You will have to adapt it to use pointers.

How to Submit Your Project

As with Project 1
submit p3.tar 3 SUBMIT

Your executable must be called exactly p3. Any other name will cause your program not to be submitted.

You can name the tar whatever you want. However, you should wait until a primary input and output have been posted. (If you submit before that, then if your project does not pass the primary input/output, you will receive a poor grade on the project, most likely a zero).

Please do not submit until a primary input and output have been posted. If you do, you may receive a 0 for failing to pass the primary.