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 WebCT upload page under "Exam 2". 
7. The deadline for submission is  Wed. April 5, 2006 @ 10:00 AM.

Download the provided code: Comp201S06Ex2.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: Modeling a Car (25 pts total)

Below is the stub code for the class Car.   You are to complete the code as specified in the problem questions that follow.

/**
 * Modeling a car with state-dependent behaviors.
 */
public class Car {

    private int mileage = 0;   

    private static abstract class ACarState {
    // STUDENT TO DETERMINE WHAT THE STATE-DEPENDENT METHODS ARE AND
    // ADD THE CORRESPONDING ABSTRACT METHODS TO THIS ABSTRACT ACarState.
    // See problem 1.b













    } 

    // STUDENT TO FIGURE OUT WHAT THE CONCRETE STATES ARE AND
    // CREATE THE CONCRETE STATES AS ANONYMOUS INNER CLASSES.
    // See problem 1.c; code for concrete car states goes here...

    // THIS IS THE STATE OF A CAR;
    // STUDENT TO SET aCarState TO AN APPROPRIATE INITIAL STATE
    private ACarState aCarState; 
    

    // STUDENT TO APPLY THE STATE PATTERN TO DELEGATE
    // THE STATE-DEPENDENT BEHAVIORS OF A CAR TO ITS STATE.
    // See problem 1.b
    public String startEngine() {
       // STUDENT TO COMPLETE


    }
    

    public String stopEngine() {
       // STUDENT TO COMPLETE


    }
    

    public String pushAccelerator() {
       // STUDENT TO COMPLETE


    }
    

    public String hitTree() {
       // STUDENT TO COMPLETE


    }
    

    public int getMileage() {
       // STUDENT TO COMPLETE


    }
}

The following is an example of a sequence of interactions with a Car object showing its response to each method call.

1. Car car = new Car();
2. car.getMileage() returns 0
3. car.pushAccelerator() returns "[Nothing happens]"
4. car.hitTree() returns "[Nothing happens]"
5. car.stopEngine() returns "[No sound]"
6. car.getMileage() returns 0
7. car.startEngine() returns "Roar!"
8. car.startEngine() returns "Grind!!"
9. car.pushAccelerator() returns "Zoom, zoom!!"
10. car.getMileage() returns 10
11. car.pushAccelerator() returns "Zoom, zoom!!"
12. car.getMileage() returns 20
13. car.stopEngine() returns "Rrrrr....sssss....[no more noise]"
14. car.stopEngine() returns "[No sound]"
15. car.startEngine()returns "Roar!"
16. car.hitTree() returns "Crash! Bang!"
17. car.getMileage() returns 20
18. car.pushAccelerator() returns "[Nothing happens]"
19. car.getMileage() returns 20
20. car.stopEngine() returns "[Nothing happens]"
21. car.hitTree() returns "[Nothing happens]"
22. car.startEngine() returns "Sputter, sputter"

(The above sequence is replicated in the supplied test code).

Problem 1.a (5 pts):   From the above sequence interactions with a Car object, it is clear that the Car object changes its behavior dynamically.  This dynamic change of behavior can be implemented using the state design pattern.  How many states does Car have?  What are they?  Write your answer at the top of the supplied Car.java code.









 

Problem 1.b (5 pts):   Of the five Car methods, startEngine, stopEngine, pushAccelerator, hitTree, getMileage, which ones are state dependent?  Is the field mileage state-dependent?  Add the corresponding state-dependent methods to the abstract class ACarState that represents the union of all the states of the Car.  Write your answer at the top of the supplied Car.java code. and complete the code for the aforementioned five Car methods.


 

Problem 1.c (15 pts):   Use anonymous inner classes to implement all the concrete states of Car such that the above behavior is replicated.   Your code should conform to the following restrictions:

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

Problem 2:  Palindrome Lists (45 pts total)

Problem 3:  Randomized Lists (30 pts total)

In this problem we will explore algorithms on a mutable list that will enable us to randomize the order of the elements in the list.

Problem 3.a (15 pts): RandomSwap   First, we will need an algorithm to swap the first element of a LRStruct list with a random element in the rest of the list. 

The problem here is that in order to randomly pick an element from the rest of the list, we must first know how may elements are in that list.   Otherwise, we cannot insure an equal probability for swapping with any given element.   After we know how many elements are in the rest of the list, we can pick a random number that is at most that large and then swap with that number element in the rest of the list.  

We could do this in two passes of the list, one to get the length and another to swap with the randomly chosen element.    NOT!

Instead we will accumulate the length using a forward accumulation (i.e. on the way in) and then swap the element on the way back out.   We do this by returning a count, which is a random number that is between zero and the length of the list.   The count gets decremented every time the algo returns, so if we swap only when the count exactly equals zero, it will swap at the desired point and swap only once.  Ta da! One pass through the list!

More succinctly, the entire algorithm looks like this:

• Empty case:  Do nothing--nothing to randomly swap.  Return host (for convenience sake)
• Non-empty case:
  1. Execute a different IAlgo on rest that will forward accumulate the length of the list and swap with a randomly chosen element as it returns.  Start the accumulation at "1" to take the first element of the list into account.
     • Empty case: Take the accumulated length and return a random number that is at most that big.    A variable of type java.util.Random, called rand, has been provided.  A call to the nextInt method, passing it the length will return a random integer between zero, inclusive, to the length, exclusive.   See the documentation on Random at http://java.sun.com/j2se/1.5.0/docs/api/index.html
     • Non-empty case: 
       1. Recurse, continuing to accumulate the length of the list.
       2. Take the return value of the recursive call, the random integer, and check if it is zero.
       3. If it is zero,  then swap this host's first with the original outside host's first.
       4. Decrement the value and return it.  Note the swapping will only take place at the point the return value crosses zero, which should be at a random place in the rest of the list.   The swapping should thus only occur once.
  2. Return host (for convenience sake)

 You are to do the following:

• Complete the implementation of a visitor called RandomSwap 
• The test code is supplied.

Problem 3.b (15 pts): Randomize   To randomize the whole LRStruct is now almost trivial. 

• Empty case:  Do nothing.  Nothing to randomize.  Return host for convenience sake.
• Non-empty case:
  1. Randomize the rest of the list.
  2. Swap the first element of the host with the a random element in the rest of the list.  
  3. Return host for convenience sake.

You are to do the following:

• Complete the implementation of a visitor called Randomize  
• The test code is supplied.

Note:  The testing routine utilizes the fact that computerized random number generators don't really produce random numbers.  If you initialize the random number generator with the same "seed" value every time, then it will give you exactly the same sequence of numbers out every time.   Since most security software that relies on random numbers, this fact causes massive problems from keno games to electronic voting systems.   We are using this fact to our advantage here to enable us to test the outcome of the randomization since the random number sequence is predictable.

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

©2006 Stephen Wong and Dung Nguyen