SUNY Geneseo Department of Computer Science

{Title}

The Sample Final is available on the Web; it is simply the final exam from last Fall's offering of this course.

Question 1

Would the Towers of Hanoi still take exponential time to solve if there were as many poles as disks?

No, because it could be solved by the following algorithm:

• Move the smallest disk to the destination pole (1 move)
• Move the top n-2 disks remaining on the source pole to the n-2 remaining empty poles, one disk per pole (n-2 moves; this leaves just the largest disk on the source pole)
• Move the smallest disk on to the top of one of the n-2 disks just moved (1 move; it doesn't matter which pole you move the smallest disk to -- the goal is to leave the destination pole empty)
• Move the largest disk to the destination pole (1 move)
• Move the smallest disk to the source pole (1 move; each disk is now on its own pole, with the largest disk on the destination)
• For each disk not on the destination pole, in order of size from largest to smallest, move the disk to the destination pole (n-1 moves)

This algorithm makes a total of 2n + 1 moves (see the counts in the algorithm), and so runs in Θ(n) time, which is less than exponential.

Question 2

What does it mean the playing a winning game of chess is "intractable?"

C, that a program that always wins at chess could take billions of years to play a game. The technical definition of an "intractable" problem is one that is solvable by algorithms, but only in inordinate amounts of time.

Question 3

List the shapes in the following ordered binary tree in increasing order:

Following the rule that at every node, items to the left are less and items to the right greater, the order of the shapes must be

Question 4

Are the following measurements consistent with a Θ(2ⁿ) execution time for an algorithm?

Divide each measured time by 2ⁿ, where n is the input size, and see if a common constant of proportionality emerges as n increases. The ratios are as follows:

Because the ratios seem to plunge towards 0 as n increases, the data are not consistent with the exponential hypothesis.

Question 5

Write an "embeds" algorithm that determines whether its parameter (a list) is embedded in the list to which the "embeds" message is sent.

    // In some subclass of List...
    boolean embeds( List l )
        if l.isEmpty()      // Empty list embedded in everything
            return true
        else if this.isEmpty()      // l not empty, so can't be in empty list
            return false
        else if this.getFirst() == l.getFirst()
            return this.getRest().embeds( l.getRest() )
        else
            return this.getRest().embeds( l )

Question 6

Prove that the following algorithm returns true if a tree contains an even number of items, and false otherwise.

    // in class ExtTree, a subclass of BinaryTree
    public boolean even() {
        if ( this.isEmpty() ) {
            return true;
        }
        else if (    ((ExtTree)this.left()).even()
                  && ! ((ExtTree)this.right()).even() ) {
            return true;
        }
        else if (    ! ((ExtTree)this.left()).even()
                  && ((ExtTree)this.right()).even() ) {
            return true;
        }
        else {
            return false;
        }
    }

The proof is by strong induction on the size of the tree.

As a base case, consider a tree of size 0. 0 is an even number of items, so the algorithm should return true. It does, because the this.isEmpty() test succeeds.

For the induction hypothesis, assume that even correctly classifies any tree of fewer than k items as containing an even or odd number of items. Note that k > 0.

Show that even correctly classifies trees of k items. Since k > 0, the initial this.isEmpty() test fails. The algorithm then analyzes whether the subtrees contain even or odd numbers of items. Since these analyses are done via even messages to the subtrees, and the subtrees contain fewer than k items, the induction hypothesis guarantees that the subtrees are correctly classified. There are four possibilities for the subtrees:

1. The left subtree has an even number of items and the right subtree an odd number. The second test in even succeeds, and so even returns true. This is correct because the total number of items in the subtrees is odd (an even number plus an odd one), and adding one more item for the root gives an even number of items in the tree as a whole.
2. The left subtree contains an odd number of items, and the right subtree an even number. The third test in even succeeds, and even returns true. This is correct by an argument similar to that in case 1.
3. Both subtrees contain an odd number of items. The even algorithm falls through to its final else, and returns false. This is correct because the subtrees collectively contain an even number of items (an odd number plus an odd number), and so the tree as a whole contains an odd number of items.
4. Both subtrees contains an even number of items. Again, even falls through to its final else and returns false, which is correct by a similar argument to case 3.

Question 7

Explain how to accurately time paint messages.

The times shown in the question are all very small, suggesting that the problem is that paint executes too quickly to time accurately. Thus, timing a loop that executes multiple paint messages should produce times long enough to measure accurately. To guarantee that the measurements are as accurate as possible, also time an empty control loop and subtract its time from the time measured for the loop that sends the paint messages. The final code looks like this (added code in red):

    ...
    Robot testBot = new Robot();
	 final int REPS = ... /* some large number */
    long start = System.currentTimeMillis();
	 for ( int i = 0; i < REPS; i++ ) {
        testBot.paint( java.awt.Color.red );
    }
    long end = System.currentTimeMillis();
	 long cStart = System.currentTimeMillis();
	 for ( int i = 0; i < REPS; i++ ) {
	 }
	 long cEnd = System.currentTimeMillis();
    System.out.println( (end ­ start) - (cEnd - cStart) );
    ...

Question 8

Derive the number of characters the following algorithm prints, as a function of n.

    public static void printParens( int n ) {
        if ( n > 0 ) {
            System.out.print( "(" );
            printParens( n-1 );
            printParens( n-1 );
            System.out.print( ")" );
        }
    }

Set up a recurrence relation to count the number of characters, c(n):

• c(n) = 0 if n = 0
• c(n) = 2 + 2c(n-1) if n > 0

Looking for a pattern in the arithmetic implied by this definition of c yields the following:

The apparent pattern is that c(n) is the sum of the powers of 2 from the first through the n^th. This sum has a closed form of c(n) = 2ⁿ⁺¹ - 2. Prove that this closed form is correct for the recurrence relation by induction on n.

For the base case, consider n = 0. According to the recurrence, c(0) = 0, and 2⁰⁺¹ - 2 = 2¹ - 2 = 2 - 2 = 0.

For an induction hypothesis, assume that c(k-1) = 2^k - 2 for some k-1 >= 0.

Show that c(k) = 2^k+1 - 2.

• c(k) = 2 + 2c(k-1) from the recurrence relation
• = 2 + 2(2^k - 2) from the induction hypothesis
• = 2 + 2^k+1 - 4
• = 2^k+1 - 2