Exam #3 - Comp 212

Rice University - Fall 2003

Instructions

  1. The examination is open book/notes.  You are allowed to consult any written materials available under the sun, except code from your current Comp212 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 (Nguyen and Wong, but not the labbies) of this course.
  3. Do not post your questions on the newsgroup.  E-mail 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.
  6. You have 5 hours to do the regular questions on the exam. You may take an extra hour to complete the optional extra credit questions.
  7. Submission instruction: you may submit your exam in two ways.
    •  a hard copy with all answers in type-written form, except perhaps diagrams (if any) which can be hand-drawn.  Be sure to print your name and sign the honor pledge.  This is the PREFERRED way!
    • e-mail both dxnguyen@rice.edu and swong@rice.edu your solutions; be sure to zip or jar your exam to keep it small.  Your e-mail message should contain the pledge of honor.

    In either case, send dxnguyen@rice.edu and swong@rice.edu  an e-mail to notify your submission.  We will reply to confirm your submission. 

  8. The deadline for submission is  Dec. 17, 2003 at 5 PM.
Pledge of Honor

 

1. 25 pts 2. 20 pts + 5 pts extra 3.  30 pts + 5 pts extra 4. 25 pts Total 100 pts + 10 pts extra
         

I. Array Implementation of the immutable IList (25 pts)

Below is an implementation of IList using array.  Some of the methods are stubbed out.  Your task is to complete all the stubbed code.  For your convenience, we have written a JUnit test class called TestListClick here to download the jar file that contains all the stubbed out code and all source code needed to compile and test your solution.  Note: ArrayListFactory.java is in the subdirectory listFW/factory.

To extract files from a jar file, enter the command: jar -xfv jarFileName.

ArrayListFactory.java 
package listFW.factory;

import listFW.*;
import listFW.visitor.Length;  // to compute the number of elements in an IList.

/**
 * Manufactures concrete IEmptyList and INEList objects as arrays of Objects.
 * @author Dung X. Nguyen
 * @since Copyright 2003 by DXN - All rights reserved
 */
public class ArrayListFactory implements IListFactory {

    /**
     * NOTE the use of multiple interface inheritance below!
     */
    private static class ArrayList implements IEmptyList, INEList {
        static final ArrayList MTList = new ArrayList(); // the empty list!

        private Object[] _elts; // the data elements in this ArrayList.
        private int _firstIdx;  // the index of the first element in this ArrayList.

        /**
         * Anonymous inner object to copy an Ilist to the array _elts starting from a given
         * index, idx, assuming there is enough room left in _elts to hold the data in _elts.
         */
        private IListAlgo copy2array = new IListAlgo() {
            public Object emptyCase(IEmptyList host, Object idx) {
                return null;
            }

            /**
             * Example: suppose _elts = {a, b, c, d, e, f, g}, host = (x y z) and idx = 2.
             * After copying, _elts = {a, b, x, y, z, f, g}.
             */
            public Object nonEmptyCase(INEList host, Object idx) {
            	// STUDENTS TO WRITE THE CODE.  7pts
            }
        };

        /**
         * Initializes _elts to an empty array of Objects and _firstIdx to 0.
         */
        private ArrayList() {
            _elts = new Object[0];
            _firstIdx = 0;
        }

        /**
         * Initializes _elts to reference the given array of Objects elts
         * and _fitstIdx to the given index start.
         */
        private ArrayList(Object[] elts, int start) {
            _elts = elts;
            _firstIdx = start;
        }

        /**
         * Initializes this ArrayList to contain the given Object dat as the first element,
         * and the rest of this ArrayList to contain the elements of the given IList tail.
         */
        public ArrayList(Object dat, IList tail) {
            // STUDENTS TO WRITE THE CODE.  8 pts
            // HINT: USE THE Length VISITOR AND copy2array.
        }

        /**
         * Returns the fist data Object in this ArrayList.
         * Throws an Exception if this ArrayList is empty.
         */
        final public Object getFirst() {
            // STUDENTS TO WRITE THE CODE.  2 pts
        }

