Problem 1: 15 points

Problem 2: 15 points

1. Multiple select

If m = 2, we can simply find the rank k₁ and k₂ 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 A₁ and A₂ of size n/2 each, where A₁ contains all elements of rank n/2 or less and A₂ 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 m₁ and m₂ ranks to be sought within each, giving a two-variable recurrence:

• T(n, m) = T(n/2, m₁) + T(n/2, m₂) + O(n),

where m₁ + m₂ = 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 m₁=m' and m₂=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(m²/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(m²) 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).