Instructions

1. The examination is open book/notes.  You are allowed to consult any written materials available under the sun that was published or posted before the start of the exam.  If your code is based on materials that we did not provide you, just give us the appropriate references.
2. You are not allowed to discuss the exam in any way with anybody beside Dr. Wong .
3. Do not post your questions on the newsgroup. Contact Dr. Wong (swong@rice.edu) to let him know when you are taking your exam so that you can set up an IM session to get your questions answered.
4. 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 in any way.
5. You have 6 hours in which to complete the exam from the time that you commence.
6. Submission instruction: you must submit your exam in two ways.
   •  a hard copy with all answers in typewritten form, except perhaps diagrams (if any) which can be hand-drawn.  Be sure to print your name and sign the honor pledge.  You do not need to print out the supplied code unless you have modified it.
   • Zip your work together with your honor pledge (included in the provided code) and upload to the usual Owlspace upload page under "Exam3". 
7. The deadlines for submission is:
   • for graduating seniors: Wed, May 3, 2007 @ noon
   • for non-graduating students: Mon., May 7, 2006 @ noon.

• Download the provided code: exam3s07.zip, which contains all the exam materials in a directory called Exam3.   Each question has its own project, perhaps multiple projects for the different sub-sections.

• Put all the code for each problem in its respective subdirectory, e.g. Prob1, Prob2, etc.

• We provide some sample test code for you to check your answers.  However do not get hung up on fixing your code to compile and pass the test code.  The given test code are not necessarily thorough.  We will give partial credits to code that do not compile but are clear enough to show your ideas on how to solve the given problem.

• Zip up the entire Exam3 directory including the filled-out Honor Code file and hand it in using the usual upload page.

PRINT THIS PAGE AND ALL YOUR CODE, WRITE AND SIGN YOUR HONOR PLEDGE AND SLIP UNDER DR. WONG'S DOOR (DH3102) ON THE DUE DATE.

You must supply both the electronic and paper copies of your exam in order to for your exam to be graded!

Problem 1: B-Trees  (50 pts total)

An interesting variation of a binary search tree is the "B-tree", which looks like an n-ary tree ("n" children trees) but with multiple data elements at each node.   In the diagram below (may show up better in Internet Explorer), we see a root node with 3 data elements, which has 4 child trees.  The child trees have various numbers of data elements in their root nodes with corresponding numbers of child trees below them (not shown).

• The key thing here is that if there are n data elements at a node, then there are n+1 children below that node.
• Conceptually, we can think of the children as being attached between the data elements of a node.
• As always, a B-tree can be either empty or non-empty.

B-trees are very commonly used to store data in databases and file systems.  For instance, the "sectors" one hears about in the formatting of hard disks are actually the data arrays of B-trees.

We will be implementing an immutable B-Tree.

To implement a non-empty B-Tree, we will first start off with a collection of interrelating interfaces to describe

• an abstract B-Tree (IBtree), 
• an empty B-tree (IMTBTree),
• a non-empty B-tree (INEBTree),
• a factory to instantiate B-trees (IBTreeFac)
• a visitor to a -Tree (IBTreeAlgo) 

(Note: in the following diagram, the vararg nature of the input parameters for the visitor and execute method is not shown.)

In the supplied code, you will find an implementation of IBTreeFac called BTreeFac that implements INEBTree by using one array to hold the data elements and another to hold the references to the children trees.   You will also find a sample visitor, ToString, that returns a String representation of a B-tree that is very similar to the vertical tree representation we used in class for a binary tree.

Things to note about the supplied code:

• The length of the children array is assumed to be one more than the length of the data array.  That is, the last element of the children array  is
  children[data.length].
• When processing the data and children arrays together in a single loop, one more step must be taken after the end of the loop to process the last element of the children array because it is longer than the data array.
• INEBTree.getData() and INEBTree.getChildren() return copies of the data and children arrays respectfully.   This helps preserve the immutable nature of the tree since arrays are fundamentally mutable and if a reference to the actual stored arrays was returned, then the tree could be mutated by setting any element of those arrays.
• Note how one often must check if the arrays are either empty or the wrong length before proceeding.

Prob. 1.a:  (15 pts) Counting the elements in a B-Tree

To start off, let's try a simple algorithm to count the number of data elements in a B-Tree.   To do so, you will complete the skeleton code for the CountElements visitor.

Algorithm description:

• Empty tree:   How many data elements here?
• Non-empty tree:
  • How many data elements at this node?
  • Use a loop to count the elements in the children trees.
  • Return the total.

Think simple!   Don't make this algorithm harder than it is!

The unit test code has been provided.

Prob. 1.b: Search Tree Criteria for B-Trees

