Due: Wednesday, February 28th at the beginning of class (but not to hand in)

Read: Carrano and Prichard, Chs. 1-5

Problem 0: Review old quizzes and homeworks.

Problem 1: Design a set of classes that can be used in an application that manages billing for a subway system. Each customer will have a smart card that stores value for fares. Upon completing a trip, the card should be charged a fare that depends on the departure and arrival stations and whether the trip started during peak times. The application should also keep track of the ridership ot each station. (A UML class diagram will suffice for the design.)

Problem 2: The following method is an attempt to write a method that, given two positive integers, returns their quotient. There are two problems with the code as given below (aside from the fact that simply returning dividend / divisor would be easier). What are the errors?

    public static int quotient(int dividend, int divisor)
    {
        // should validate arguments
        if (dividend <= 0 || divisor <= 0)
            throw new IllegalArgumentException("Arguments must be positive");

        // no base case
        if (dividend < divisor)
            return 0;
        else
        {
            // recursive invocation uses same arguments; arguments
            // should be set according to identity
            // a / b = 1 + (a - b) / b (for b != 0)
            // to get us one step closer to the base case

            return 1 + quotient(dividend - divisor, divisor);
        }
    }

Problem 3: Consider the following method

public static int bar(String s)
{
  if (s.length() < 2)
    return 0;
  else if (s.charAt(0) != s.charAt(1))
    return 1 + bar(s.substring(1));
  else
    return bar(s.substring(1));
}

• What does bar("a") return? 0
• What does bar("abc") return? 2
• What does bar("aaa") return? 0
• Describe what bar does. Your description should enable someone to easily determine what bar(s) returns without having to trace the code. It returns the number of non-matching adjacent characters.

Problem 4: Write a recursive method that computes a_k, where a_k is defined as follows: a₀ = 2, a₁ = 1, and a_k = a_k-1 + 2 * a_k-2 for k > 1.

public static int a(int k)
{
    if (k < 0)
	throw new IllegalArgumentException();
    else if (k == 0)
	return 2;
    else if (k == 1)
	return 1;
    else
	return a(k - 1) + 2 * a(k - 2);
}

Problem 5: Consider the following recursive function.

public int w(int k)
{
  if (k == 0)
    return 2;
  else if (k <= 3)
    return 1;
  else if (w(k - 1) + w(k - 2) + w(k - 3) % 3 == 0)
    return 2;
  else
    return 1;
}

          w(5)
       /    |   \
   w(4)    w(3)    w(2)
 /   |   \
w(3) w(2) w(1)

w(5) and w(7) both return 1.

Problem 6: Define an ADT for a television. Include operations that are included on most modern televisions.

We specify the operations using Java syntax; this is not intended to imply that the ADT must be implemented in Java.

public interface Television
{
    /**
     * Mutes the sound if mute is currently off; otherwise unmutes the
     * sound by returning the volume to the level it was at when it
     * was muted.
     */

    public void toggleMute();

    /**
     * Tunes to the next highest channel, wrapping around to the lowest
     * channel if there is no next highest channel.
     */

    public void channelUp();

    /**
     * Tunes to the next lowest channel, wrapping around to the highest channel
     * if there is no next lowest channel.
     */

    public void channelDown();

    /**
     * Tunes this TV to the given channel.  There is no effect if the
     * argument is not a valid channel number
     *
     * @param channel
     */

    public void selectChannel(int channel);

    /**
     * Increases the volume.  Turns off mute if it was on.  No effect
     * if the volumn is already at the maximum.
     */

    public void increaseVolume();

    /**
     * Decreases the volume.  Turns off mute if it was on.  No effect
     * if the volumn is already at the minimum.
     */

    public void decreaseVolume();

    /**
     * Turns off this TV.  No effect if the TV is already off.
     */

    public void turnOff();

    /**
     * Turns on this TV.  The volume and channel are set to what they were
     * when this TV was last on and mute is turned off.  If this TV is being
     * powered on for the first time, volume is set to 1/2 max and the channel
     * is set to the lowest possible value.
     */

    public void turnOn();

    /**
     * Returns true iff this TV is on.
     */

    public boolean isPoweredOn();

    /**
     * Returns true iff the volume is muted on this TV.
     */

    public boolean isMuted();

