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.  Use the WebCT exam chat rooms during the designated times or 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. You have 3 hours to do the regular questions on the exam.
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 upload page under "Exam2". 
7. The deadline for submission is  Wed. April 6, 2005 @ 10:00 AM.

• Download the provided code: Comp201Ex2.zip, which contains all the exam materials in a directory called Comp201Ex2.   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. Problem1, Problem2, etc.

• Your code is required to pass the supplied test code!

• Zip up the entire Comp210Ex2 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: An Anonymous Baby (25 pts total)

Consider the following behavior of an instance of the class Baby (each step is performed in sequence):

1. Baby calvin = new Baby(125)  // weight = 125 ounces at instantiation
2. calvin.getWeight()  returns 125.
3. calvin.tryFeed()  returns "Slurp, slurp, slurp..."
4. calvin.getWeight() returns 127.
5. calvin.getWeight() returns 127.
6. calvin.tryFeed() returns "Waaaaa! Waaaaa!"
7. calvin.getWeight() returns 126.   (Don't ask why--you don't want to know!)
8. calvin.getWeight() returns 126.
9. calvin.tryFeed() returns "Slurp, slurp, slurp..."
10. calvin.tryFeed() returns "Waaaaa! Waaaaa!"
11. calvin.tryFeed() returns "Slurp, slurp, slurp..."
12. calvin.getWeight() returns 129

Problem 1.a (5 pts):   In comments at the top of the supplied stub code for Baby.java, explain the above behavior in terms of states.   

• How many states does Baby have?
• What methods cause Baby to change state?

Problem 1.b (5 pts):   In comments at the top of the supplied stub code for Baby.java, explain what methods and attributes are invariant with respect to the Baby's state and which methods and attributes are variant with respect to the Baby's state.

Problem 1.c (15 pts):   Using anonymous inner classes, complete the implementation of Baby.java such that the above behavior is replicated.   The test code is supplied.   Your code should conform to the following restrictions:

• No if-statements should be used anywhere.
• No additional methods should be added to the Baby class.   Additional fields are acceptable.
• No additional classes or interfaces may be added that are visible from outside of the Baby

Problem 2:  Running Sums on Lists (30 pts total)

In this problem we will explore algorithms on both immutable and mutable lists that calculate the running sum as the list is traversed.

The "running sum" sum of a list is a list of the sums of all the elements up and including any given element of a list, starting at the front of the list.

Examples:

• The running sum of the empty list is the empty list. 
• The running sum of (5) is (5).
• The running sum of (-2, 2) is (-2, 0)
• The running sum of  (1, 2, 3) is (1, 3, 6).   
• The running sum of (10, -3, -4, 7, -1) is (10, 7, 3, 10, 9).

The running sum algorithm will be implemented as a visitor that takes no input parameters.

In the supplied stub code, the following sections are in separate projects.

Problem 2.a (15 pts):   Running sum of an immutable list (IList)

• Complete the implementation of a visitor called RunningSum to calculate the running sum of an IList list.  
• The visitor should return a new instance of an IList containing the running sum. 
• The test code is supplied.

Problem 2.b (15 pts):   Running sum of an mutable list (LRStruct)

• Complete the implementation of a visitor called RunningSum to calculate the running sum of an LRStruct list.  
• The visitor should return the value null.
• The visitor should mutate the host list such that it ends up containing the running sum.
• The test code is supplied.

Problem 3:  Removing Duplicates from an LRStruct (45 pts total + 10 pts extra credit)

Given a list with duplicate values in it, there are (at least) two ways in which one can define the removal of the duplicate values.  For instance:

(a, 2, a, 3, c, d, 3, a, e)  becomes either 

(a, 2, 3, c, d, e)   or 

(2, c, d, 3, a, e) 

What should the algorithm do if the host list is empty?

The difference is whether you keep the first occurrence of a value by looking from left to right (the first result) or from right to left (the second result).   This is simply the difference between a forward and a reverse accumulation removal algorithm (Which is which?).

We wish to express the duplicate removal algorithm that mutates the host list such that all duplicate values are removed.    The list should contain Objects, not just Strings or Integers, so the equals method of Object should be used to compare if two values are equal, e.g. a.equals(b) returns true if a and b have the same value or returns false if they are different.

In the supplied stub code, the following sections are all in a single project.

Problem 3.a (15 pts): Duplicate detection algorithm 

Whether we are doing a forward or reverse accumulation duplicate removal algorithm, we always need a way to detect if a duplicate value exists in a list, so we'll write a utility algorithm first and separately.   We will incorporate it into our whole algorithm in the later sections of the problem.

• Write an algorithm (visitor) called Contain that returns true if the supplied parameter is contained in the host list or returns false otherwise.
• The test cases are supplied.

Just in case...

In the following sections, if you could not get your Contain visitor to work properly, download the class file, Contain_Soln.class and place it in your prob3\classes\lrs\visitor folder.   (Careful, "Clean Build Directory" in DrJava will delete this file too!)   In your code, you can refer to Contain_Soln wherever Contain would be used.     It is an Honor Code violation to attempt to decompile this or any supplied class files.

Problem 3.b (15 pts):  Reverse accumulation duplicate removal.

• Using the supplied stub code and your Contain visitor, write a reverse accumulation algorithm called RemDupRev to remove all the duplicate values in an LRStruct.
•  RemDupRev should return the host list (not the empty list!).
• Complete the the test code to test your solution. 
• Hint:  Carefully think about what steps need to be accomplished and in what order.  Then write down a series of Java statements that do exactly what you want to do.  

Problem 3.c (15 pts + 10 pts extra):  Forward accumulation duplicate removal.

• Using the supplied stub code and your Contain visitor, write a forward accumulation algorithm called RemDupFwd to remove all the duplicate values in an LRStruct.
• RemDupFwd should return the host list  (not the empty list!).
• There are no test cases supplied  
• Hint: As you move forward through the list, you need to accumulate a list of the objects that you have seen so far.  What elements you remove will depend on whether or not you have seen that value before.
• 5 pts extra credit:   Use closure to eliminate the passing of the accumulator as an input parameter.
• 5 pts extra credit:   Write the test cases to test your algorithm.

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

©2008 Stephen Wong and Dung Nguyen