CSC 491

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.

Marcus Schaefer

Last updated: September 25th, 2006.