Problem Set 4—Recurrence Relations

Purpose

This problem set reinforces your understanding of recurrence relations and how to use them to analyze the execution time of recursive algorithms.

Background

This problem set is based on material covered in lectures on from September 29 through October 8. This material is also developed in chapter 4 of our textbook.

Activity

Solve each of the following problems.

Problem 1

Show that recurrence relations of the form

T(0) = c
T(n) = T(n-1) + k, n > 1

and

T(0) = c
T(n) = kT(n-1), n > 1

where c and k are constants, have exact closed forms T(n) = nk + c and T(n) = ckⁿ respectively.

Problem 2

Exercise 4.5-1 in our textbook (use the master method to find asymptotic closed forms for 4 recurrences).

Problem 3

Here are two possible recursive algorithms for finding the smallest element in a list A of numbers (the notation A[i..j] means elements in positions i through j of A, inclusive; A[i] means the element in position i):

min1( A )
    if length(A) = 1
        return A[1]
    else
        x = min1( A[2..length(A)] )
        if x < A[1]
            return x
        else
            return A[1]

min2( A )
    if length(A) = 1
        return A[1]
    else
        mid = ⌊ length(A) / 2 ⌋
        x = min2( A[1..mid] )
        y = min2( A[ mid+1 .. length(A) ] )
        if x < y
            return x
        else
            return y

Which, if either, of these algorithms is asymptotically fastest? Support your answer with appropriate derivations of both asymptotic execution times.

Problem 4

Here is an algorithm (far more complicated than necessary, by the way) that rearranges the section of array A between positions first and last inclusive into a random order (i.e., the algorithm “shuffles” A). The algorithm works by recursively shuffling the first and last thirds of A, and then swapping the middle and last thirds of A.

shuffle( A, first, last )
    if first < last
        third = ( last - first ) / 3
        shuffle( A, first, first + third - 1 )
        shuffle( A, last - third + 1, last )
        for i = 0 to third - 1
            swap A[ first + third + i ] and A[ first + 2*third + i ]

Derive a recurrence relation for the execution time of this algorithm as a function of the size of the section of A being shuffled, and find an asymptotic closed form for that recurrence.

Follow-Up

I will grade this exercise in a face-to-face meeting with you. During this meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Please bring a written solution to the exercise to your meeting, as that will speed the process along.

Sign up for a meeting via Google calendar. If you worked in a group on this exercise, the whole group should schedule a single meeting with me. Please make the meeting 15 minutes long, and schedule it to finish before the end of the “Grade By” date above.