        /**
         * Returns an ArrayList representing the rest of this ArrayList.
         * Throws a NoSuchElementException if this ArrayList is  empty.
         */
        final public IList getRest() {
            // STUDENTS TO WRITE THE CODE.  3 pts
        }

        /**
         * An emtpty ArrayList will call alog.emptyCase, while a non-empty ArrayList will call
         * algo.nonEmptyCase.
         */
        final public Object execute(IListAlgo algo, Object inp) {
            // STUDENTS TO WRITE THE CODE.  5 pts
    }

    /**
     * The unique instance of this class.
     */
    public static final ArrayListFactory Singleton = new ArrayListFactory();
    private ArrayListFactory() {
    }

    /**
     * Creates an empty list.
     * @return an IEmptyList object.
     */
    public IEmptyList makeEmptyList() {
        return ArrayList.MTList;
    }

    /**
     * Creates a non-empty list containing a given first and a given rest.
     * @param first a data object.
     * @param tail != null, the rest of the non-empty list to be manufactured.
     * @return an INEList object containing first and tail
     * @exception IllegalArgumentException if tail == null.
     */
    public INEList makeNEList(Object first, IList tail) {
        if (null == tail) {
            throw new IllegalArgumentException("tail is null!");
        }
        return new ArrayList(first, tail);
    }
}

II. Cars and Key Fobs  (20 pts + 5 pts extra credit)

In this problem we will build a model of cars and remote entry key fobs – the little things on a key chain used to remotely lock or unlock a car.  In our model we have

·        factories that make cars (ICarFactory) with a given color,

·        cars (ICar) that have unique vehicle identification numbers (VIN) and can make their associated key fobs.

·        key fobs (IKeyFob) have a single button on it (i.e. a single method of no parameters) that controls a single car.

You are to write the code for two ICarFactorys: SaturnFactory and MercedesFactory.  The ICars made by these factories should have these behaviors when the button on their associated key fobs is pressed:

Action:

Saturn

Mercedes

When car is initially created:

Unlocked

Unlocked

After first time IKeyFob.pressBtn() is called:

Locked

Locked, but security system is unarmed.

After second time IKeyFob.pressBtn() is called:

Unlocked

Locked and security system armed.

After third time IKeyFob.pressBtn() is called:

Locked

Unlocked

After fourth time IKeyFob.pressBtn() is called:

Unlocked

Locked, but security system is unarmed.

Etc.

Note that the Saturn undergoes a two-click cycle, but the Mercedes undergoes a three-click cycle. 

To simplify matters, we will simply have the car do a System.out.println(…) with enough information to tell what car was affected (i.e. make, color and VIN), and what the effect of pressing the key fob’s button was (i.e. locked, unlocked, unarmed, armed).

Your task is write the SaturnFactory and MercedesFactory classes such that the above behaviors are replicated and the following conditions are met (20 pts):

5 pts Extra Credit:  Include the ability for a car to identify exactly which key fob is controlling it.

To facilitate testing, we have supplied you with the CarDealer class which instantiates 2 Saturns, one of which has two key fobs, and 2 Mercedes.  It then randomly picks from a single key fob from the 5 key fobs and presses its button.  It repeats this 15 times.  CLICK HERE TO DOWNLOAD THE JAR FILE CONTAINING THE SOURCE CODE FOR THE INTERFACES AND TEST CODE.

A typical output from running the main(..) method of CarDealer is:

CarDealer: KeyFob #2 picked.

The blue Mercedes with VIN #2661678 is now locked but unarmed!

CarDealer: KeyFob #0 picked.

The blue Saturn with VIN #23328673 is now locked by key fob ID#29744585!

CarDealer: KeyFob #1 picked.

The red Saturn with VIN #13655059 is now locked by key fob ID#28472268!

CarDealer: KeyFob #4 picked.

The blue Saturn with VIN #23328673 is now unlocked by key fob ID#22927632!

CarDealer: KeyFob #3 picked.

The red Mercedes with VIN #12206609 is now locked but unarmed!

CarDealer: KeyFob #4 picked.

The blue Saturn with VIN #23328673 is now locked by key fob ID#22927632!

CarDealer: KeyFob #2 picked.

Beep! Beep! The blue Mercedes with VIN #2661678 is now locked and armed!

CarDealer: KeyFob #3 picked.

Beep! Beep! The red Mercedes with VIN #12206609 is now locked and armed!

CarDealer: KeyFob #2 picked.

The blue Mercedes with VIN #2661678 is now unlocked, unarmed and has adjusted the seats just for you!

CarDealer: KeyFob #4 picked.

The blue Saturn with VIN #23328673 is now unlocked by key fob ID#22927632!

CarDealer: KeyFob #4 picked.

The blue Saturn with VIN #23328673 is now locked by key fob ID#22927632!

CarDealer: KeyFob #2 picked.

The blue Mercedes with VIN #2661678 is now locked but unarmed!

CarDealer: KeyFob #4 picked.

The blue Saturn with VIN #23328673 is now unlocked by key fob ID#22927632!

CarDealer: KeyFob #3 picked.

The red Mercedes with VIN #12206609 is now unlocked, unarmed and has adjusted the seats just for you!

CarDealer: KeyFob #0 picked.

The blue Saturn with VIN #23328673 is now locked by key fob ID#29744585!

 

In the above printout, the Saturns include the extra credit behavior of being able to identify their individual key fobs.  You are not required to replicate the exact wording above, just the included information.

 

III. Higher Order List Operations (30 pts + 5 pts extra credit)

“Higher order” functions on a list are operations on lists that take other functions as input parameters.  The following should be familiar to those die-hard Scheme-heads:

Foldr (“fold-right”) is an operation on a list, aList which has a first and rest, a value, b,  and a function, f of two variables,  defined recursively as follows:

Foldr(empty, b , f) = b

and

Foldr(aList, b, f) = f(first, Foldr(rest, b, f)

For example, suppose

    aList = (xn, xn-1, xn-2, … x2, x1, x0)

then

    foldr(aList, b, f) = f(xn, f(xn-1, f(xn-2, …f(x2, f(x1, f(x0, b)))…)))

Thus, we see that

b = a base case value

and

f= an inductive case function which calculates the next recursive result, given an element (first) of a list and the current recursive result. 

That is, f(x, current_rr) = next_rr  

Foldr is the same as “natural recursion” or “reverse accumulation”. 

Similarly, Foldl (“fold-left”) is an operation on a list, aList which has a first and rest, a value, b,  and a function, f of two variables, defined recursively as follows:

Foldl(empty, b , f) = b

and

Foldl(aList, b, f) = Foldl(rest, f(first, b) ,f) 

Again, for example using the same definition of aList as above,

Foldl(aList, b, f) = f(x0, f(x1, f(x2, …f(xn-2, f(xn-1, f(xn, b)))…)))

where b and f are define exactly as above.

Note once again that if the list is empty, the result of Foldl is simply b.

Notice also that the order of the calculation using Foldl is the reverse of that for Foldr.

Foldl is the same as “forward accumulation”.

Filter is a list operation that takes predicate function as an input parameter.  A predicate function is a function that returns a boolean true or false.  In this case, the predicate function is limited to those which take only a single input parameter whose domain is the range of the list.  Filter on a list, aList, with a predicate, pred, is defined as follows: 

Filter(empty, pred)  = empty

and

Filter(aList, pred)  = { xi | pred(xi) = true} where xi is an element of aList

That is, the result of filtering the list with the predicate is the list of elements from aList for which the predicate function, pred, is true when applied to each of those elements.

Given the interface IFoldInp, which encapsulates the base case value and the inductive case function (see the source file for complete documentation), you are to write

  1. an IAlgo called Foldr that performs the fold-right operation on its LRStruct host, where an IFoldInp is the parameter.   The result of the fold-right operation is returned.  10 pts
  2. an IAlgo called Foldl that performs the fold-left operation on its LRStruct host, where an IFoldInp is the parameter.  The result of the fold-left operation is returned.  10 pts

And, given the interface ILambda, which can be used to represent a predicate function, you are to write

  1. an IAlgo called Filter that performs the fold-right operation on its LRStruct host, where an ILambda is the parameter.  The ILambda should take an Object as its input parameter and return a Boolean object.  Filter should mutate its host to eliminate the elements for which the predicate is false.   The modified host is returned.  10 pts

5 pts Extra credit: Using a either a new class, FoldFilter that implements IFoldInp, or a new method, IFoldInp makeFoldFilter(ILambda pred), of the supplied test class, HigherOrderTests, create an IFoldInp that utilizes a given ILambda predicate to create a filtering operation using either Foldr or Foldl.  One difference will be that this filtering will need to create a new LRStruct and not modify the original host.

CLICK HERE TO DOWNLOAD THE JAR FILE CONTAINING THE SOURCE CODE FOR LRStruct, THE INTERFACES AND TEST CODE.

When the main(…) method of HigherOrderTests is run, the following output should be obtained:

lrs = (1 2 3 4 5 6 7 8 9 10)

add foldr on lrs = 55

add foldrl on lrs = 55

mult foldr on lrs = 3628800

mult foldrl on lrs = 3628800

cons foldr on lrs = (1 2 3 4 5 6 7 8 9 10)

cons foldrl on lrs = (10 9 8 7 6 5 4 3 2 1)

filter all multiples of two on lrs = (2 4 6 8 10)

filter all non-multiples of two on lrs = (1 3 5 7 9)

filter range 3 < x < 7 on lrs = (4 5 6)

filter range !(3 < x < 7) on lrs = (1 2 3 7 8 9 10)

// The following is the output of the extra credit:

foldr-filter all multiples of two on lrs = (2 4 6 8 10)

foldl-filter all multiples of two on lrs = (10 8 6 4 2)

foldr-filter all non-multiples of two on lrs = (1 3 5 7 9)

foldl-filter all non-multiples of two on lrs = (9 7 5 3 1)

 

IV. Heap Implementation of Priority Queues  (25 pts)

The following is the code for a heap implementation of an IRAContainer that is a priority queue containing Comparable.  Your task is to complete the stubbed out code.

HINT: You may find it useful to call on the siftUp and siftDown method of the Heapifier.  Click here to download the source code for all required classes (including the JUnit test class).

PQArrayContainer.java
package rac;

import listFW.*;

/**
 * Uses the Heap structure to implement a priority queue.
 * Assume the container only contains Comparable elements.
 */
public class PQArrayContainer implements IRAContainer {
    private Comparable _elts[];
    private int _insertIdx;  // next available index for insertion.
    
    public PQArrayContainer(int size) {
        _elts = new Comparable[size];
        _insertIdx = 0;
    }
    
    /**
     * Empty the container.
     * NOTE: This implies a state change.
     * This behavior can be achieved by repeatedly removing elements from this IRAContainer.
     * It is specified here as a convenience to the client.
     */
    public void clear() {
        _insertIdx = 0;
    }

    /**
     * Return TRUE if the container is empty; otherwise, return
     * FALSE. 
     */
    public boolean isEmpty() {
        // STUDENT TO COMPLETE;  2 pts
    }

    /**
     * Return TRUE if the container is full; otherwise, return
     * FALSE. 
     */
    public boolean isFull() {
        // STUDENT TO COMPLETE;  3 pts
    }

    /**
     * Return an immutable list of all elements in the container in the same order as the _elts array.
     * @param fact for manufacturing an IList.
     */
    public IList elements(IListFactory fact) {
        // STUDENT TO COMPLETE;  5 pts
    }

    /**
     * Remove the next item from the container and return it in log(n) time.
     * NOTE: This implies a state change.
     * @throw an Exception if this IRAContainer is empty.
     */
    public Object get() {
        // STUDENT TO COMPLETE;  7 pts
    }

    /**
     * Add an item to the container in log(n) time.
     * NOTE: This implies a state change.
     * @param input the Object to be added to this IRAContainer.
     * @throw an Exception if this IRAContainer is full.
     */
    public void put(Object input) {
        // STUDENT TO COMPLETE;  8 pts
    }
    
    /**
     * Return the next element in this IRAContainer withour removing it.
     * @throw an Exception if this IRAContainer is empty.
     */
    public Object peek() {
        return _elts[0];
    }
}