Solution for the Final Exam

Here is my solution. There are lots of acceptable variations ...

Problem 1

A Battery is an object that implements the following interface:

interface BatteryI {
  // The current charge of the battery is a number between 0 
  // and MAX_CHARGE (inclusive).
  final int MAX_CHARGE = 5;

  // A call to recharge() sets the current charge to MAX_CHARGE.
  void recharge ();

  // A call to use() throws the NoPower exception if the current 
  // charge is 0; otherwise it decrements the current charge by 1.
  void use () throws NoPower;
}

Write class definitions for NoPower and Battery.

Solution

class NoPower extends Exception {}

class Battery implements BatteryI {
  private int charge;

  public Battery () { this(MAX_CHARGE); }
  public Battery (int c) { charge=c; }

  public void recharge () { charge=MAX_CHARGE; }

  public void use () throws NoPower {
    if (charge == 0) {
      throw new NoPower();
    }
    else charge--;
  }
}

Problem 2

A Maze is recursively built using two kinds of objects:

a DeadEnd, or
a Hall leading to two Mazes: a left one and a right one.

Every Maze object (whether it is a DeadEnd or a Hall):

has a name of type String that identifies it,
may have a hidden treasure,
may have an electric outlet, and
can be searched by MazeVisitors.

Formally, a Maze object implements the following interface:

interface MazeI {
  String toString ();
  boolean hasTreasure();
  boolean hasElectricOutlet();
  void accept (MazeVisitor rv) throws VisitorStuck;
}

Given that the MazeVisitor interface is:

interface MazeVisitor {
  void visitDeadEnd (DeadEnd r) throws VisitorStuck;
  void visitHall (Hall r) throws VisitorStuck;
}

write class definitions for Maze, DeadEnd, and Hall.

Solution

abstract class Maze implements MazeI {
  protected boolean outlet = false; 
  protected boolean treasure = false; 
  protected String name;

  public boolean hasElectricOutlet() { return outlet; }
  public boolean hasTreasure() { return treasure; }

  abstract public void accept (MazeVisitor rv) throws VisitorStuck;
}

//////////////////

class DeadEnd extends Maze {
  public DeadEnd (String name) { this.name = name; }
  public DeadEnd (String name, boolean o, boolean t) { 
    this.name = name; 
    outlet=o; 
    treasure=t; 
  }

  public void accept (MazeVisitor rv) throws VisitorStuck {
    rv.visitDeadEnd(this);
  }

  public String toString () { 
    return "DeadEnd " + name;
  }
}

//////////////////

class Hall extends Maze {
  public Maze leftExit, rightExit;

  public Hall (String name, Maze l, Maze r) { 
    this.name = name; 
    leftExit=l; 
    rightExit=r; 
  }

  public Hall (String name, boolean o, boolean t, Maze l, Maze r) {
    leftExit = l; 
    rightExit = r; 
    outlet = o;
    treasure = t;
  }

  public void accept (MazeVisitor rv) throws VisitorStuck {
    rv.visitHall(this);
  }

  public String toString() { 
    return "Hall " + name;
  }
}

Problem 3

The goal of a TreasureSeeker is to look for a DeadEnd or Hall object that has a treasure. To be able to search the maze, a TreasureSeeker must implement the MazeVisitor interface (defined in Problem II). In addition, every TreasureSeeker will have an instance variable treasureLocation of type String in which it will save the location of the treasure. The details of visiting a maze are as follows:

While traversing a maze, a MazeVisitor may fail by throwing a VisitorStuck exception. Failures can be fatal or non-fatal:
```
class VisitorStuck extends Exception {
  boolean fatal;
  VisitorStuck (boolean f) { fatal = f; }
}
```
When visiting a DeadEnd object, the TreasureSeeker will look for the treasure. If it finds it, it saves it in the treasureLocation and returns. Otherwise it signals failure by throwing a non-fatal VisitorStuck exception.
When visiting a Hall object, the TreasureSeeker will first look for the treasure in the current Hall object. If it finds it, it saves it and returns. Otherwise, it searches the left Maze. If a non-fatal exception occurs during that search, it will search the right Maze. If the exception was fatal, it re-throws it.

Write the class TreasureSeeker.

Solution

class TreasureSeeker implements MazeVisitor {
  Maze treasureLocation;

  public TreasureSeeker () {}

  public void visitDeadEnd (DeadEnd r) throws VisitorStuck {
    if (r.hasTreasure()) treasureLocation=r;
    else {
      throw new VisitorStuck(false);
    }
  }

  public void visitHall (Hall r) throws VisitorStuck {
    if (r.hasTreasure()) { treasureLocation=r; return; }
    Maze left = r.leftExit;
    Maze right = r.rightExit;
    try {
      left.accept(this);
    }
    catch (VisitorStuck e) {
      if (e.fatal) throw e;
      else right.accept(this);
    }
  }
}

Problem 4

A Robot is-a TreasureSeeker operating on batteries. Every Robot has a Battery initially charged to MAX_CHARGE. When visiting either a DeadEnd or a Hall, the Robot will first try to use its Battery. If there is enough charge, it will perform the same operations as the generic TreasureSeeker. Otherwise if there is not enough power, the Robot will look for an electricOutlet, and if it finds one, it will recharge its Battery, and try to visit the DeadEnd or Hall again. If the Robot can't find an electricOutlet, it will throw a fatal VisitorStuck exception. Write the class Robot.

Solution

