Computer Science 3650
Summer 2001
Practice Questions for Exam 2

This is a closed book exam, but you may use one page of prepared notes. Answer all of the questions.

1. Consider the definition

       h(0) = 1
       h(n) = h(n-1) + h(floor(n/2)) + 1
     

   For example, h(2) = h(1) + h(1) + 1 = 3, h(3) = h(2) + h(1) + 1 = 5, etc. An obvious algorithm to compute h is a recursive one, based directly on the defining equations. Is that algorithm efficient? Why or why not? If not, how can the algorithm be improved? Justify your answer.

2. What are the main principles of scan algorithms? That is, what characteristics do they share?

3. What are the main principles of dynamic programming algorithms? That is, what characteristics do they share?

4. This is 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?

5. Show the Knuth/Morris/Pratt pattern matching machine for pattern aabaabcab.

6. Consider a problem where the input is a list of n points in the plane plus one more point called Q. Describe an algorithm to sort the points in clockwise order from Q. If your list of points after sorting is p₁,...,p_n, and you draw a line segment from Q to each point, then as you go from x₁ to x₂, ..., to x_n, you should see the line segments sweep in a clockwise direction.

   Your algorithm should run in time O(n log(n)), assuming arithmetic operations take constant time.