SUNY Geneseo, Department of Computer Science

Solutions to Exam 2 Practice Questions

CSci 141 , Fall 2003

Prof. Doug Baldwin

Here are my solutions to the Practice Questions for the second hour exam.

Question 1

Write a recursive algorithm that tests whether all the items in a list are equal to each other.

The algorithm is based on the recursive insight that all items in a list with 1 or fewer items are equal, because there aren't enough items for any to be unequal. In longer lists, all items are equal if the first two items are equal, and all items in the tail of the list are equal:

    // In class ExtendedList...
    boolean allEqual()
        if ( this.isEmpty() || this.rest().isEmpty() )
            return true
        else if ( this.first().equals( this.rest().first() ) )
            return this.rest().allEqual()
        else
            return false

Question 2

Prove that the following algorithm computes the sum of the numbers in a list:

    // In class NumberList
    sum()
        if this.isEmpty()
            return 0
        else
            return this.first() + this.rest().sum()

The proof is by induction on the length of the list.

The base case is an empty list. As defined in the question, the sum of the numbers in an empty list is 0, and the algorithm returns 0 because the "this.isEmpty()" test succeeds.

For the induction hypothesis, assume that a "sum" message sent to a list of k-1 numbers, k-1 >= 0, will return the sum of those numbers.

Show that a "sum" message sent to a list of k numbers will return the sum of those numbers. Since k-1 >= 0, k > 0, meaning that the list is not empty. Thus the "this.isEmpty()" test fails and the algorithm returns "this.first()" plus "this.rest().sum()." "this.rest()" contains k-1 numbers, so by the induction hypothesis "this.rest().sum()" returns their sum. Since "this.first()" is the only other number in the original list, adding it to "this.rest().sum()" computes the sum of all numbers in the list.

Question 3

Are the list sizes and average search times in the left two columns below consistent with the hypothesis that the algorithm runs in time Theta(n)?

To test the hypothesis, divide the average time by the list size and see if the ratio seems to converge towards a constant of proportionality as list size increases. The results of this division appear in the right-most column above. Because the ratios seem to converge to 2, the data are consistent with the Theta(n) hypothesis.

Question 4

Show how you would declare a “Node” class for lists in which each node has a link to both the previous and next nodes.

Each node needs member variables for the data in the node, and for the two links. All of these members are public, in the expectation that clients will implement list algorithms (the clients will most likely be classes that represent some sort of list):

    class Node
        Object data
        Node previous    // Link to the previous node in the list, or null if this is first node
        Node next        // Link to the next node, or null if this is the last node