Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

/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 k1, k2, ... km, where m >= 2, and an unsorted array of n elements, and returns the elements with rank k1, k2, ... km 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 (x1,y1) and (x2,y2) are too close if |x1-y1| and |x2-y2| 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.

2014-06-17 11:58