# CSCI 151 Lab 7: The Two Towers

## Overview

This lab will:

- Give you practice writing and using
`Iterator`

s. - Give you practice working with integers as sequences of bits.

## Acknowledgements

This lab is adapted from *Java Structures* by Duane A. Bailey.

## Introduction

Suppose that we are given \(n\) uniquely sized cubic blocks and that each block has a face *area* between \(1\) and \(n\) square inches. If we build two towers by stacking these blocks, how close can we get their heights? The following two towers built by stacking 15 blocks, for example, differ in height by only 129 millionths of an inch:

Still, this stacking is only the *second-best* solution! To find the best stacking, we could consider all the possible configurations. We do know one thing: the total height of the two towers is computed by summing the heights of all the blocks:

\[h = \sum_{i=1}^n \sqrt i\]

If we consider all the subsets of the \(n\) blocks, we can think of the subset as the set of blocks that make up, say, the left tower. We only need to keep track of which subset comes closest to \(h/2\) without exceeding it. In this lab, we will represent a set of \(n\) distinct objects by an `ArrayList`

, and we will construct an `Iterator`

that returns each of the \(2^n\) subsets.

## Background

The trick to understanding how to generate a subset of \(n\) values from an `ArrayList`

is to first consider how to generate a subset of indices of elements from \(0\) to \(n-1\). Once this simpler problem is solved, we can use the indices to help us build an `ArrayList`

(or subset) of values identified by the indices.

There are exactly \(2^n\) subsets of values \(0\) to \(n-1\). We can see this by imagining that a coin is tossed \(n\) times—once for each value—and the value is added to the subset if the coin flip shows a head. Since there are \(2 \times 2 \times \dots \times 2 = 2^n\) different sequences of coin tosses, there are \(2^n\) different subsets.

We can also think of the coin tosses as determining the values for \(n\) different digits in a binary number. The \(2^n\) different sequences generate binary numbers in the range \(0\) through \(2^n - 1\). Given this, we can see a line of attack: count from \(0\) to \(2^n - 1\) and use the binary digits (bits) of the number to determine which of the original values of the `ArrayList`

are to be included in a subset. For example, suppose our original `ArrayList`

contains \(3\) items. Then the counter \(0 = 000_2\) means the empty subset; \(3 = 011_2\) means the subset containing only the first and second items but not the third, since the first two bits (counting from the right end!) of \(011_2\) are \(1\), but the third bit is \(0\).

Computer scientists work with binary numbers frequently, so there are a number of useful things to remember:

- An
`int`

value is represented by 32 bits. A`long`

is represented by 64 bits. For maximum flexibility, it will be useful to use`long`

integers to represent sets of up to 64 elements. - The arithmetic left shift operator
`<<`

can be used to quickly compute powers of \(2\). Left shift works by “shifting” the bits of a value over, adding zero bits on the end. For example, \(1101_2 <\!\!< 1 = 11010_2\); \(1101_2 <\!\!< 2 = 110100_2\); \(1101_2 <\!\!< 3 = 1101000_2\); and so on. Just as adding a zero to the end of a decimal number means multiplying by ten, adding a zero to the end of a binary number is the same as multiplying by \(2\). Therefore, the value \(2^i\) can be computed by starting with a single \(1\) bit, and shifting it \(i\) places to the left. In Java we write this`1L << i`

. The constant`1L`

is the value one stored as a 64-bit`long`

value. Using this constant ensures that we are using a 64 -bit shift operation resulting in a`long`

value instead of a 32-bit operation resulting in an`int`

value. The “bitwise AND” of two numbers (written

`&`

in Java) takes the logical AND of each pair of bits. For example,`101110 & 110100 = 100100`

. Each bit in the result is`1`

only if both inputs to`&`

had a`1`

bit in the corresponding place; otherwise the result bit will be`0`

.We can use this to determine the value of a single bit in a number’s binary representation: to retrieve bit \(i\) of a