Continuing along with the analogy with a binary search tree, we can define a search tree criteria for B-trees:

For any data element at index i, then all the elements in the entire child tree at index i are less than the data element value and all the elements in the entire child tree at index i+1 are greater than the data element value.

That is,

{all elements in children[i]} < data[i] < {all elements in children[i+1]}

In the above B-Tree diagram, we would thus get:

{all of D-E} < A < {all of F} < B < {all of G-H-I} < C < {all of J}

So we see why it is useful to think of the child trees as being "sandwiched" between the data elements (or the data elements being sandwiched between the child trees, if you prefer).

There is also one more criteria that we now need to explicitly impose because it was implicit for the binary search tree:

The number of data elements in any given node of the tree is limited to a maximum value, called the "order" of the tree.

For a binary search tree, the order was implicitly set to 1.   In the above example, we could surmise that the order is 3.   Note that this implicitly limits the number of children to order+1.

(Note: in the literature, you will often see the order of a B-Tree defined as the maximum number of children, not the maximum number of data elements at a node.  While mathematically equivalent definitions, plus or minus one, we find it much more conceptually useful to think of the limit on the data elements because order = 0 is the empty tree in that case.)

Thus, an empty B-tree satisfies the search tree criteria.

We will now proceed to develop an algorithm, called InsertSearchTree, to insert data elements into a B-tree search tree that preserves the search tree criteria.

Prob. 1.b.i:  (15 pts) Utility method to calculate the insertion index.

We always want to break our development process down into as small and isolated chunks as possible.   So, let's concentrate initially on a simple method to calculate the index of the insertion point of a new data element with regards to a given data array.  

A returned  insertion index of 0 means that the new data element is smaller than any existing elements in the data array.  An insertion index value of 1 means that the new data is larger than the first element but smaller than the second.  A  insertion index value of  2 means that it is larger than the second element but smaller than the third and so on.   A returned insertion index of the data array length means that the new data element is larger than any element in the data array.

You are to complete the getInsertIndex method in the InsertSearchTree class.

The InsertSearchTree class utilizes a Comparator object just like the binary search tree to determine the ordering of any given pair of data elements.

• Since the given array is assumed to already be ordered as per the Comparator object, _comp, you just need to find the lowest index for which the data element in the array is larger than the new data element.
• When you find that index value, simply break out of the processing loop by returning the index value.
• If the new data element is larger than any element in the given array, the index value where it belongs is array.length.

The unit test code is provided.

See note at top of exam if you get "Uncheck type warnings".

Prob. 1.b.ii: (20 pts) The rest of the Search Tree Insertion Algorithm

Now we can complete the search tree insertion algorithm.   You are to complete the mtCase and neCase methods of the InsertSearchTree class.

The insertion index value can be thought of as either the index where the new data element is inserted into the existing data array or  is the index of the child tree that would hold the new data.

Since the number of data elements at any given node can vary from nothing (empty tree) to the order of the search tree, when we insert a new value, we will either

• recursively insert the value into the child trees, ala a binary search tree, if the child tree is non-empty, or
• if the child tree is empty and the number of data elements is not at its maximum, we will insert (how do you do this?) the new data element directly into the data array at that node.

The InsertSearchTree visitor is executed along with a single input parameter, the new data element.    The order, comparator, and IBTree factory are passed to its constructor.

Algorithm description:

mtCase:

1. Use the saved IBTreeFactory to instantiate a new INEBTree that has exactly one data element, params[0], and whose children are all empty.

neCase:

• First do the following:
  1. Get a copy of the host's data array.
  2. Get a copy of the host's children array.
  3. Calculate the index of the insertion point given the new data element and the data array.
• The number of data elements is less than the defined order
  • The child tree at the insertion index is empty: We can insert the new data directly into the host's data array.
    1. Allocate new, empty arrays for both the data and children trees that are one longer than the existing arrays.
    2. Place the new data element into the new data array at the insertion index.
    3. Place an empty tree into the new children array at the insertion index.
    4. Copy all the elements from the old data array and old children arrays over to the new arrays, skipping over the new data and child.
       • This can be done with a single loop.
       • Initialize two index counters, one for the old array and one for the new array.
       • For the loop conditional, check if the index counter for the old array has gone past the end of the old array.
       • Increment both counters every time around the loop.
       • The above will cause the old and new index counters to start and count together, which is fine until the insertion point is encountered.
       • If the insertion index equals the old index counter, increment the new index counter by one.  This will cause the insertion point to be skipped, because we already set it above.
       • In any case, copy the value at the old index counter from the old arrays to the location at the new index counter in the new arrays.
       • Don't forget the last child element in the array!  After the loop, copy the last element of the old child array to the last element of the new children array.   Note that the index values of the last elements are not the same between the old and new children arrays!
    5. Return a new INEBTree created by the IBTreeFac using the new data and children arrays.
  • The child tree at the insertion index is non-empty: We must recursively insert the new data element. and rebuild the host.
    1. Replace the value of the child tree at the insertion point in the copy of the children array with the recursive result of inserting the new data element into that very child tree.
    2. Return a new INEBTree created by the IBTreeFac using the copies of the data and the (now mutated) children arrays.
