SUNY Geneseo, Department of Computer Science

Solutions to Sample Problems for Exam 1

CSci 141 , Fall 2003

Prof. Doug Baldwin

Here are my solutions to the Sample Questions for exam 1.

Question 1

(Write a recursive algorithm that computes xⁿ)

The recursion is based on the idea that x⁰ = 1, while xⁿ can be written as x * x^n-1.

    power( x, n )
        if n == 0
            return 1
        else
            return x * power( x, n-1 )

Question 2

(How many letters does the following algorithm print, as a function of n:

    printChars( int n )
        if n > 1
            print “aa”
            printChars( n – 1 )
            print “bbb”
        else
            print “c”

)

Set up a recurrence relation to count the number of letters. Let the function that relates the number of letters to n be L(n). Since the algorithm prints 1 letter ("c") when n = 0, and 5 (2 "a's" and 3 "b's"), plus however many the recursive message prints, when n > 0, the recurrence is

• L(n) = 1 if n = 0
• L(n) = 5 + L(n-1) if n > 0

Looking at some values of L(n) gives

It looks like L(n) = 5n + 1, and this can be proved by induction on n:

Base Case: n = 0

From the first line of the recurrence, L(0) = 1 = 5*0 + 1.

Induction Hypothesis: Assume that for some natural number k-1 >= 0, L(k-1) = 5(k-1) + 1.

Induction Step: Show that L(k) = 5k + 1.

• L(k) = 5 + L(k-1), from the recurrence relation
• = 5 + 5(k-1) + 1, replacing L(k-1) with 5(k-1) + 1 per the induction hypothesis
• = 5 + 5k - 5 + 1
• = 5k + 1

So the final answer is that printChars(n) prints 5n + 1 letters.

Question 3

(A clock function with a resolution of 1 millisecond measures the following times:

1, 2, 2, 1, 2, 2, 2, 1, 2, 1

A: What would you give as the time for this operation?

B: What do you think is the main source of error in these measurements?)

Part A

The best estimator of the "true" value of a series of measurements is their average, which in this case is ( 1 + 2 + 2 + 1 + 2 + 2 + 2 + 1 + 2 + 1 ) / 10 =  16 / 10 = 1.6 milliseconds.

Part B

Because all the times are within the clock's resolution of each other, the main error source is probably the +/- 1 count error inherent in clock functions. This is a random error.