# Computer Science 211 Data Structures

### Mount Holyoke College Fall 2009

Lab 4: The Two Towers Problem
Due: 9:00 AM, Friday, October 23, 2009

This week's assignment is the laboratory at the end of Chapter 8 in Bailey. You will gain experience writing your own generally-useful Iterator class and use it to solve an interesting problem.

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.

Notes and Hints

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.

Thought Questions

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).

Submission

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.