/Discuss this assignment. /Solutions are available.

1. Multiple select

Recall that there exists a deterministic algorithm that finds the k-th smallest element (also called the element with rank k) in an unsorted array of n elements in O(n) time. Suppose however that we want to find more than one element by its rank---for example, we may want to find the elements at the 10th, 20th, 30th, etc. percentiles. We can easily do this in O(n lg n) time by sorting the array, but perhaps we can do better if the number of elements we wish to extract is much less than n.

Devise a deterministic algorithm that takes as input a sorted list of ranks k₁, k₂, ... k_m, where m >= 2, and an unsorted array of n elements, and returns the elements with rank k₁, k₂, ... k_m using O(n lg m) time. If it makes the problem easier, you may assume that n is a power of 2.

2. You sunk my battleship

The Royal Navy of Ruritania positions its ships on an m-by-m grid, where each ship takes up one cell of the grid. To avoid problems with fraternization between crews of different ships, it is not permitted to have two ships in adjacent cells (including cells that are diagonally adjacent. Some examples of forbidden and permitted placements:

S---    -S--    ----
-S-- or -S-- or -SS-
----    ----    ----

Forbidden

-S--
---S
S---

Permitted

Formally, the position of each ship is described by a pair of coordinates (x,y), and two ships at (x₁,y₁) and (x₂,y₂) are too close if |x₁-y₁| and |x₂-y₂| are both less than or equal to 1.

Devise an algorithm that takes a list of n ship coordinates as input and detects whether any pair of ships is too close in expected O(n) time. You may assume that no two ships in the list have exactly the same coordinates.