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, except code from your current Comp201 classmates.  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 the instructors
of this course (i..e. Nguyen and Wong, but not the labbies) .
3. Do not post your questions on the newsgroup.  E-mail both of 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 and respond to your questions
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. We expect correct Java syntax that compiles without error.
6. You have 5 hours to do the regular questions on the exam plus an additional 0.5 hour if you attempt the extra credit problems.
7. 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 upload page under "Exam3". 
8. The deadline for submission is  Wednesday, May 5, 2004 @ 10:00 AM.

• Download the provided code: Comp201Ex3.zip, which contains all the exam materials in a directory called Comp201Ex3.

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

• Be sure to load all the files for a particular problem and compile them all. Do not mix files from different problems in DrJava!
  

• Your code is required to pass all the supplied JUnit test code! Note: sometimes DrJava does not appear to run all the tests, so click the "Test" button several times to make sure that all the tests actually run.

• All required work is in sections labeled with "TODO". Doing a "Find" across all files for "TODO" will find all the places you need to work on.

• Zip up the entire Comp210Ex3 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 BRING IT TO CLASS ON THE DUE DATE.

Problem 1: SmartArray Processing (15 pts total + 5 pts extra credit)

Using the SmartArray system (see lab14), implement the method remDup that removes all duplicate elements in the SmartArray. Two objects, x and y, are defined as being duplicates if x.equals(y) returns true.

SmartArray remDup()-- For each element, remove any duplicates of it in the array.

• Write a loop that goes through every element of the list.
• Inside that loop, write a loop that removes any duplicates of the current element in the outer loop.
• Which direction should the inner loop traverse the array? From where to where? Think about which element is referenced by an index after you remove that index.
• Write the algorithm without the return SmartArray first, then add that feature in. How do you insure that any duplicate is only recorded once?

You may assume that the SmartArray does not contain any null values in its apparent array.

5 pts extra credit if you implement your algorithm using a variable shift mechanism (use remDupBetter) to minimize the number of traversals of the array. You may implement both remDupBetter and remDup if you are not sure if one technique will work. You are not required to have both implementations.

Problem 2: A State-ful RAC (20 pts total)

This is very similar to the RAC presented in class except for one very important difference: the IRAContainer.isEmpty() method is absent.

A RAC behaves differently when it is empty or non-empty. Therefore, it makes sense for a RAC (IRAContainer) to be able to accept a two-case visitor.

a) (5 pts) Write IRACVisitor interface for visitors to the above RAC. A skeleton file for the class has been provided.

b) (10 pts) Write the code for the execute method of LRSRAContainer (ALRSFactory$LRSRAContainer in the above UML class diagram which does not show the execute method).

• You do not need to define any new classes to accomplish this! (Anonymous inner classes derived from existing classes are ok.)
• Look carefully at what is already there to find what you need.
• A skeleton of the execute method has been provided.

c) (5 pts) Write an IRACVisitor called rac.visitor.IsEmpty that returns Boolean.TRUE if the RAC is empty and Boolean.FALSE if it is non-empty. A skeleton file for IsEmpty has been provided as well as a test file.

Tip: To access the outer LRSRAContainer object from within an anonymous inner class inside a LRSRAContainer, use the syntax LRSRAContainer.this.

NO CONDITIONALS ARE ALLOWED IN YOUR SOLUTION! Think simply and directly!

Problem 3: Counting Elements in a Binary Tree (25 pts total)

Write a BiTree visitor, called CountGreaterThan, for execution on a binary search tree (BST) that counts all objects greater than a given key.

• The key is passed as a parameter to the visitor.
• An Integer representing the total number of data objects in the host tree that are greater than the given input key is returned.
• The return result for a host that is an empty BiTree should be zero.
• Assume the host tree contains Comparable objects. If x and y are Comparable, then x.compareTo(y) is less than zero if x < y.

Finally, to receive full credit, your visitor must visit the fewest possible nodes.

The brs package along with some of the visitors developed in class has been provided, including a skeleton of the CountGreaterThan class.

A test file has been provided.

Recommendation: Take a piece of paper and draw a tree on it, tracing what you want the algorithm to do under various circumstances. Be sure to consider all possibilities!

Problem 4: Sink Sorting (20 pts total)

Consider the following technique for sorting called a "Sink Sort" . (See the demo)

Initially:  4 5 1 3 2 ("top" is on the left at index 0, "bottom" is on the right at index 4)

