SUNY Geneseo, Department of Computer Science

Answers to Hour Exam 2

CSci 141 , Fall 2003

Prof. Doug Baldwin

Here are my solutions to the questions on our second hour exam. These answers are slightly more detailed than I would expect from you on a test, since I am trying not only to show you good answers, but also explain why I consider them good and/or how I would arrive at them. If you have any questions, please ask -- in person, by e-mail, in class, whatever you like.

Question 1

Write a recursive algorithm for binary trees that counts the number of nodes for which both subtrees are non-empty.

The algorithm is based on the following ideas: If the tree is empty, there are no nodes with non-empty subtrees. Otherwise, this tree might have two non-empty subtrees, or it might not. In the former case, the total number of nodes with non-empty subtrees is one (for this tree's root), plus the sum of the number of such nodes in the left and right subtrees. In the latter case, the total number of nodes with non-empty subtrees is just the sum of the number of such nodes in this tree's subtrees. (This tree may still have one non-empty subtree, and it may contain such nodes.)

    // In class ExtendedTree...
    public int count() {
        if ( this.isEmpty() ) {
            return 0;
        }
        else if (  ! this.left().isEmpty()  &&  ! this.right().isEmpty()  ) {
            return 1 + this.left().count() + this.right().count();
        }
        else {
            return this.left().count() + this.right().count();
        }
    }

Question 2

Do the execution times in the left two columns below support the hypothesis that time is Theta(n²)?

To test this hypothesis, divide the average time by the square of the list size, and see if the ratio seems to converge towards a constant of proportionality as list size increases. The right two columns of the table show the calculations. Since the ratios steadily decline, the data do not support the hypothesis.

Question 3

Draw a binary search tree containing the numbers 1, 4, 6, and 7.

Any tree with no more than two children per node (binary), and with small values to the left of larger ones (a search tree) is correct. For example...

Question 4

Derive (and prove, if necessary) a formula for the number of primitive List messages (“isEmpty,” “first,” and “rest”) that the following algorithm sends, in terms of the length of the list.

    // In class SearchableList...
    int count( Object x )
        if ( this.isEmpty() )
            return 0
        else if ( this.first().equals(x) )
            return 1 + this.rest().count( x )
        else
            return this.rest().count( x )

Let n stand for the length of the list. If the list is empty (n = 0), the algorithm simply sends one isEmpty message. If the list is non-empty (n > 0), the algorithm sends an isEmpty message, a first, and (no matter which way the conditional goes) a rest and a recursive count. The recursive count message is sent to a list of n-1 items. Therefore the total number of primitive List messages the algorithm sends can be described by the following recurrence relation:

M(n) = 1 if n = 0

M(n) = 3 + M(n-1) if n > 0

This recurrence is one of those whose general closed form is kn + c, with k = 3 and c = 1, so the specific closed form is

M(n) = 3n + 1

Having identified the recurrence as one for which an already-proven general rule provides the closed form, you don't need to further prove that this specific closed form is correct. However, you could go ahead and do so if you wanted, in which case the proof would be an induction on n.