Problem Set 6—The Master Method

Purpose

Background

Recurrence relations are simply a certain sort of recursively defined mathematical function. Many recurrence relations have “closed forms,” i.e., non-recursive definitions of the same function, and mathematical techniques for finding some closed forms are well known. Furthermore, it is easy to find a recurrence relation that describes the execution time of a recursive algorithm. Thus, recurrence relations form an ideal “bridge” between recursive algorithms and mathematical descriptions of their execution times.

Section 2.3.2 of our textbook illustrates how to set up a recurrence relation for the execution time of a recursive algorithm, and chapter 4 discusses ways of finding closed forms. Of particular note, section 4.5 presents the “master method,” a very fast way to find asymptotic closed forms for many of the recurrences that arise from divide-and-conquer algorithms. We began discussing these things in class on February 14 and will continue on February 19.

Exercise

Solve each of the following problems.

Problem 1

Derive the asymptotic worst-case execution time of the variation on binary search presented in problem set 5. The variation counts the occurrences of a key, k, in the section of array A between positions first and last; the corrected algorithm is as follows:

    count( k, A, first, last )
        if first > last
            return 0
        else
            mid = ⌊( first + last ) / 2⌋
            if k < A[mid]
                return count( k, A, first, mid-1 )
            else if k > A[mid]
                return count( k, A, mid+1, last )
            else
                return count( k, A, first, mid-1 ) + count( k, A, mid+1, last ) + 1

Problem 2

Derive the asymptotic execution time of the “first non-zero element“ algorithm presented in problem set 5. The algorithm finds the position of the first non-zero element between positions first and last in array A, given that there is at least one non-zero value in the section, and that all zero values appear before any non-zeros. The algorithm is as follows:

     firstNonZero( A, first, last )
        if first == last
            return first
        else
            mid = ⌊( first + last ) / 2⌋
            if A[mid] == 0
                return firstNonZero( A, mid+1, last )
            else
                return firstNonZero( A, first, mid )

Problem 3

One of the problems computer graphics systems face is that of filling with color a polygonal area inside a rectangular window—for example, filling the gray into this pentagon:

Here is an algorithm that solves this problem for a window with left edge coordinate x1, right edge coordinate x2, top coordinate y1, bottom coordinate y2, and shape s. All coordinates are inclusive, and the shape is an object with an inside method that returns True if a point is inside the shape and False if the point is outside.

    fill( x1, x2, y1, y2, s )
        if x1 == x2  &&  y1 == y2
            if s.inside(x1,y1)
                color pixel x1,y1 in foreground color
            else
                color pixel x1,y1 in background color
        else
            midx = ⌊( x1 + x2 ) / 2⌋
            midy = ⌊( y1 + y2 ) / 2⌋
            fill( x1, midx, y1, midy, s )
            fill( midx+1, x2, y1, midy, s )
            fill( x1, midx, midy+1, y2, s )
            fill( midx+1, x2, midy+1, y2, s )

Derive the asymptotic execution time of this algorithm on an n-by-n window, as a function of n.

Problem 4

For each of the recurrences in problem 4-1 in our textbook, determine whether the master method can be used to find a closed form. If so, use it to find the closed form; if not, explain why the master method does not apply.

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.

Schedule your meeting to last 15 minutes. Please sign up for your meeting on the schedule outside my office or via Google calendar. If you work in a group, the entire group can schedule a single meeting with me. Be sure your meeting ends by the end of the day on the due date above.