• The number of data elements is equal to (not less than) the defined order: We must recursively insert the new data element. and rebuild the host.
  1. Replace the value of the child tree at the insertion point in the copy of the children array with the recursive result of inserting the new data element into that very child tree.
  2. Return a new INEBTree created by the IBTreeFac using the copies of the data and the (now mutated) children arrays.

Hints:

• Follow the above descriptions very carefully!   Keep asking yourself:  "Does my code match the description of the algorithm?"
• Don't put in code that doesn't exist in the description!
• To instantiate and initialize an instance of an array of MyClass objects in one step, you can use the following syntax:   
  new MyClass[]{ instance1, instance2, etc }
• Whenever you need an empty tree, just use the stored convenience reference, _mt, that references the empty tree made by the stored factory.
• How do you determine if a child tree is empty or not?
• Be sure that you know to what object "this" refers.

Teaser: Next semester we will see a much fancier, more powerful and  mutable B-tree implementation whose search tree insertion code is not much longer than the above code and which will simultaneously balance the tree for optimal performance and even repair the tree if it is damaged!

Problem 2:  A Fancier RAC and TAMU (40 pts total)

Prob. 2.a:  RAC's with both insertion and retrieval policies.

The Restricted Access Containers (RAC's) discussed in class were slightly limited because they were based on two assumptions:

1. The priorities or retrieval order of the stored elements was static and did not change during the time that the elements were in the RAC.
2. The relative insertion and retrieval speeds were irrelevant so the system was written for slow insertion but fast retrieval.

But neither of the two above assumptions are always true, so in order to address these shortcomings, we need to modify our RAC implementation. 

A simple way to fix the problem is to use both insertion and retrieval strategies (policies).   Looking specifically at our LRStruct-based implementation, this means supplying an IAlgo visitor to determine where in the internal storage list, a newly inserted ("put") element is saved as well as another IAlgo visitor to retrieve ("get") the desired element from the list.

See note at top of exam if you get "Uncheck type warnings".

Prob. 2.a.i.   (10 pts) Modify ALRSRACFactory.LRSRAContainer

Modify the e ALRSRACFactory.LRSRAContainer class (inside the ALRSRACFactory.java file) so that it's get() and peek() methods use the _retrieveStrategy to obtain the desired value from the _lrs list.    (Replace the original get() and peek() code that has been provided for your reference.)

• IMPORTANT:  The retrieval strategy is defined as returning the list whose first contains the desired element, not the element value itself!   Why do think this was defined this way?
• get() and peek() return the desired data value, not lists.
• Note that if the get() or peek() algorithms are written with too many lines, they may cause the comparative speed test between LRSQueueFactory and LRSQueue2Factory in the next section to fail.
• The constructor for  LRSRAContainer has already been modified for you.
• Note that in this new formulation, the behavior of the RAC when get or peek is performed on an empty RAC is now handled by the retrieval policy not by the RAC itself .  This means that in some cases, a user could choose to throw an exception if the RAC is empty, or simply, for instance, return some well-defined "null" value.   We will utilize this capability in the next section.
• The factories for queues, stacks, priority queues and a random RAC have already been modified to use the new ALRSRACFactory.
• Test code has been provided to test the modified RAC using the supplied modified queue factory.

Prob. 2.a.ii.   (15 pts) A new, fast insertion queue

Create a new implementation of a queue, called LRSQueue2Factory, that unlike the existing queue implementation, has a fast, order 1, O(1), insertion but a slow, order N, O(N), retrieval.

• The skeleton for the LRSQueue2Factory class has been provided.   You will need to fill in the empty and non-empty cases for the insertion and retrieval policy visitors.
• For fast insertion, where should you always put the new data?
• Where is the data to be retrieved?  What algorithm do you need to remove it?  Is this familiar?
• Attempting to remove data from an empty RAC should throw an IllegalStateException.
• The test code for LRSQueue2Factory has been provided.
• Note that the last test, the speed comparison between the new and old queue formulations may fail if too many lines of code were used to write the get or peek method of ALRSRAContainer.

Prob. 2.b: (15 pts) Retrieving dynamically changing entities from a RAC

Last Revised Thursday, 03-Jun-2010 09:50:26 CDT

©2007 Stephen Wong and Dung Nguyen