Computer Science 211
Data Structures

There is no graded design this week because of the exam, but I encourage you to do one anyway and go over it with me early in the week.

When you implement your SubsetIterator that extends AbstractIterator, be sure to import structure5.* and java.util.Iterator at the top of your file. Also remember that your SubsetIterator should use generic types. It is far from obvious how to accomplish this, so here is what your class header should look like for the SubsetIterator:

public class SubsetIterator<E,T extends Vector<E>> extends AbstractIterator<T>

During the implementation of your SubsetIterator's get and next methods, you will need to create a Vector<E> and return it as a T to satisfy the required return types specified by AbstractIterator<T> for those methods. Java's syntax for this is again not entirely obvious. This should work:

  T subset = (T)new Vector<E>();

For testing, write a main method of your SubsetIterator that creates a Vector<Integer> with the Integers from 0 through 7, creates a SubsetIterator<Integer,Vector<Integer>> with this Vector<Integer>, and then prints out all subsets returned and a count of the subsets returned. Make sure you end up with 256 subsets printed. Please leave this main method in your program when you submit.

Write the main method to solve the two towers problem in a separate class called TwoTowers, proceeding as specified in the lab description in the Bailey text.

In a plain-text file named README, write your answers to the two thought questions in the text.

Also in the README file, answer these extra questions (let's call them thought question 3): How long does it take your program to find the answer to the 20-block problem? (hint: try the time command rather than instrumenting your source code with a timer). Based on the time taken to solve the 20-block problem, about how long do you expect it would take to solve the 21-block problem? What is the actual time? How about each problem size up to the 25-block problem? Do these agree with your expectations, given the time complexity of the problem? What about the 40- and 60-block problems? (You can try these if you're very patient, but for the purposes of this question, just estimate based on the run times of the smaller problems).

When you're finished, submit your well-documented and nicely-formatted source code. Use Javadoc comments, including pre and postconditions, as appropriate. Also use assertions to enforce your preconditions. Be sure to name your files SubsetIterator.java and TwoTowers.java.

This lab assignment is graded out of 30 points. As in all labs, your grade includes design, documentation, style, and correctness. Be sure to document your program with appropriate comments (use Javadoc!), including your name and a general description at the top of the file, a description of each method with pre and postconditions where appropriate. Also use comments and descriptive variable names to clarify sections of the code which may not be clear to someone trying to understand it.

The program design grade will be based on the design choices you make in the implementation of both of the classes you will submit. The program style grade will be based on code formatting and approriate use of Java naming conventions. The program documentation grade is, of course, based on the comments you provide (including Javadoc and pre and postconditions as appropriate). The program correctness grades are based on how well the different parts of your program meet the functionality requirements.