Algorithms Practice Problems

Finding the Peak Entry in a Down-Up Array

1. (20 points) Suppose you are given an array A with n entries, with each entry holding a distinct number (i.e., no two numbers of A are equal). You are told that the sequence of values A[1];A[2]; : : : ;A[n] is down-up ordered: For some index p between 1 and n, the values in the array entries decrease down to position p in A and then increase the remainder of the way until position n. (So if you were to draw a plot with the array position j on the x-axis and the value of the entry A[j] on the y-axis, the plotted points would decline until x-value p, where they'd achieve their minimum, and then rise from there on.) You'd like to nd the \peak entry" p without having to read the entire array { in fact, by reading as few entries of A as possible. Show how to nd the entry p by reading at most O(log n) entries of A. In other words, design an O(log n) time algorithm to nd the peak entry p. For example, let A = f12; 11; 8; 6; 1; 10; 13; 19; 27g, which is be a down-up array. The peak entry of A is 1. So the output of your algorithm is either 1 or the index of 1 in A. 2. (20 points) Suppose you are consulting for site location of an emergency exit of a shopping street. There are n stores, represented by n points p1; p2; : : : ; pn on the line. Let the line be x-axis. We are given the x-coordinate of the n stores pi = (xi; 0) for i = 1; 2; : : : ; n. Note that the stores are not given in any sorted order. Our goal is to pick an optimal location for the emergency exit (i.e., nd the x-coordinate of the exit) such that the total sum of the distances of stores to the exit is minimized. For simplicity, we assume no two stores have the same x-coordinate. Design an O(n) time algorithm to compute an optimal location for the emergency exit. 3. (30 points) Here is a generalized version of the selection problem, called multiple selection. Let A[1 n] be an array of n numbers. Given a sequence of m sorted integers k1; k2; : : : ; km, with 1 k1 < k2 < < km n, the multiple selection problem is to nd the ki-th smallest number in A for all i = 1; 2; : : : ;m. For simplicity, we assume that no two numbers of A are equal. For example, let A = f1; 5; 9; 3; 7; 12; 15; 8; 21g, and m = 3 with k1 = 2, k2 = 5, and k3 = 7. Hence, the goal is to nd the 2nd, the 5-th, and the 7-th smallest numbers of A, which are 3, 8, and 12, respectively. (a) Design an O(n log n) time algorithm for the problem. (5 points) 1 (b) Design an O(nm) time algorithm for the problem. Note that this is better than the O(n log n) time algorithm if m < log n. (5 points) (c) Improve your algorithm to O(n logm) time, which is better than both the O(n log n) time and the O(nm) ti