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
<= (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.
- 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
- x = A[i].x y = A[i].y for dx = -1 to 1:
- for dy = -1 to 1:
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
- return found a collision
- for dy = -1 to 1:
- // 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).