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.

Problem 1: 15 points

Problem 2: 15 points

# 1. Multiple select

If m = 2, we can simply find the rank k1 and k2 elements in time O(n) by running deterministic select twice. A similar bound holds if m = 1. For larger m, we can find the median in O(n) time and then partition the input array A into two arrays A1 and A2 of size n/2 each, where A1 contains all elements of rank n/2 or less and A2 contains all elements of rank n/2+1 or greater. Similarly we can partition the list of ranks into those less than or equal to n/2 and those greater than n/2. This reduces the original problem to two equivalent subproblems of size n/2 each, with m1 and m2 ranks to be sought within each, giving a two-variable recurrence:

• T(n, m) = T(n/2, m1) + T(n/2, m2) + O(n),

where m1 + m2 = m. The base for the recurrence is T(n,1) <= T(n,2) = O(m).

We wish to show that T(n, m) = O(n lg m). Let us show the stronger result that T(n,m) <= an lg m for a constant a to be determined later. The basis is the observation that T(n,2) <= an for sufficiently large a and that T(n,n) = O(n) <= an for sufficiently large a. For larger values of n and m, assume by induction that the bound holds for any (n',m') with n' <= n and m' <= m with at least one of these inequalities strict. Let m1=m' and m2=m-m'. Then

• T(n,m) = T(n/2,m')+T(n/2,m-m')+cn

<= (an/2) (lg m' + lg(m-m')) + cn = (an/2) lg(m'(m-m')) + cn

Now observe that at least one of m' and m-m' is less than or equal to m/2. Without loss of generality, assume that m' <= m/2. We trivially have m-m' <= m, so lg(m'(m-m') <= lg((m/2)m) = lg(m2/2) = 2 lg m - 1. We thus have

• T(n,m)

<= (an/2) lg(m'(m-m')) + cn

<= (an/2) (2 lg m - 1) + cn = an lg m - (an/2) + cn

<= an lg m,

provided a >= 2c.

# 2. You sunk my battleship

## 2.1. Hash table solution

Construct a hash table with keys of the form (x,y). Insert each ship into the hash table in O(n) expected time. For each ship, check each of the 9 squares that would cause a collision, reading the hash table to see if there is a ship there. This takes (n ship) * (9 squares) * (O(1) time) = O(n) time.

## 2.2. Very big array solution

By cheating a bit we can do this deterministically. The trick is to use an m-by-m array which we do not initialize (since initializing the array would take Theta(m2) time). Because we do not initialize the array, we have to assume that its initial contents are arbitrary, and the correctness of our algorithm cannot depend on these initial values. But this is actually enough: we can store the identity of each ship at its position, and then check that what we read out of the big array is consistent with our input before trusting it.

In the pseudocode below, we assume that the input is an array A of records, so that the coordinates of the i-th ship are given by A[i].x and A[i].y.

{{{DetectFraternization(A, m):

• let B be an uninitialized m-by-m array of integers // store the ships for i = 1 to length(A):
• B[A[i].x, A[i].y] = i
// look for collisions for i = 1 to length(A):
• x = A[i].x y = A[i].y for dx = -1 to 1:
• for dy = -1 to 1:
• if(
• 1 <= x + dx <= m

• and 1 <= y + dy <= m and (dx != 0 or dy != 0) and 1 <= B[x+dx,y+dy] <= length(A) and A[B[x+dx,y+dy]].x = x+dx and A[B[x+dx,y+dy]].y = x+dy

) then
• return found a collision
• // else return no collision

}}

This pseudocode has many nested loops, but all but the outermost span a constant range. So the total running time is O(n).

2014-06-17 11:58