`long`

integer`m`

, we first compute \(2^i\) using`1L << i`

. This creates a binary number with all zero bits except for a single`1`

bit at index`i`

. If we then take the bitwise AND of this with`m`

(that is,`m & (1L << i)`

), all the bits of the result are zero except possibly bit`i`

: in particular, the result is \(0\) if`m`

had a \(0\) bit at position`i`

, and nonzero otherwise.

## Step 1: SubsetIterator

Create a new `SubsetIterator<E>`

class which `implements Iterator<ArrayList<E>>`

. This new class should have a constructor that takes an `ArrayList<E>`

as its sole argument. Subsets of this `ArrayList`

will be returned as the `Iterator`

progresses. Notice that the class implements `Iterator<ArrayList<E>>`

, not `Iterator<E>`

!

Internally, `SubsetIterator`

should use a `long`

value to represent the current subset. This value starts out as \(0\) (which represents the empty set) and increases to \(2^n - 1\) (which represents the entire set of values) as the `Iterator`

progresses.

Write a `hasNext`

method that returns `true`

if the current value is a reasonable representation of a subset.

Write a `next`

method that returns a new `ArrayList`

of values that are part of the current subset (using the techniques explained in the Background section above), and then increments the counter. If bit \(i\) of the current counter is 1, element \(i\) of the original `ArrayList`

should be included in the resulting subset `ArrayList`

.

## Step 2: Test

You can now test your new `SubsetIterator`

by having it print all the subsets of an `ArrayList`

of values. For example, write a `main`

method for your `SubsetIterator`

that creates an `ArrayList`

with the `Integer`

s from `0`

through `3`

, creates a `SubsetIterator`

with this `ArrayList`

, and then prints out all subsets returned. Make sure you end up with all \(16\) different subsets printed.

## Step 3: Best height

To solve the two towers problem, write a `main`

method in a new class `TwoTowers`

that inserts the values \(\sqrt 1, \sqrt 2, \dots, \sqrt n\) into an `ArrayList<Double>`

. (To compute the square root of `n`

, you can use the `Math.sqrt(n)`

method.) A `SubsetIterator`

is then used to construct \(2^n\) subsets of these values. The values of each subset are summed, and the sum that comes closest to, but does not exceed, the value \(h/2\) is remembered. After all the subsets have been considered, print the height of the tower that came closest to \(h/2\).

## Step 4: Best tower

Your solution from step 3 printed out the *height* of the best tower, but we want to actually know which blocks to use! Modify your code so that it prints out not just the height of the best tower, but the numbers of the blocks that were used to make it. (*Hint*: change your `ArrayList<Double>`

to an `ArrayList<Integer>`

.)

## Thought Questions

- What is the best solution to the \(15\)-block problem?
- How long does it take your program to find the answer to the \(20\)-block problem? (You may find the StopwatchCPU or NanoStopwatch classes from a previous lab to be helpful.) 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 50-block problems? (These will take a
*very*long time. Just estimate based on the run times of the smaller problems). - This method of exhaustively checking the subsets of blocks will not work for very large problems. Consider, for example, the problem with \(50\) blocks: there are \(2^{50}\) different subsets. One approach is to repeatedly pick and evaluate random subsets of blocks; stop the computation after 1 second of elapsed time, printing the best subset found so far. How would you implement
`randomSubset`

, a new`SubsetIterator`

method that returns a random subset? (You do not have to actually implement it, just describe how you*would*implement it.)

## What to Hand In

You should turn in

`SubsetIterator.java`

`TwoTowers.java`

- A document containing your answers to the Thought Questions

## Grading

- To get a C, complete Steps 1 and 2 (
`SubsetIterator`

+ test) - To get a B, complete Step 3 (Best height)
- To get an A, complete Step 4 (Best tower)
- To get a 100, complete all the steps and the Thought Questions