Exam #3 - Comp 212

Rice University - Spring 2006

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 exam is made publicly available.  Using any materials other than your own created after the exam is posted is a direct violation of the Honor Code.  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 (Cox and Nguyen, but not the labbies) of this course.
  3. Do not post your questions on WEBCT.  E-mail to both of us, alc at rice.edu and dxnguyen at rice.edu, your questions instead. We will reply to you directly, and if deemed necessary, we will forward our reply to WEBCT 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. For some problems, 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.  You may end up wasting a lot of time that way.  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.
  6. There are 4 questions for a total of  100 points.  You have 5 hours to do the exam.
  7. Submit the exam in two ways:
  8. The deadlines for submission are:
    • for graduating seniors:  12 PM (noon), May 04, 2006,
    • for the rest: 5 PM, May 10, 2006.
Pledge of Honor

 

1 (15 pts)   2.a (25 pts)  2.b  (20pts)  3 (40  pts) Total (100 pts)

 

1. Priority Queue and the Heap Structure

Download and unzip heap.zip for the source code to be used in this problem.  The class Heapifier  provides two key methods: siftUp and siftDown to maintain the heap structure for an array of Comparable.  The class RACHeap is implements the IRAContainer interface using an array of Comparable that satisfies the heap property.  RACHeap is an example of what is called a priority queue.  The objects in the RACHeap are compared based on their priorities.  The smaller (with respect to compareTo) the object, the higher the priority.  The class TestObject inside the JUnit test class TestRACHeap is an example of such a Comparable class.

There are situations when the priority of an object in a priority queue changes requiring the priority queue to be updated to maintain the proper ordering.  Complete the method update in RACHeap as specified in the provided stub code.

2. Application of Binary Search Tree

Roughly speaking, a computer's memory can be modeled as an array of integers. Your task is to write a class for managing the free, or unused, parts of a computer's memory. Download and unzip memory.zip for the source code to be used in this problem.  In the provided code, this class Allocator implements the interface:

interface IAllocator {
    int allocate(int count);
    void free(int index, int count);
}

The method allocate() returns the starting index of the first contiguous group of unused locations of size "count" in memory. If, however, there is no sufficiently large contiguous group of unused locations, then allocate() returns -1. The method free() adds the "count" contiguous locations starting at "index" to the allocator's collection of unused memory.

The class Allocator utilizes a binary search tree (BST) _memory consisting of objects of class Range. representing contiguous block of available memory.  This class has the following definition.

class Range {
    int index;
    int count;
}

Here index denotes the starting index of the array of available memory.  count denotes the number of available units of memory.

2.a  Initially, the BST will hold a single Range object covering all of memory. As allocation requests are made, Range objects are either removed in their entirely from the BST or reduced in count. For example, if allocate() is called with size 500 and the first Range object of sufficient size is (index: 1000, count: 750), then the Range object becomes (index: 1500, count: 250).  Write the code for the anonymous inner class _alloc as indicated in the provided class Allocator.

Note: Allocator has method called insert(int index, int count).  This method is for the purpose of testing the method allocate without using the method free.  The provided JUnit test class TestAllocator uses the method insert to enter disjoint contiguous blocks of memory and tests the correctness of allocate.  You may want to comment out the assertEquals statements and run the test class to see how it behaves.

2.b  Analogously, when memory is freed, adjoining Range objects are expanded to include the newly freed memory. For example, if the allocator hold Range objects (index: 5000, count: 1000) and (index: 6500, count: 500) and the memory at index 6000 of count 500 is freed, the allocator will replace the two previous Range objects by a single Range object (index: 5000, count: 2000).  Write the pseudo-code for the anonymous inner class _freer as indicated in the provided class Allocator.    The pseudo-code should clearly describe the various cases where adjoining Range objects need or need not be coalesced  and the steps to handle these cases.  Working code is not required.
 

3. Postfix Calculator

Demo

To see where we are going, download and run the demo (executable jar file--select "Open" when downloading): postfix.jar   As you can see this is a really cheap postfix calculator:  it  does not support subtraction nor division.  Nevertheless, it seems to calculate arithmetic expression in postfix notation correctly.  It also displays the content of the stack and the accumulator that are internal to the calculator.  What do we mean by an "postfix" expression?  A binary operation is said to be in postfix notation if the operator (e.g. +) follows the two operands.  There are also "infix" and "prefix" expressions.  The following table shows an example of each form of notation.

Adding two numbers x, y together

Infix Notation x + y
Prefix Notation + x y
Postfix Notation x y +


Note that it is an Honor Code violation to attempt to decompile any of the demos in this problem.

Background Information