    /**
     * Returns the channel this TV is currently tuned to.
     */

    public int getChannel();

    /**
     * Returns the current volume level of this TV, or 0 if this TV is muted.
     */

    public int getVolume();
}

Problem 7: Implement a switch method for lists in three ways: 1) as a method that uses the ADT List methods, 2) as a method in the ArrayList631 class, and 3) as a method in the LinkedList631 class. switch should switch the order of the first two elements on the list. Think of a precondition for this method and have your code throw an exception if the precondition is not met.

// *** ARRAY LIST VERSION ***

public void switch2()
{
    if (numElements < 2)
        throw new IllegalStateException("Must have two elements to switch"
                                        + "; only have " + numElements);

        Object temp = elements[0];
        elements[0] = elements[1];
        elements[1] = temp;
}

// *** LINKED LIST VERSION ***

public void switch2()
{
    if (numElements < 2)
        throw new IllegalStateException("Must have two elements to switch"
                                        + "; only have " + numElements);

    Node oldFirst = head;
    Node oldSecond = head.getNext();

    head = oldSecond;
    oldFirst.setNext(oldSecond.getNext());
    oldSecond.setNext(oldFirst);
}

// *** ADT METHOD VERSIOn ***

private static void switch2(List631 l)
{
    if (l.size() < 2)
        throw new IllegalArgumentException("List must have >= 2 elements");

    // remove first element and insert it in position 1

    Object oldFirst = l.remove(0);
    l.add(1, oldFirst);
}

Problem 8: Implement a split method for lists in three ways: 1) as a method that uses the ADT List methods, 2) as a method in the ArrayList631 class, and 3) as a method in the LinkedList631 class. split should remove the last half of the elements from a list and return a new list that contains them in the order they appeared in on the original list. If the original list had an odd number of elements, the extra element should remain on the original list. Is there any difference in efficiency between the three implementations?

// *** ARRAY LIST VERSION ***

public List631 split()
{
    // compute number of elements that get split off into new list

    int numToSplit = size() / 2;

    // set up and copy elements into new list

    ArrayList631 result = new ArrayList631();
    result.elements = new Object[Math.max(numToSplit, 1)];
    result.numElements = numToSplit;
    System.arraycopy(elements, numElements - numToSplit, result.elements, 0, numToSplit);

    // null out elements in this list and update element count

    for (int toClear = numElements - numToSplit; toClear < numElements; toClear++)
        elements[toClear] = null;

    numElements -= numToSplit;

    return result;
}

// *** LINKED LIST VERSION ***

public List631 split()
{
    // compute number of elements to keep in this list

    int numToSplit = size() / 2;
    int numToKeep = size() - numToSplit;

    // position lastToKeep and firstToSplit on corresponding nodes
    // by setting firstToSplit at beginning of list and following
    // numToKeep next links; lastToKeep follows behind by one node

    Node lastToKeep = null;
    Node firstToSplit = head;
    for (int i = 0; i < numToKeep; i++)
        {
            lastToKeep = firstToSplit;
            firstToSplit = firstToSplit.getNext();
        }

    // unlink lastToKeep and firstToSplit

    if (lastToKeep != null)
        lastToKeep.setNext(null);

    // create new list

    LinkedList631 result = new LinkedList631();
    result.head = firstToSplit;

    // update tails

    result.tail = tail;
    tail = lastToKeep;

    // update counts

    numElements = numToKeep;
    result.numElements = numToSplit;

    return result;
}

// *** ADT METHOD VERSION ***

private static List631 split(List631 l)
{
    int numToSplit = l.size() / 2;

    LinkedList631 result = new LinkedList631();

    // remove numToSplit elements from end of l and add them to beginning
    // of result

    for (int i = 0; i < numToSplit; i++)
        {
            result.add(0, l.remove(l.size() - 1));
        }

    return result;
}

Both methods implemented as ADT methods run in O(n) time -- for the array list from copying the elements and for the linked list from finding the nodes where the split occurs. The implementation using existing ADT methods runs in O(n) time if the list to be split is an array-based list (then each of the O(n) removes from the array-based list and each of the O(n) adds to the linked list take O(1) time) but it runs in O(n²) time if the list to be split is a linked list (from each of the removes taking O(n) time).