College of Computer & Information Science Spring 2005 Northeastern University Handout 6 CSU690: Algorithms and Data 7 February 2005

Problem Set 3 (due Wednesday, February 16)

1. (5 + 5 = 10 points) Consider a set S of n distinct numbers given in unsorted order. Each of the following parts asks you to give an algorithm to determine two distinct numbers x and y that satisfy a stated condition. For each part, describe your algorithm and then briefly justify the correctness and the running time of the algorithm.

(a) In O(n) time, determine x, y ∈ S such that |x − y| is maximum.

(b) In O(n lg n) time, determine x, y ∈ S such that |x − y| is minimum.

2. (5 + 5 + 2 = 12 points) Stooge sort

Problem 7–3, pages 161-162.

3. (8 points) Generating a random uniform permutation

Exercise 5.3-4, page 105.

4. (5 + 5 = 8 points) The effect of group size on Select

In the algorithm Select covered in class and described in Section 9.3 of the text, the input elements are divided into groups of 5. Will the algorithm work in linear time if they are divided into groups of 3? How about groups of 7? Justify your answers.

(Hint: Obtain recurrence relations for both approaches, and solve them.)

5. (10 points) Locating the Central Post Office in Manhattan

We are given the coordinates (x_{1}, y_{1}), …, (x_{n}, y_{n}), for each of n houses in Manhattan. The distance between any two houses (a, b) and (c, d) is given by |a − c| + |b − d|. This is referred to as the Manhattan distance, since the streets in Manhattan are organized in a grid.

We would like to determine the location for a central post office in the city such that the sum of the distances of the n houses from the central post office is minimized. Design and analyze an efficient algorithm for this problem. The more efficient your algorithm is in terms of its worst-case running time, the more points you will get.

6. (10 bonus points) Selection from two sorted lists

Design and analyze an efficient algorithm to select the median from a set of m + n keys given in the form of two sorted lists, one of length m and the other of length n. For convenience, you may assume that the m + n keys are all distinct. (Hint: A running time of O(log(min{m, n})) is achievable.)