A postfix calculator, a.k.a. Reverse Polish Notation (RPN) calculator, is a calculator that computes arithmetic expressions in postfix notation.  Internally it uses a stack, S, to store the operands in a postfix expression.  It also has an accumulator, acc, to maintain the current input and to display the result of a computation.  The RPN calculator does not maintain a "pending operation" as the infix calculator (see lab #13) does.  Whenever a operation is entered, the RPN calculator immediately performs the operation by doing the following:

The following table illustrates how an RPN calculator works.  Use the above postfix.jar demo to study the behaviors of the calculator.

Infix expression   Postfix Expression   Key Sequence   Internal Calculation acc   S (grows to right)  
34 + 56 34  56  + Enter 34 acc = 34 34 empty
Push S.put(acc 34 34
Enter 56 acc = 56 56 34
+ accS.get() + acc = 34 + 56 
S.put(acc)
90 90
    Clear acc = 0;
S.clear()
0 empty
3 + ( 4 * 5) 3  4  5 *  + Enter 3 acc = 3 3 empty
Push S.put(acc ) 3 3
Enter 4 acc = 4 4 3
Push S.put(acc ) 4 3  4
Enter 5 acc = 5 5 3  4
* acc = S.get() * acc = 4 * 5
S.put(acc )
20 3  20
+ acc = S.get() + S.get() = 3 + 20 
S.put(acc )
23 23
    Clear acc = 0;
S.clear()
0 empty
(3 + 4) * 5 3  4  +  5  * Enter 3 acc = 3 3 empty
Push S.put(acc ) 3 3
Enter 4 acc = 4 4 3
+ acc = S.get() + acc = 3 + 4
S.put(acc )
7 7
Enter 5 acc = 5 5 7
* acc = S.get() + acc = 7 * 5
S.put(acc )
35 35
    Clear acc = 0;
S.clear()
0 empty
(3 + 4) * (5 + 6) 3  4  +  5  6  +  * Enter 3 acc = 3 3 empty
Push S.put(acc ) 3 3
Enter 4 acc = 4 4 3
+ acc = S.get() + acc = 3 + 4
S.put(acc )
7 7
Enter 5 acc = 5 5 7
Push S.put(acc ) 5 7  5
Enter 6 acc = 6 6 7 5
+ acc = S.get() + acc = 5 + 6
S.put(acc )
11 7  11
* acc = S.get() *  S.get() = 11 * 7 
S.put(acc )
77 77
    Clear acc = 0;
S.clear()
0 empty
3 * (4 + 5) * 2 3  4  5  +  * 2 * Enter 3 acc = 3 3 empty
Push S.put(acc ) 3 3
Enter 4 acc = 4 4 3
Push S.put(acc ) 4 3  4
Enter 5 acc = 5 5 3  4
+ acc = S.get() +  acc = 4 + 5
S.put(acc )
9 3 9
* acc = S.get() *  S.get() = 9 * 3 
S.put(acc )
27 27
Enter 2 acc = 2 2 27
* acc = S.get() *  acc = 27 * 2
S.put(acc )
54 54

 

Problem Description

Your job is to design and implement a postfix calculator like the above demo with a simpler interface.  This calculator has on the outside:

This calculator is to correctly compute any syntactically legal postfix expression. Entering any malformed postfix expression should result in an error.  Click here to download and run the demo of the calculator you are going to produce: rpn.jar.  The behaviors of this RPN calculator can be modeled as a finite state machine that is similar to the infix calculator done in lab #13.  In fact, it has the same number of states as that infix calculator.  Because the infix calculator and the postfix calculator differ in their internal representations, the actions performed in each state transition will differ.

Click here to download and save the source code of that you will need to use to implement your calculator: rpnsource.zip.  Most of the files are the source code of the data structures you have learned in this semester: immutable list, mutable list, restrict access container.  You need only complete the code for RNPMachine.java in the model package.  You are free to add any number of non-public fields and methods to RNPMachine.java.  You are free to add any number of non-public classes to support your RNPMachine class.  RPNView.java in the view package is the view with the main method. You need not modify the view at all.

Hint: It helps to analyze the state transitions first.  Below is the state transition for the start state to help you get started!

Start State

event

actions performed

next state

enterDigit(0)

display “0”

start state

enterDigit(d != 0)

display “d”

accum state

enterPoint()

display “0.”

point state

enterOp(op)/do op[err]

display “Error!”

error state

enterOp(op)/do op[no err]

perform op w/ operand from stack and from display

push acc onto stack

display acc

comp state

push()/push[err]

display “Error!”

error state

push()/push[no err]

push display onto stack

start state

clear()

acc = 0

display “0”

empty stack

start state