Computer Science 501
Data Stuctures and Algorithm Analysis

Fall 2013, The College of Saint Rose

Home     Syllabus     Schedule     Style Guide

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.

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

Thought Questions

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

1. Thought question 1 from Bailey p. 177. (1 point)
2. Thought question 2 from Bailey p. 177. (2 points)
3. What is the time complexity of this problem? Explain briefly. (1 point)
4. 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). (1 point)
5. 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? (1 point)
6. How long does it take to solve the 22-, 23-, 24-, and 25-block problems? (1 point)
7. Do these agree with your expectations, given the time complexity of the problem? (1 point)
8. Estimate the time that would be needed to solve the 40- and 60-block problems, and explain briefly how you arrived at these approximations. (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). (2 points)

Before 6:00 PM, Wednesday, October 30, 2013, submit your Java program for grading. There are two things you need to do to complete the submission: (i) upload a copy of your tar or zip file (for your program, please include .java files only, no .class files) using Submission Box under assignment "TwoTowers", and (ii) print and turn in a hard copy of your program.

Don't forget to check your programs for compliance with the Style Guide for CSC 501 Programs

Grading

This lab assignment is graded out of 30 points.