We saw how to do order statistics deterministically in linear time (9.3), saw Karatsuba's Algorithm (Exercise 30-1) and did some computational geometry, the closest-pair algorithm (33.4). Finally, we talked about some of the ideas behind FFT without going into details (see Chapter 30 for full coverage). We began talking about dynamic programming using Fibonacci numbers as an example (see Exercise 31-3).

Next week we will cover dynamic programming in depth, starting with 15.4 and 15.5 (also 15.3) and 25.2.

If you are interested in latex, check out MikTex, you can use it with any texteditor, WinEdt is very nice though (but not free).

Submission: you can submit the homework to me either by hardcopy in class or email it to me.

1. [Quicksort, 5pt; book 9.3-3] How can you make Quicksort run in O(n log n) time? Deterministically, not randomized. Why, do you think, does the randomized version perform better?

2. [Median, 15pt; book 9.3-5] Suppose you have an algorithm that finds the median in time O(n). How can you use this algorithm to solve the general selection problem in time O(n)? That is, you want to find the kth element in an n-element array in time O(n) using the median-algorithm as a black box.

3. [Divide & Conquer] You are given an array A of length n and you want to determine whether there is a majority element, that is, an element that occurs more than n/2 times in the array. For example, A = [4, 1, 4, 4, 7] has a majority element, namely 4, but A = [4, 1, 4, 1, 7] does not have a majority element. The only operation you are allowed on the array are equality comparisons, i.e. A[i] = A[j] or A[i] = x. In particular, you cannot ask whether A[i] <= A[j] (the elements of the array might not be integers, and might not be sortable), so there is no meaning to sorting A.

a) [20pt] Give an O(n log n) divide & conquer algorithm that determines whether there is a majority element in the array, and, if so, what it is.

b) [Extra Credit, 20pt] Give an O(n) divide & conquer algorithm that determines whether there is a majority element in the array, and, if so, what it is.

4. [Multiplication, 10pt] Suppose you can built an algorithm that computes the square of an integer with n digits in time O(f(n)), for some function f(n). Show that you can compute the product xy of two n digit integers in time O(f(n)). So squaring an integer is as hard as multiplying two integers.

5. [Farthest Points, 20pt] You are given a set of n points in the plane; your goal is to find the farthest pair of points, that is, the two points with the largest Euclidean distance between them. Observe that any two farthest points must be on the boundary of the convex hull of the pointset (see Section 33.3 for what a convex hull is). You already have done some preprocessing and limited your pointset to the points on the convex hull. Moreover you have stored these points in an array A[1..n] that lists the points on the boundary in clockwise order as you move along the boundary of the convex hull. Give an O(n) algorithm that finds the two farthest points given this information. You can assume that there is a function d(). such that d(A[i], A[j]) computes the distance between points A[i] and A[j] accurately. Hint: for each point A[i] find the farthest point.  How does the farthest point change as you move from A[i] to A[i+1]?

6. [Dynamic Programming, 20pt] A robot can take steps of 1 or 2 or 3 meters along a line. Write a linear time algorithm that computes how many ways a robot can walk a line of length n. For example, if n = 4, the robot could walk 1 + 1 + 1 + 1 or 1 + 1 + 2 or 1 + 2 + 1 or 2 + 1 + 1 or or 2 + 2 or 1 + 3 or 3 + 1. Hint: write it as a recurrence.