CS 252: Algorithms
Takehome exam
Due 9:40 AM Friday, 6 March 2009

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.

1. (18 points) Voronoi diagrams.

   1. Sketch the Voronoi diagram and the Delauney triangulation for the point set {(1,1), (2,3), (3,2), (4,3), (6,0), (6,2)}.

   2. 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.

   3. Because of the special nature of P, we expected the Voronoi diagram to be a bit odd, and it was. Similarly, the Delauney "triangulation" is weird. Draw it.
   4. A triangulation can be stored as a list of edges connecting adjacent vertices in the triangulation. In the Delauney triangulation you drew above, how many edges are there? List them.
   5. Suppose you have already constructed the Delauney triangulation of P, and thus you have computed the list of edges you provided in part (d). Unfortunately, although you have the complete list of edges in the triangulation, you may not have stored them in left-to-right order. Show how you can, in O(N) time, sort the Delauney edges into left-to-right order.
   6. Now that you have the Delauney edges in left-to-right order, show how you can print out the x's in numerical order.
   7. Briefly explain why all the foregoing steps guarantee that Voronoi diagram construction must take Ω(N log N) time.
   8. The End. Take a bow.

2. (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.

   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?)

   2. Consider the problem of splitting a list L into three approximately-equal-sized lists A, B, and C, where all the elements of A are smaller than all the elements of B, which are in turn smaller than all the elements of C. Propose an efficient algorithm for solving this problem. Make sure your assumptions are clear, and that you state clearly what you mean by "approximately-equal-sized." Discuss the running-time complexity of your algorithm.
3. (3 points) I'd like to read an entertaining story over spring break. Any suggestions?

4. (10 points) The Boyer-Moore algorithm.

   1. Read about the Boyer-Moore algorithm. Its Wikipedia page is pretty good, but it also shows up in lots of Algorithms textbooks, and of course on-line.

   2. 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".

      • Show the data structures or tables that are computed during the preprocessing phase of the Boyer-Moore algorithm in this case.
      • List the character comparisons that are performed during the string matching phase of the algorithm. You'll need to come up with a way to express this clearly--perhaps lining up "panamanian" underneath the larger string at various horizontal positions will help. How many character comparisons are made by the time the search string is found?
   3. Briefly, why is this algorithm relevant in bioinformatics?