Problem Set 5—The Master Method

Purpose

Background

Exercise

Solve the following problems.

Problem 1

Exercise 4.5-1 from our textbook.

Problem 2

Derive a recurrence relation for the execution time of binary search, and use the master method to solve that recurrence. For reference, here is a binary search algorithm that searches the section of array A between positions first and last (inclusive) for value k:

    boolean search( A, first, last, k )
        if first > last
            return false
        else
            mid = ( first + last ) / 2
            if k < A[mid]
                return search( A, first, mid-1, k )
            else if k > A[mid]
                return search( A, mid+1, last, k )
            else
                return true

Problem 3

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 use the master method to solve that recurrence.

Follow-Up

I will grade this exercise in a face-to-face meeting with you. Please bring a written solution to your meeting. During the meeting, I will look over your solution, give you my reactions to it, answer any questions you have about it, etc.

Meetings should take about 15 minutes, although you are welcome to reserve a longer time if you have a lot of questions. Please sign up for your meeting on the schedule outside my office. If you work in a group, the entire group can schedule a single meeting with me. You should be ready to grade this exercise shortly after class on the “Complete By” date above; however, you have until the end of the “Grade By” date to actually meet with me.