Computer Science 136 Data Structures and Advanced Programming Williams College Fall 2005

Do the laboratory at the end of Chapter 7. There are no practice questions or design for this week because of reading period, but lab will meet as usual when we return.

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

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 5'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.

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

When you're finished, create and submit a tar file lab5.tar that includes the following:

• Your well-documented and nicely-formatted source code. Use Javadoc comments, including pre- and post-conditions, as appropriate. Also use Assertions to enforce your preconditions. Be sure to name your files SubsetIterator.java and TwinTowers.java.
• A README file that includes 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 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).

Extra Credit Opportunity

In class, we looked at a program in the "SortingComparisons" example and saw how each of the sorting algorithms we have studied (and some which we have not yet studied) perform when presented with random, sorted, and reverse sorted data. Everyone is encouraged to experiment with this program to learn more about the behavior of the algorithms we have considered so far. If you would like to earn a few points of extra credit on your lab grade, you may submit a more formal study, possibly consisting of:

1. Running the program on array sizes over some wide range. A good choice might be the powers of 2 from, say, 32, up to the largest size that you can run without running out of memory or patience. You can probably get up to 32768.
2. Graph the times to get a picture of their asymptoic behavior.
3. Analyze your results in a few paragraphs.

One graphing package available on our computers is gnuplot. Try out some of the examples from the gnuplot tutorial. Please ask if you would like some additional examples.

If you want to practice being a real computer scientist, you can do your writeup in the typesetting language LaTeX, which is used to generate all handouts for this course, was used to write our textbook, and is the most widely-used system for generating technical research papers. An example LaTeXdocument can be found on the FreeBSD systems at

/home/faculty/terescoj/shared/latexexample

Regardless of your choice of typesetting package or word processor, please submit your writeup as either a postscript file lab5extra.ps or a PDF file lab5extra.pdf.