CLRS 9.3 Selection in worst-case linear time | Rip's Infernal Majesty

CLRS 9.3 Selection in worst-case linear time | Rip's Infernal Majesty

9.3-1

In the algorithm SELECT, the input elements are divided into groups of 5. Will the algorithm work in linear time if they are divided into groups of 7? Argue that SELECT does not run in linear time if groups of 3 are used.

For groups of 7, the number of elements greater than x, or less than,  is at least 2n/7 – 8, we have

T (n) ≤ T (n/7) + T (5n/7 + 8 ) + O(n)

This works in linear time as can be proved similar to case of group 5.

For groups of 3, the number of elements greater than x, or less than,  is at least n/3 – 4, we have

T (n) ≤ T (n/4) + T (n/3 + 4) + O(n)

We can prove by induction this dose not work in linear time.

9.3-2

Analyze SELECT to show that if n ≥ 140, then at least ⌈n/4⌉ elements are greater than the median-of-medians x and at least ⌈n/4⌉ elements are less than x.

3n / 10 = 3*140/10 = 36, while 140/4 = 35.

9.3-3

Show how quicksort can be made to run in O(n lg n) time in the worst case.

Use the SELECT procedure in this chapter for Partition in Quicksort.

9.3-5

Suppose that you have a "black-box" worst-case linear-time median subroutine. Give a simple, linear-time algorithm that solves the selection problem for an arbitrary order statistic.

Just as Randomized-Select in textbook using Randomized-Partition, we use linear-time our median subroutine to do the partition every time. Because we get the median thus partition of an array always results in two subarrays at most half the number of elements of that array. So we have T (n) ≤ T (n/2) + O(n) = O(n).

9.3-7

Describe an O(n)-time algorithm that, given a set S of n distinct numbers and a positive integer k ≤ n, determines the k numbers in S that are closest to the median of S.

We first use linear time selection to find the (n − k)/2, n/2, and (n + k)/2 elements of the set S. Then we go over the set S once to find the numbers less than (n+k)/2 element, also greater than the (n−k)/2 and not equal to the n/2 one element. This takes O(n) time as we use linear time selection three times and traverse the n numbers in S once.

9.3-8

Let X[1 .. n] and Y [1 .. n] be two arrays, each containing n numbers already in sorted order. Give an O(lg n)-time algorithm to find the median of all 2n elements in arrays X and Y.

Because X and Y are already sorted, we first select in O(1) the medians of X and Y, say x and y. We compare X[x] with Y[y], say X[x] <= Y[y]. Then we repeat the procedure on two new arrays which are X[x..n], Y[y..n], till there is ≤ 2 elements left in each array. Return the median of these 4 numbers. There are O(lg) Selection of O(1) and O(lg n) comparisons, so this is O(lg n) time algorithms.

9.3-9

Professor Olay is consulting for an oil company, which is planning a large pipeline running east to west through an oil field of n wells. From each well, a spur pipeline is to be connected directly to the main pipeline along a shortest path (either north or south), as shown in Figure 9.2.

Given x- and y-coordinates of the wells, how should the professor pick the optimal location of the main pipeline (the one that minimizes the total length of the spurs)? Show that the optimal location can be determined in linear time.

When n is even, as long as the numbers of wells to the north and to the west of the main pipeline are equal is an optimal location.

If n is odd, let the main pipeline pass through the median of n wells would achieve optimal. Because otherwise make the pipeline move north or west by y, the new total length of all spur pipelines are L = L0 + (n+1)x – n*x > L0.

To solve we just need to select the median of n wells by their y-coordinates. It's linear time.

Read full article from CLRS 9.3 Selection in worst-case linear time | Rip's Infernal Majesty