Split all the array into one element arrays:  4  5  1  3  2

2 is already sorted:         4  5  1  3  2

Sink 3 until at right of 2:  4  5  1  2 3

Sink 1-already there :   4  5  1 2 3

Sink 5 until at right of 3: 4  1 5 2 3

                 4  1 2 5 3

                 4  1 2 3 5

Sink 4 until at right of 3: 1 4 2 3 5

                 1 2 4 3 5

                 1 2 3 4 5

Basically the idea is that the next number is "sunk" by swapping places with its adjacent number on the right until it is smaller than the number to its right.  According to Merritt's split-sort-sort-join model of sorting, Sink sort is an easy split/hard join algorithm.  The code for split is simply:

protected int split(Object[] A, int lo, int hi){
    return (lo + 1);
}

Write the code for the join method of Sink sort as described in the above. 

/**
* Given A[lo..s-1] and A[s..hi] sorted, 
* merges the two sub-arrays so that A[lo..hi] is sorted.
* Here s == lo + 1 (see split).
* The merge should be done in such a way that the numbers in A[lo..s-1]
* sink by swapping places with their adjacent right (higher indexed) neighbors until each
* is smaller than the number to its right, or until hi is encountered.  
*/
protected void join(Object[] A, int lo, int s, int hi){
    // Students to write code.
}

Notes:

• lo and hi are inclusive
• The sinking stops when the value being "sunk" is less than the number at the higher index, which is the same as saying that the two values being compared are already in order.
• The sinking stops when hi is encountered. Be careful not to overrun past hi! You may encounter it sooner than you think.
• Swapping two values in an array always requires the use of a third, temporary variable.
• The graphical sorting framework demonstrated in class (support for SinkSorter has been added) has been provided and you may use it for testing purposes. A SinkSorter.java skeleton file is provided.
• AOrder.lt(x,y) returns true if x < y.
• To create a boolean expression that involves two conditions, specify each condition and use the logical AND operator, "&&", between them. See the InsertionSorter code for an example.
• Using either a for loop or a while loop is acceptible.
• DO NOT HARDCODE THE COMPARISON!!! Use the protected abstract order strategy, aOrder, declared in the abstract sorter class, ASorter.
• To run the application, run the main method in Sorter.Application1.
• A test class has been provided for SinkSorter, Sorter.test.Test_SinkSorter
  

Problem 5: BiTree to Array (20 pts total + 5 pts extra credit)

One very interesting application of binary trees and arrays is to implement a binary tree as an array. Such a marriage would imbue the binary tree with the speed and random access capabilities of an array, something that could be quite useful if the binary tree was a binary search tree, or something of that ilk (stay tuned next semester!). Of course, it would also come with the price that an array pays, namely the inability to mutate its structure. But let's forge ahead anyway...

Consider the following binary tree:

We can put this tree into an array as such: [A, B, C, D, E, F, G]

This ordering technique has the following interesting properties:

Given an index of the parent (root) node, idxRoot,

• the index of the left subtree is idxLeft = 2*idxRoot + 1     (e.g. A->B, B->D, C->F)
• the index of the right subtree is idxRight = 2*idxRoot + 2    (e.g. A->C, B->E, C->G)

Convince yourself this is true for any element of the binary tree, no matter how big it is.

If the tree is not "full" then we simpy leave nulls in the array:

[A, B, C, null, E, F,null]

See the test class for more examples.

The array must therefore be sized for the worst case scenario: Given the maximum height of the binary tree, hMax, then the required size of the array is (int)Math.pow(2, hMax)-1

Write an IVisitor called BRS2Array that returns a new array of Objects filled with the elements of the host BiTree where the elements are located in the above ordering scheme.

Notes:

• A skeleton of the BRS2Array class and corresponding test case class have been provided.
• Executing BRS2Array on an empty BiTree should return an empty Object array.
• The root node's data always go into index 0 of the array.
• Since all subtrees' data goes into mathematically calculated locations in the array, consider using a helper visitor.
• You may use any previously written algorithm from class, lab or homework.
• However, you should minimize the number of named classes used. A valid reason for using a named class is that it represents a fundamentally distinct operation from BRS2Array.

5 pts Extra Credit: Write a the body of util.ArrayUtil.equals() such that it returns true if the two given Object arrays are equal and returns false if they are not. To test your code, substitute in the use of this static method in the body of Test_BRS2Array.isEqual() and re-run the test cases.

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

©2004 Stephen Wong and Dung Nguyen