Details of the calculation are written in Scheme.
Homework assignments counted for 45% of the grade, the midterm for 22%, and the final exam for 33%.
All homework scores were computed as percentages of the maximum possible score; then the lowest homework percentage was dropped. The average homework percentage was computed by weighting the remaining 7 homework scores equally.
The midterm was not curved. The final exam was curved by adding 10 points to the raw score. The statistics for the final exam were:
N = 20 hi = 92 median = 65.5 lo = 45 mean = 64.8 90-100 1 80-89 3 70-79 3 60-69 4 50-59 5 40-49 4
31. [6 points] Write Java code that implements the immutable
abstract data type DAG as specified below.
(If all four operations run in constant time and space, then
you may receive up to 4 points of extra credit.)
Signature:
ut: DAG x DAG --> DAG
ht: DAG --> int
wt: DAG --> int
bt: int --> DAG
Client syntax: As illustrated by the following example.
public static void main (String[] args) {
DAG d1 = DAG.bt(3);
DAG d2 = DAG.ut(d1, d1);
DAG d3 = DAG.ut(d1, d2);
System.out.println(d3.wt()); // prints 14
System.out.println(d3.ht()); // prints 5
}
Algebraic specification:
DAG.ut(d1, d2).ht() = 1 + max (d1.ht(), d2.ht())
DAG.bt(n).ht() = n
DAG.ut(d1, d2).wt() = 1 + d1.wt() + d2.wt()
DAG.bt(n).wt() = 1 + n
A recipe implementation would receive full credit. Here is an untested recipe implementation that has been refactored enough to earn the 4 points of extra credit:
public abstract class DAG {
public static DAG bt (int n) { return new BT(n); }
public static DAG ut (DAG d1, DAG d2) { return new UT (d1, d2); }
public abstract int ht();
public abstract int wt();
private static class BT extends DAG {
private int n;
BT (int n) { this.n = n; }
public int ht () { return n; }
public int wt () { return 1 + n; }
}
private static class UT extends DAG {
private DAG d1;
private DAG d2;
private int ht0; // precomputed result of ht()
private int wt0; // precomputed result of wt()
UT (DAG d1, DAG d2) {
this.d1 = d1;
this.d2 = d2;
this.ht0 = 1 + Math.max (d1.ht(), d2.ht());
this.wt0 = 1 + d1.wt() + d2.wt();
}
public int ht () { return ht0; }
public int wt () { return wt0; }
}
}
32. [8 points] Write Java code that implements a mutable
ADT named DSet, whose public operations include those
shown below, using the client syntax shown:
new DSet()
returns a mutable DSet with no elements
boolean add(Refreshable r)
if r is already in this DSet, returns false and leaves
this DSet unchanged; otherwise returns true and changes
this DSet by adding r
boolean contains(Refreshable r)
returns true if and only if this DSet contains r
java.util.Iterator<Refreshable> iterator()
returns an Iterator that generates the elements of
this DSet
Here is one of the simplest correct solutions:
public DSet extends java.util.HashSet<Refreshable> { }
For solutions similar to the above, a common mistake was
to extend java.util.Set, which is not a class.
Here is another solution using composition and delegation instead of inheritance:
public DSet {
private java.util.TreeSet<Refreshable> dset;
DSet () {
this.dset = new java.util.TreeSet<Refreshable>();
}
public boolean add (Refreshable r) { return dset.add(r); }
public boolean contains (Refreshable r) { return dset.contains(r); }
public java.util.Iterator<Refreshable> iterator () {
return dset.iterator();
}
}
For solutions similar to the above, a common mistake was
to declare that DSet implements Set,
which obliges the implementor to implement many more methods.
Another way to answer this question is to implement everything from scratch, eschewing reusable software as Mel would have. That is much more difficult; everyone who attempted that kind of solution made several mistakes.
Last updated 24 April 2009.