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, 2008 @ noon
   • for non-graduating students: Mon., May 5, 2008 @ noon.

• Download the provided code: exam3s08.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 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  (35 pts total)

(This problem is a continuation of Prob. 1 from Spring 2007 exam.  The solution to that problem is included in the supplied code.)

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 B-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.

Traversing a B-Tree using a Restricted Access Container

In this problem we will explore how a RAC can be used as a memory device to help us traverse data structures in different ways.  It should be noted that this problem isn't really intended to show any particularly useful traversal path, but to show how RACs are used in traversals to produce wildly different traversal paths with the same code by simply substituting a different type of RAC.

Traversing a data structure using a RAC is overall, quite simple:

1. Throw the host data structure itself into the RAC.
2. Pull an element from the RAC
   1. Process whatever parts of the data structure you desire in some manner (read: run some sort of lambda on it).  
   2. Throw any parts of the data structure that are not immediately being processed into the RAC.   This includes, possibly, the host data structure itself and any children or peer data structures.  Note that there may not be any parts to throw into the RAC, e.g. you're in an empty data structure.
   3. Check if the RAC is now empty
      1.  Empty: You're done because there's nothing more to process.   
      2. Not Empty: Recur to step 2 above.

Notice that the traversal of a data structure is more of an algorithm on the RAC than it is an algorithm on the data structure itself.

