Exam #3 - Comp 212

Rice University - Fall 2000

Instructions

  1. The examination is open book/notes.  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 I did not provide you, just give me the appropriate references.
  2. There is no time limit on the exam.
  3. You are not allowed to discuss the exam in any way with anybody beside myslef, your (not-so-humble instructor).
  4. Do not post your questions on the newsgroup.  E-mail me your questions instead. I  will reply to you directly, and if deemed necessary, I will forward my reply to the newsgroup as well.  I will check my e-mail as often as I can to catch your questions.
  5. 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.  The code must be written in perfect Java syntax.  I will compile your code and deduct points for compilation errors.  Feel free to compile and test all of your code before submission.
  6. In all of the questions, feel free to write additional helper methods or visitors to get the job done.
  7. Use the Singleton pattern whenever appropriate.
  8. There are  5  questions for a total of  100  points.
  9. You can submit your exam electronically or by turning in a hardcopy.    Electronic papers must be in ASCII or html format.  Hard copies must be type written, except perhaps diagrams (if any) which can be hand-drawn.

    To submit electronically, email the exam (in ASCII or html format) to dxnguyen@cs.rice.edu.  Your e-mail should include your pledge of honor.

    If you turn in a hard copy of the exam, then

    • Fill in your name on every page of the exam.
    • Fill in and sign the honor pledge below.
  10. The deadline for submission is  Dec. 20, 2000 at 5 PM.
Pledge of Honor

1. The purpose of this question is to assess your understanding of the framework for the binary tree structure represented by the class BiTree and the interface IVisitor.


Write a visitor for BiTree called CountInteriorNodes that computes and returns the number of interior nodes in the host.  An interior node is a node that is not a leaf node.  A leaf node is a node whose left and right subtrees are both empty.  The empty tree has no node and thus no interior node.   Your code should not check for the state of the subtrees.  Use anonymous inner classes whenever appropriate.  15 points

2. The purpose of this question is to assess your understanding of the 2-3-4 tree structure represented by the class Tree234 and your ability to read a specification given in the comments and write implementation code for it.

  1. Rewrite the insertion algorithm for 2-3-4 trees without checking for emptiness.  The original code discussed in the lecture includes the method isEmpty to check for the state of the tree is before making the insertion.  You are now given a revised version  with stub methods for you to complete.   The specification for each of   the methods is stated in the method's comment.  I have updated the code for the 2-3-4 tree discussed in the lecture to include more comments.  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, but do not change the signature of any of the given methods.  Throw an IllegalStateException whenever is appropriate.  30 points

  2. 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.  20 points

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

3. The purpose of this question is to assess your understanding of the function abstraction represented by the interface ILamda discussed in class and your ability to express a given algorithm on the array structure in pseudo-code as a concrete implementation of ILamda.

The following is the description of what is commonly known as binary search, an algorithm for looking up a key object in a given an array of objects sorted in ascending order.

If the high index is less than the low index then return -1 to signify that the key is not in the array.
Otherwise look for the key in the middle of the array. 
If the element in the middle of the array is equal to the key
then return the middle index
else if the element in the middle of the array is less than the key
then repeat the search process on the sub-array to the left of the middle index
else repeat the search process on the sub-array to the right of the middle index.

For our purpose, we assume the array contains Integers and  is indexed from lo to hi.  Write a class called BinarySearch that implements ILambda to carry out the above algorithm.   Decide how to pass the parameters to this class yourself.  Do not use for loops.  Use recursion instead. 20 points

4. The purpose of this question is to assess your understanding the abstract notion of ordering as a strategy and the design of our object-oriented sorting framework.

In our discussion of sorting, we use Integer for the sake of simplicity.  In general we can sort any array of Objects provided we have a total ordering on the set of Objects in question.  The abstract notion of a total order relation is modeled by the abstract class called AOrder discussed in class.   What needs to be changed in our current sorting framework in order to incorporate AOrder as ordering strategy in sorting?  Rewrite the code for InsertionSorter to illustrate your answer.  15 points