Computer Science 15-100 (Sections S-V), Fall 2008
Homework 11
Due: Thu 20-Nov-2008 at 11:59pm (email copy) and at Friday's
class/recitation (identical physical copy)
(no late submissions accepted).
Read these instructions first!
public static void bogusShuffle1(int[] a) {
// reversing isn't shuffling!
Collections.reverse(intArrayAsList(a));
}
public static void bogusShuffle2(int[] a) {
// rotating isn't shuffling!
Collections.rotate(intArrayAsList(a), a.length/2);
}
public static void bogusShuffle3(int[] a) {
// sorting isn't shuffling!
Collections.sort(intArrayAsList(a));
}
public static void bogusShuffle4(int[] a) {
// This one DOES shuffle, but it also CORRUPTS the array!
a[0] = a[1]; // this corrupts the array!
Collections.shuffle(intArrayAsList(a));
}
Note that these use the intArrayAsList helper method, that you will have to also include in your code if you wish to use these methods:
public static
List<Integer> intArrayAsList(final int[] a) {
return new AbstractList<Integer>() {
public Integer get(int i) { return a[i]; }
public Integer set(int i, Integer val) { int old=a[i];
a[i]=val; return old;}
public int size() { return a.length; }
};
}
In effect, you should have a test method for your test method (really!),
and you should verify that your test method correctly detects each bogus
shuffler. Then, it should also note that the following method actually
works (although it would not be allowed as a solution to this problem):
public static void workingShuffle(int[] a) {
// This really does shuffle (of course), although you could not
// use this as a solution to this problem (but it's useful for
// testing your test method!)
Collections.shuffle(intArrayAsList(a));
}
Finally, your test method should not depend on human observation (so it
should not, for example, print out an array and ask the user to "check if
this looks shuffled"). Instead, you may need to call a shuffle method
many times and look for some patterns that should occur if it works (for
example, how often should a[0] remain at a[0] after a shuffle?
Think about this!). You have to handle the fact that there is some
variation, of course, but still, you should be able to write a test method
that, without human assistance, determines that workingShuffle works and
that the 4 bogusShuffles do not work.
public static ArrayList<String> f(String[] a) {
ArrayList<String> result = new ArrayList<String>();
HashSet<String> set = new HashSet<String>();
for (String s : a) {
if (set.contains(s))
result.add(s);
set.add(s);
}
Collections.sort(result);
return result;
} public static ArrayList<String> g(String[] a) {
HashSet<String> set = new HashSet<String>(Arrays.asList(a));
ArrayList<String> result = new ArrayList<String>(set);
Collections.sort(result);
return result;
} public static ArrayList<String> h(String[] a) {
ArrayList<String> list = new ArrayList<String>(Arrays.asList(a));
ArrayList<String> result = new ArrayList<String>();
String last = null;
Collections.sort(list);
for (int i=0; i<list.size()-1; i++)
if ((list.get(i).compareTo(list.get(i+1)) == 0) &&
!list.get(i).equals(last))
result.add(last = list.get(i));
return result;
}import java.util.*;
class MyCode {
public static void main(String[] args) {
// Create the quadratic equation f(x) = 3x^2 + 2x + 1
QuadraticEquation f = new QuadraticEquation(3, 2, 1);
// Verify that f(2) = 3*2*2 + 2*2 + 1 = 12 + 4 + 1 = 17
assert(f.eval(2) == 17);
}
}
// This class models a quadratic equation of the form y = ax^2 + bx + c,
// where each of a, b, c, x, and y are all ints.
class QuadraticEquation {
private int a, b, c;
public QuadraticEquation(int a, int b, int c) {
this.a = a;
this.b = b;
this.c = c;
}
public int eval(int x) {
return a*x*x + b*x + c;
}
}
Here is a modified version of the main method that uses an enhanced for loop to print out the coefficients a, b, and c of the equation:
public static void main(String[] args) {
// Create the quadratic equation f(x) = 3x^2 + 2x + 1
QuadraticEquation f = new QuadraticEquation(3, 2, 1);
// Show that f(2) = 3*2*2 + 2*2 + 1 = 12 + 4 + 1 = 17
assert(f.eval(2) == 17);
// Print out the coefficients of this equation
System.out.println("The
following should print the coefficients of");
System.out.println("y
= 3x^2 + 2x + 1, one per line. That is, it should");
System.out.println("print
3 on the first line, 2 on the second, and 1 on the third.");
for (int coeff : f)
System.out.println(coeff);
}
In a file Hw11IterableAndIterator.java, first copy the modified
version of the code from above, and then change the implementation of
QuadraticEquation so that the enhanced for loop in the sample code
works.
Note: the solution to this question is very similar to the
Iterable + Iterator example from the class notes. Use those
notes as your guide here! One important difference, however, is
that here you may not place the coefficients a, b, and c into an array,
an ArrayList, or any other Collection, even if that is a reasonable
approach to this problem.
Specifically, you will have to change the QuadraticEquation class so
that it implements the Iterable<Integer> (since we are iterating over
int values, we must use the wrapper class Integer here). This, in
turn, requires that you create an instance of QuadraticEquationIterator
-- a class you must write that has been specialized to iterate over
QuadraticEquation coefficients a, b, and c, and so it implements
Iterator<Integer>. Again, look closely at the notes for details.
Remember: you may not place the coefficients a, b, and c into an
array, an ArrayList, or any other Collection!
Carpe diem!