B-Trees create a little bit of a problem here however because B-Trees contain those distinctly non-OO, non-recursive arrays that hold the peer data and the children B-trees.   That means that it is very difficult to only process, say one of the data elements, and equivalently specify the rest of the unprocessed data elements.   That is, the elements 1 through n-1 of an array of n elements cannot be described or referenced in a manner relating to the entire array and/or the first (0'th) element.   Part of an array cannot be referenced as an array (at least without copying it to a new array).

So what we need to do is to create a utility wrapper class that will enable us to uniformly treat both entire B-Trees, such as the children trees, and single data elements, such as the various peer data elements at the root of a B-Tree. 

IRACElt is the abstract interface that will represent the type of objects we will throw into ("put()") and pull out of ("get()") our RAC.   IBTReeElts will hold entire B-Trees that have yet to be processed, which could be either empty or non-empty.   IDataElts will hold only non-empty B-Trees with an additional index value that will indicate which data element at the root level is the one to be processed.

IRACEltAlgo is the visitor to an IRACElt, with cases corresponding to IDataElt and IBTReeElt hosts, thus allowing us to properly process it without having to check which sub-class it actually is.   IRACEltFactory will be used to create instances of IDataElt or IBTreeElt.    RACEltFactory is a concrete implementation of IRACEltFactory.

The RAC will thus only ever hold IRACElt objects.

We will need to modify the above pseudo-code for traversing a B-Tree with a RAC such that anything we put into the RAC is first inserted into an IRACElt object using the methods of an IRACEltFactory before putting it into the RAC.

As far as processing any given data element, as in step 2.a above, we will pass along an ILambda that will be applied to the data element, as in lambda.apply(data_element).    The supplied test code, RACTraverse_Test, uses a lambda that simply takes the String representation of the data element and appends it onto a running result String, called result, so that in the end, the result String will show the order in which all the data elements were processed.  

A more detailed look at the algorithm:

You are to write an IBTreeAlgo called RACTraverse that will traverse a B-Tree, using a given RAC and applying a given ILambda to every data element in the tree.

• inp[0] = an empty IRAContainer to be used by the algorithm.
• inp[1] = an ILambda to be applied to
• RACTraverse will return false if the B-Tree is empty, i.e. no data elements were ever processed and true if the B-Tree was non-empty and at least one data element was processed.    
• The effect of applying the ILambda to a data element is assumed to be purely a side-effect, so no return value with respect to that application is required.  For instance, in the test code, applying the lambda will simply modify the private result field of the test class.

The algorithm is follows:   Since the traversal is really an algorithm on the RAC, the first thing to do is to load the RAC with the tree if the tree is non-empty.

• IMTBTree:  Nothing to do, return false.  (Already completed in supplied code)

• INEBTree:   Need to process this tree, but the RAC is starting out empty.

1. Wrap the host tree in an IBTreeElt and load it into the given, empty RAC.  
2. Since the RAC is known to now be non-empty, get the first IRACElt element from the RAC and delegate to it (Remember that IRAContainer.get() returns type Object!).   You will need to reference this algorithm later, so you may want to use the old "MyHelperClass myHelper = this;" trick (substituting in the appropriate class name, of course).

• IDataElt:  This means that we have encountered a data element in a tree that has already been visited, so now is the time to process that data element.   The IDataElt holds an INEBTree and an index value that indicates which data element in the INEBTree to process.  

1. Apply the lambda function to the data element held at the supplied index in the INEBTree's data array.   Any return value can be discarded.

2. The child tree that is the child tree to the right of the indicated data element, i.e. at the given index+1, has not yet been processed, wrap it up in an IBTreeElt and so put it in the RAC.

3. If there are any more data elements to be processed in the INEBTree's data array, i.e. at the supplied index+1, wrap the INEBTree and the incremented index value up in an IDataElt and put it in the RAC as well.

4. The RAC is clearly not empty now, so get the next element from the RAC and recur to it.

• IBTreeElt:  This is an as-yet unprocessed B-tree, which could be empty or non-empty.  You've got no choice but to delegate.

• IMTBTree: No data here to process. No children trees either.  Since we had to get an element from the RAC to arrive at this point, the RAC could be empty:

• Empty RAC: Nothing more to process!  All done!  Since we had to go through a non-empty tree to get here, we obviously processed at least one data element, so return true.

• Non-empty RAC:  There's more to process.   Go get the next element and recur to it.

• INEBTree: This is an unprocessed, but non-empty B-tree, so we have to start processing it.  A non-empty B-tree has at least one data element and at least two child trees, so we know we have a few things to process.

1. Wrap the first child tree (index = 0) in an IBTreeElt and put it into the RAC.

2. Wrap the host INEBTree and an index value of zero (to indicate that the first data element needs to be processed) and put it into the RAC.

3. The RAC is clearly not empty, so get the next element from the RAC and recur to it.

The test code uses both a stack and a queue to test the RACTraverse algorithm.  It sets up the B-trees using a Binary Search Tree like algorithm, so that it is easier to see where the data elements are in the tree (see Prob. 1.b from Spring 2007 exam for more details on the insertion criteria).    Notice how the stack and the queue create wildly different traversal routes through the same tree, but yet, both guarantee that all data elements will be processed in the end.

Grading breakdown, referencing the parts of the above algorithm description:

Prob. 1.a (5 pts):  INEBTree above, steps 1 & 2, not including  the cases inside the delegation.

Prob. 1.b (10 pts):  IDataElt above, steps a-d, not including  the cases inside the delegation.

Prob. 1.c (5 pts):  IBTreeElt not including  the cases inside the delegation.

Prob. 1.d (5 pts):  IMTBTree, entire code for this case.

Prob. 1.e (10 pts):  INEBTree, entire code for this case, i.e. steps i-ii.

Problem 2 (40 pts total):  Life is a Game!

In this problem we will explore a modification of the famous "Conway's Game of Life".  This is simply a grid of cells where the cells can be described as either dead or alive.   With the addition of a few simple rules that govern how cells die or live or are born, based on the composition of their neighbors (usually the 8 nearest neighbors), successive iterations of the system show a remarkable complexity of behavior emerging from very simple underpinnings.    For more and better information than can possibly be mustered here, please visit the following web sites and try out their demos:

http://www.math.com/students/wonders/life/life.html

http://www.radicaleye.com/lifepage/

You can also Google "Game of Life" to find many, many more resources on this rich topic called "Cellular Automaton", which has many applications, including topics such as the spread of diseases in a population.

It should be noted that the web pages use worlds for the cells that are either bounded by walls or are infinite in size.    For computational simplicity, we will use a "toroidal" world where the top and bottom wrap around to each other and the sides wrap around to each other.  If you were to make a 3-D picture of this world, it would be in the shape of the surface of a torus, i.e. the surface of a doughnut.  This is very much like the way the old "Asteroids" games used to be laid out.   This will cause the cells' evolutions to be slightly different in our world than in the above reference web pages.

Live/Die/Birth Rules:  The basic Game of Life as described in the above web pages uses a few simple rules:

• A dead cell with exactly 3 nearest neighbors will come to life.
• A live cell with less than 2 or more than 3 nearest neighbors will die.
• A cell with exactly 2 or 3 nearest neighbors will continue to live.

The twist that we are adding is that our Game of Life will have multiple live states, allowing us to simulate two simultaneous, interacting populations in our system.   For instance, this could be used to simulate a disease and a cure combating each other in a population.  Of course, our game uses strategies, in the form of visitors to a cell, that are used to create the evolutionary cell behaviors based on a variant set of rules.

How to play our Game of Life:

The code, as supplied is already fully operational.  To run the game, simply run the project.   All the cells will start out dead.

• Clicking on a cell multiple times will cause it to cycle through its possible states.  White= dead, blue= live1 and Red = live2.
• Clicking "Start" will run the simulation using the displayed evolution strategy.
• Clicking "Stop" will stop the simulation.   You can stop the simulation, change the states of some cells and continue on if desired.
• Clicking "Reset" will cause all the cells to die.
• Clicking the "Change Strategy" button will set the current evolution strategy to that specified in the text field.   If the specified evolution algorithm class is invalid, the previous strategy will remain and be redisplayed.
  • Evolve1Strategy will follow the classic rules above but only for live1 (blue) cells.   Red live2cells are essentially ignored.
  • Evolve2Strategy will follow the classic rules above for live1 and live2 cells when their populations are in isolation, except 2 or more live2 neighbors will kill a live1 cell.  The red cells are thus the "cure" for the blue cell "disease".

Be sure to try the following patterns (images from the math.com web reference above):

"block", a stable state

"blinker", a metastable state

"glider", a moving metastable state

"r-pentomino" a wildly growing system

"toad" a metastable state

"beehive", a stable state

Be sure to try multiple "gliders" and "r-pentominos" simultaneously in both blue live1 and red live2 states combined with an Evolve2Strategy.  

Prob. 2.a (20 pts total):   mapRowCol() method to replace double for-loops.

In the ActionListener for the time object in LifeModel, there is double for-loop that is used to update the cells' states by executing the evolution strategy algorithm on every the cell in the system, i.e. in the cells array.

You are to do the following to convert the use of the double for-loops into a more compact, reusable mapping process:

Prob. 2.a.i:  (10 pts) Complete the  LifeModel.mapRowCol() method so that it will map the given lambda across all the elements of the cells array, passing the cell and its corresponding row and column to the ILambda's apply method.

Prob. 2.a.ii (10 pts) :  Fix the Timer's ActionListener

A bit of background information on how this sort of simulation is done: 

The Game of Life is what is called a "synchronous" simulation, which means that the next state of each entity (cell, here) is calculated but not enacted in one pass over the set of cells.  (This is the code that you are to be modifying.)  Thus the next states of all the cells are calculated at a single moment in time, based on the old, not the new states of the entities.   The system then takes a second pass through the system to enact all the changes that were calculated on the first pass.  This is contrast to an "asynchronous" simulation where each entity both calculates its new state and effects that change right away, before the other entities have calculated their changes.  The entities that have not yet calculated their changes thus do their calculations based on the new state of the already-updated entities and the old states of the not-yet updated entities.  The BallWar system is an asynchronous simulation system.

For synchronous systems, one of the ways of saving the changes that are yet to be done is by saving a set of lambda (command) objects that when applied, will enact the desired changes.   In our Game of Life system, the evolution algorithms save an ILambda to an LRStruct for each cell that needs to change state.   After the first pass is done, all the lambdas stored in the list are simply applied and the changes to the cells takes place.   This is the line of code after the double for-loop you are to be replacing. The BallSwarm codebase is a synchronous simulation system that works similarly.  

Do the following:

1. Comment out the double for-loop in the ActionListener for the Timer object and replace it with a definition of an ILambda whose

• apply() should be given 3 input parameters: the cell, its row and its column in that order.  Note, ILambda.apply() takes Objects as inputs. 
• apply() should take the cell at row, col in cells and run the current evolution strategy on it, which takes the row, col and the LRStruct list called "lambdas" as its 3 input parameters.
• apply() should return null.

2. Comment out the now unnecessary double for-loop in the Timer's ActionListener and replace it with a call to  mapRowCol() using your newly defined lambda to actually perform the updating process. 

Prob 2.b (20 pts total):    map() method to replace double for-loops

In the reset() method of LifeModel, a double for-loop is used to go through all the cells to set their states to dead.   This operation does not require the row and column of the cell, so we can use the for-each version of a for-loop to replace the current counted for-loop with a mapping process. 

Prob. 2.b.i (10 pts):   Complete the LifeModel.map() method to use a for-each loop to apply a lambda to every element of the cells array.  The ILambda's apply method will only take one parameter, the cell itself.

Probl. 2.b.ii (10 pts):   Do the following:

1. Complete the definition of the ILambda killCell field of LifeModel using an anonymous inner class so that it's apply method will set the given cell's (x[0]) state to "ICell.CELLSTATES.DEAD".   This will kill the cell. 
2. Comment out the double for-loop in the reset() method and replace it with a call to map(), using your killCell lambda.

Background note on enumerations (enum):  Enumerations are an OO way of not using "magic numbers" to denote one thing from another.  Instead of saying "1" means this thing and "2" means this other thing, we can create an "enumeration" that allows us to use regular words to describe different things without worrying about how to implement those distinctions (e.g. as integers or whatnot).   Here, ICell.CELLSTATES is an enumeration that lists out the all the possible different states that a cell could be in.   Individual values can be references as ICell.CELLSTATES.DEAD or ICell.CELLSTATES.LIVE1 or ICell.CELLSTATES.LIVE2.    See the code for Evolve1Strategy and Evolve2Strategy to see how enum values are used.   See the LifeModel code too to see how we can do things like figure out how many possible enum values there are.  Enumerations are a way of making a common procedural programming practice more OO.  Hardcore OO programs rarely use them.   They are used here as a way of decoupling the view from the model and the pieces of the model from itself.   This way the view can change the states of the cells without knowing what the available states are and also enables the states to be set without exposing the actual underlying state design pattern.

Prob. 3.  Task Scheduler

A task scheduler is a component that executes tasks (lambdas) in a certain order depending on various priority issues.    For instance, in most computers these days, there are many, many processes taking place at once.   The CPU  however is technically able to only perform on process at a time, so the operating system divvies up the process into a series of tasks, each with a certain "priority level".   High priority tasks get run first and more often than lower priority tasks.  

It gets a little more complicated than that unfortunately.  What if a low priority task keeps getting bypassed because there are always tasks of higher priority?  The low priority task would never get run at all .   So most task schedulers include a notion of time as well.   That is, the longer a task has been waiting in the queue to be run, the higher its "effective" priority.  Thus a low priority task if it hasn't been run for long enough will finally rise in effective priority to the point that it will run.   This insures that all tasks get run eventually.  

Clearly we have to use a priority queue of some sort here, but  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 for a task scheduler, since time is involved, our current implementation may be inappropriate.  We need to modify our RAC implementation.   We will do it in a slightly different way than last year's Exam 3 however.   Instead of completely rewriting the RAC implementation from class, we will simply augment it. The following interfaces and classes have been added:

• IRACFactory2 :   An  extension of IRACFactory that adds a method that will produce a RAC that uses a fixed insertion process and a variant retrieval algorithm based on a supplied Comparator.
• RACFactory2:  Concrete implementation of IRACFactory2

• ALRSRACFactory2:   Creates an implementation of an IRAContainer that use IAlgos for both insertion and retrieval.  Essentially, what is being done is that this abstract factory produces IRAContainers that require both insertion and retrieval policies.

• PQComparatorRACFactory2: A implementation of an IRACFactory2 that can instantiate IRAContainers that either have a variable insertion policy and a fixed removal policy or ones that have a fixed insertion policy and a variable removal policy.   The variable policies are determined by a supplied Comparator.

The task scheduler is thus just a shell around a RAC with a Comparator that defines its insertion/removal policy.   Since the task scheduler works with both numerical priority values plus time values, there is a utility wrapper class called TimePriorityCmd that holds a time value (in nanoseconds), an integer priority value and an ILambda task.  

The RAC holds TimePriorityCmds

The Comparator used with the policy algorithms must therefore work on TimePriorityCmd objects. 

The class TaskScheduler has the following methods:

• public void addTask(ILambda task, int priority) : Adds the given task with the given priority value.  Lower is values means higher priority.    Along with a time stamp created at the time that this method is run, the priority value and the task are wrapped in a TimePriorityCmd and stored in the RAC. 
• public ILambda getNextTask() : Retrieves the next task that should be run, based on the policies of the internal RAC.   The "no-op" ILambda given during the construction of the TaskScheduler is returned if there are no stored tasks to run.

Prob. 3.a (5 pts):  The Right RAC

What is the proper type of RAC to use in a TaskScheduler?  We have several different types of RAC factories producing different types of RACs.   Complete the constructor of the TaskScheduler class to properly initialize the internal RAC.  

After this section is complete, the test cases for the TimeComp and PriorityComp Comparators, which prioritize tasks based solely on time or priority value respectively, should now pass.   Note that the tests, in the TaskScheduler_Test class, will take a few seconds to run because they are putting in various time delays into the tasks submitted to the task scheduler.

Prob. 3.b (20 pts):  A Time and Priority-Dependent Comparator

Now, let's write a Comparator called TimePriorityComp that uses both time and priority.    There are many, many ways to do this, but here's a simple way:

TimePriorityComp.compare(x, y) returns -1 if x is to be run before y, +1 otherwise.  Remember that x and y are TimePriorityCmd objects.

The task to run first is is determined by

• The one whose time stamp is earlier by greater than the maximum allowed time difference (maxDeltaTime).
  • Otherwise the one with the lowest priority rating
    • Otherwise the one that has the older timestamp (i.e. when equal priority).   

You are to complete the TimePriorityComp.compare(x, y)method to implement the above rules.

Important:  Note that the time values are longs, not ints! 

Notice that in the test code for TimePriorityComp, low priority value tasks can run before high priority tasks if they are old enough.

Hint: Use the code from the TimeComp and PriorityComp Comparators,

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

©2008 Stephen Wong and Dung Nguyen