SUNY Geneseo Department of Computer Science

Problem Set 4—Divide and Conquer

CSci 242, Spring 2013

Prof. Doug Baldwin

Due Friday, February 8

Purpose

This exercise reinforces your ability to design divide-and-conquer algorithms.

Background

Divide-and-conquer is one of several common algorithm design styles, characterized by splitting a large problem instance into several smaller ones, solving them recursively, and then combining their solutions into a solution to the original problem. Sections 2.3.1, 4.1 and 4.2 of our textbook present examples of divide-and-conquer algorithms. We will discuss divide-and-conquer in class on February 5.

Exercise

Solve each of the following problems.

Problem 1

Given a real number, x, and a natural number n, xⁿ can be defined by the following recursive function:

xⁿ = 1 if n = 0
xⁿ = (x^n/2)² if n > 0 and n is even
xⁿ = x (x^(n-1)/2)² if n > 0 and n is odd

Use this recursion to give a divide-and-conquer algorithm for computing xⁿ. Explain how your algorithm meets the definition of “divide and conquer.”

Problem 2

Suppose you have an array, A, containing n numbers sorted into increasing order. You want to construct a balanced binary tree containing the numbers in A. Give a divide-and-conquer algorithm to do so.

Problem 3

A bitonic array is an array of numbers that consists of an increasing first part followed by a decreasing second part. More precisely, an array, A[1..n], is bitonic if and only if there is an index i, 1 ≤ i ≤ n, such that the A[1..i] is strictly increasing, and A[i..n] is strictly decreasing. For example the array 2, 5, 8, 7 is bitonic, with i = 3. Give a divide and conquer algorithm that finds the maximum element in a bitonic array (you can assume all elements are distinct).

Follow-Up

I will grade this exercise in a face-to-face meeting with you. During this meeting I will look over your solutions, ask any questions I have about them, answer any questions you have, etc. Even though we will have a chance to talk about your solutions, please bring them in writing to the meeting—that will speed things along.

Each meeting should take about 15 minutes. Please schedule your meeting by signing up on the schedule sheet outside my office or electronically via Google calendar. If you work in a group on this exercise, the whole group can have a single meeting with me. Make sure that your meeting ends by the end of the day on the due date above.