This is an open-book, open-Internet exam. Do not consult with people (in person, electronically, or otherwise) other than Jeff Ondich about this exam. Justify your answers, and cite your sources.
(18 points) Voronoi diagrams.
As we discussed briefly in class, there are two classes of algorithms that construct the Voronoi diagram of an N-point set in O(N log N) time (Shamos and Hoey's divide-and-conquer approach and Fortune's sweep-line approach). Parts (b)-(e) of this excercise will guide you through a proof that Voronoi diagram construction requires Ω(N log N) time, guaranteeing that the divide-and-conquer and sweep-line strategies are optimal.
Suppose your point set P = {(x1,0), (x2,0),...,(xN,0)}. That is, P consists of N points on the x-axis.
Note that you may not assume that x1, x2,...,xN are in numerical order. However, we can refer to the sorted order by defining k1 to be the index of the smallest x, k2 to be the index of the next smallest x, and so on. Thus, the x's in sorted order are xk1 < xk2 < ... < xkN.
Sketch the Voronoi diagram of P.
(13 points) The linear-time selection algorithm.
Recall the "groups-of-five" algorithm (sometimes known as "BFPRT" after its discoverers Blum, Floyd, Pratt, Rivest, and Tarjan) for finding the kth-smallest item in an unordered list of N items, where k ranges from 0 to N - 1.
Suppose your list is L = [30, 14, 16, 4, 28, 5, 33, 3, 22, 38, 29, 20, 21, 15, 19, 7, 8, 25, 13, 31, 35, 37], and you seek the 18th smallest item (that is, item k = 18--known more colloquially as the 19th smallest item). The BFPRT algorithm begins by splitting the list into groups of five items [30, 14, 16, 4, 28], [5, 33, 3, 22, 38], etc., and eventually makes one or more recursive calls to the same algorithm.
Show exactly which recursive calls get made by the top-level call to this
algorithm with the data above. That is, if the top-level call is
SelectItem(L, 18)
where L
is the long list above,
then exactly which parameters are passed to SelectItem
in the
recursive calls made by SelectItem(L, 18)
? (Note that I am
definitely not asking you to trace the entire recursion down to
the base cases. Instead, I want to know how many times does
SelectItem(L, 18)
itself call SelectItem
directly, and with what parameters?)
(10 points) The Boyer-Moore algorithm.
Consider an instance of the Boyer-Moore algorithm where we are looking for the string "panamanian" inside the string "the man on an island with a mania for panama hats and anions is an amanuensis and is also panamanian".