Comp 212 - Extra Credit Project

Rice University - Fall 2001

1. The project is open book/notes.  It is absolutely optional and has no negative effect on your final grade.  You are allowed to consult any written materials available under the sun, except code from your current Comp212 classmates.  If your code is based on materials that we did not provide you, just give us the appropriate references.
2. You are allowed and encouraged to work in teams of at most two people.  All team members will share the same grade.
3. The total grade of this project will added to the lowest exam grade of each of the team member, not to exceed the maximum grade of the corresponding exam.
4. You are not allowed to discuss the project in any way with anybody beside your team member and the instructors (not the labbies) of this course.
5. Do not post your questions on the newsgroup.  E-mail us, dxnguyen@rice.edu and swong@rice.edu, your questions instead. We  will reply to you directly, and if deemed necessary, we will forward our reply to the newsgroup as well.  We will check our e-mail as often as we can to catch your questions.
6. Write your code in the most object-oriented way possible, that is with the fewest number of control statements and no checking of the states and class types of the objects involved.
7. Create a subdirectory called xtra in your Comp212 directory for the project.  This subdirectory should contain:
   • An ASCII (or html) README file to indicate what you have and/or have not done, and to point out specific details that you feel we need to know when grading your work.
   • UML diagrams with javadoc of all your class designs.
   • All the Java source code necessary to compile and execute your test code.
8. The deadline for submission is  Dec. 16, 2001 at 11:59 PM.  No late submission will be accepted.  No extension will be granted.  Please e-mail us, dxnguyen@rice.edu and swong@rice.edu, as soon as your project is ready to be graded.

Project Description

1. The original code for 2-3-4 trees (Tree234 ) discussed in the lecture includes the method isEmpty() to check for the state of the tree before making the insertion.  Remove isEmpty() from the 2-3-4 tree class and rewrite the insertion algorithm for 2-3-4 trees without checking for emptiness.  Feel free to re-use the given existing code in any way you see fit.  Feel free to add any non-public method to the classes.  Throw an IllegalStateException whenever is appropriate.  Write appropriate test code.  3 points
2. Add a public method called boolean find(Integer n) to look up a given Integer n and return true if n is found in the 2-3-4 tree, false otherwise.  Write appropriate test code. 1 point.
3. Add a public method called boolean remove(Integer n) to remove a given Integer n.  If n is not in the 2-3-4 tree before the removal, then return false, otherwise remove n from the 2-3-4 tree and return true.  Feel free to add non-public helper methods.  Write appropriate test code.  4 points
4. Add the method toString() to the class Tree234 and appropriate methods to the node classes to compute and return a String representation of Tree234 in the way similar to that of the toString() method for the binary tree class BiTree.   Feel free to add non-public helper methods.   Below is an example of the required String representation.  2 points

-5  5
|_ -10
|  |_ []
|  |_ []
|_ 0
|  |_ []
|  |_ []
|_ 15  20  25
   |_ []
   |_ []
   |_ []
   |_ []