Computer Science 3650
Summer 2000
Take home exam 2

Answer all of the following questions. Write the answer to each question on a separate sheet of paper. Do not collaborate with others on this. Do your own work.

  1. Let X = x1x2...xn be a string of n characters. A proper prefix of X is a string x1x2...xk where k < n, consisting of an initial part of X (and not all of X). A proper suffix of X is a string xkxk+1...xn where k > 1, consisting of a final part of X (and not all of X). For example, abc is a proper prefix of abcde, and cde is a proper suffix of abcde.

    Give an algorithm that, given string X, produces the longest string that is both a proper prefix of X and a proper suffix of X. For example, if X is abcabc, then the algorithm should produce string abc. The algorithm must run in time O(n), where n is the length of X. Less efficient algorithms are unacceptable.

    Hint. Do not approach this problem in an ad-hoc way. Use the Knuth-Morris-Pratt string matching algorithm. Look at the way that algorithm works, including the pattern matching machine.

  2. One way to analyze algorithms is via a potential method. This method is used for algorithms that work by manipulating a data structure in steps, and that can take much longer for some steps than for most steps.

    The idea is to define a potential function that gives a number for each possible data structure. Then the amortized time of a step of the algorithm is defined to be the actual cost of the step minus the decrease in potential of the data structure.

    For example, suppose that a particular operation starts with a data structure that has a potential of 8. The step performs 4 basic operations, and modifies the data structure so that its potential is 5. Then the potential has decreased by 3, so the amortized time of the step is 4 - 3 = 1. Suppose that the next step performs 3 basic operations, and modifies the data structure so that its potential is now 6. Then the potential has increased from 5 to 6, so the potential decrease is -1. The amortized cost of this step is 3 - (-1) = 4.

    Consider that Graham scan algorithm for computing the convex hull of a collection of points in the plane. Imagine that the points have already been sorted, and we are only analyzing the scan phase. Graham's algorithm maintains a stack of points. Let the potential of the stack be the number of points in the stack.

    A step of Graham's algorithm is to process one point and add it to the stack (possibly popping some other points in the process). Show that the amortized cost of each step is O(1).

    The total cost of n steps is no larger than n times the amortized cost per step, plus the total potential decrease in the data structure during the course of the algorithm. Show that the cost of the scan phase of Graham's algorithm is linear by noting that the potential cannot be lower at the end of the algorithm than it is at the start of the algorithm, and that the amortized cost per operation is constant.

  3. Say that a point (x,y) in the plane dominates another point (u,v) if x > u and y > v. Given a collection of n points, you would like to remove all points that are dominated by any other points in the collection, and produce only the undominated points. Describe an O(n lg(n)) time algorithm to do this.

    Hint. There are many ways to solve this problem, and I will accept any method that works, as long as it runs within the required time bound. A suggestion is to use a modification of the Graham scan algorithm.

  4. Work problem 16-4 (page 326) in Cormen/Leiserson/Rivest. Here is a rewording of that problem, to clarify what is wanted.

    The input to the problem has two parts.

    1. The first part is a tree that describes a company hierarchy, with the president at the top. There is a node of the tree for each employee. The children of a node V are the employees whom V directly supervises.

    2. The second part is a table giving a conviviality rating for each employee. The rating is a positive integer.

    The algorithm must solve the following optimization problem. The goal is to select a subset of the employees to invite to a party. It is required that, if employee V is invited to the party, then none of the employees that V directly supervises can also be invited. (In terms of the tree, the algorithm must select a collection of nodes in the tree such that no two adjacent nodes are both selected.)

    The goodness of a solution is the sum of the conviviality ratings of all of the selected employees. Among all possible solutions, the algorithm must produce one that has the highest possible goodness. If there are several equally good solutions, the algorithm can produce any of those equally good solutions.

    Only solve part (a) of the problem. (Part (b) asks how to solve the problem if you are required to select the root of the tree.) Give a clear description of how the algorithm works.

    Hint. Use dynamic programming. Should you sweep up the tree or down?