class Robot extends TreasureSeeker {
  private Battery b; 
  
  public Robot () { b = new Battery(); }

  public void visitDeadEnd (DeadEnd r) throws VisitorStuck {
    try {
      b.use();
      super.visitDeadEnd(r);
    }
    catch (NoPower e) { 
      if (r.hasElectricOutlet()) {
	b.recharge();
	visitDeadEnd(r);
      }
      else {
	throw new VisitorStuck(true);
      }
    }
  }

  public void visitHall (Hall r) throws VisitorStuck {
    try {
      b.use();
      super.visitHall(r);
    }
    catch (NoPower e) { 
      if (r.hasElectricOutlet()) {
	b.recharge();
	visitHall(r);
      }
      else {
	throw new VisitorStuck(true);
      }
    }
  }
}

Problem 5

Almost every hardware machine includes a cache. We will build a CachedMemory which is an object that behaves like a regular Memory but is optimized to use to a small local cache whenever possible. The idea is that when a fetch operation is requested from the CachedMemory, the operation will first attempt to use the cache; if the cache entry is not valid or missing, the operation will use the main memory as usual. Here is an example of how a CachedMemory operates. Consider a Memory of size 70 and a cache of size 10. The cache will be represented using three arrays of size 10:

an array Word[] cacheCells,
an array boolean[] valid, and
an array int[] tag.

If we try to fetch the contents of location 32, the following sequence of events take place:

We compute 32 / 10 and 32 % 10 which gives us the tag 3 and the index 2.
We check whether valid[2] is true.
We check whether tag[2] is equal to 3.
If both checks succeed, the cache entry is valid, and there is no need to go to the main memory. We can immediately return cacheCells[2].
If one of the checks fails, then we fetch a Word from location 32 in the main memory (call this Word X), then:
- set valid[2] = true,
- set tag[2] = 3,
- set cacheCells[2] = X, and
- return X.

In the case of a store operation, we will always write to both the memory and the cache without performing any checks.

We will extend our hardware machine with a cache by implementing a class CachedMemory. that extends the class Memory. The constructor for the class CachedMemory should create a Memory and then three local arrays cacheCells, valid, and tag to represent the cache. Initially, every entry in the array valid contains false. The other two arrays may contain arbitrary values. For your convenience, I have attached the relevant APIs.

Solution

package duckMachine.architecture;

/**
 *  Memory with cache.
 *  @author Amr Sabry
 *  @version jdk-1.1
 */

public class CachedMemory extends Memory {
  private Word[] cacheCells;
  private boolean[] valid;
  private int[] tag;

  public CachedMemory (int c, int s) {
    super(s);
    cacheCells = new Word[c];
    valid = new boolean[c];
    tag = new int[c];
    for (int i=0; i < c; i++) {
      valid[i] = false;
      cacheCells[i] = new Data(0);
      tag[i] = 0;
    }
  }

  public Word fetch (Word addr) throws MemoryE {
    int add = addr.toInt();
    int ctag = add / cacheCells.length;
    int cadd = add % cacheCells.length;
    if (valid[cadd] && tag[cadd] == ctag) {
      return cacheCells[cadd];
    }
    else {
      Word data = super.fetch(addr);
      valid[cadd] = true;
      tag[cadd] = ctag;
      cacheCells[cadd] = data;
      return data;
    }
  }

  public void store (Word addr, Word word) throws MemoryE { 
    int add = addr.toInt();
    int ctag = add / cacheCells.length;
    int cadd = add % cacheCells.length;
    valid[cadd] = true;
    tag[cadd] = ctag;
    cacheCells[cadd] = word;
    super.store(addr,word);
  }
}

Extra Credit Problem

There is a neat algorithm that generates all the prime numbers. The idea is to start with the following infinite sequence of natural numbers:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, ...

The first number of that sequence is the prime number 2. We now generate a new infinite sequence that excludes all the multiples of 2:

3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, ...

The first number of the new sequence is the prime number 3. We now generate a new infinite sequence that excludes all the multiples of 3:

5, 7, 11, 13, 17, 19, 23, 25, ...

The first number of the new sequence is the prime number 5. We now generate a new infinite sequence that excludes all the multiples of 5:

7, 11, 13, 17, 19, 23, ...

and so on. Using this algorithm, one can easily get the first n prime numbers for any n.

Solution

abstract class InfiniteSequence {
  abstract int getNext();
}

class FromTwoSeq extends InfiniteSequence {
  private int current;

  FromTwoSeq () { current=1; }

  int getNext() { return ++current; }
}

class FilteredSeq extends InfiniteSequence {
  private InfiniteSequence source;
  private Function filter;

  FilteredSeq (InfiniteSequence s, Function f) { source=s; filter=f; }
  
  int getNext() {
    int i = source.getNext();
    while (! filter.apply(i)) {
      i = source.getNext();
    }
    return i;
  }
}

abstract class Function {
  abstract boolean apply (int n);
}

class NotMultipleOf extends Function {
  private int i;

  NotMultipleOf (int i) { this.i = i; }

  boolean apply (int j) { return !(j % i == 0); }
}

class Primes {
  private InfiniteSequence primes;

  Primes () { primes = new FromTwoSeq(); }
  
  int nextPrime() {
    int prime = primes.getNext();
    primes = new FilteredSeq(primes, new NotMultipleOf(prime));
    return prime;
  }
}

Visited

times since December 15, 1997 (or the last crash).

sabry@cs.uoregon.edu