Computer Science 3650
Spring 2004
Solutions to 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. What is the definition of the prefix function that is used by the Knuth/Morris/Pratt algorithm?

   For a given pattern string p, the value pi(k) is defined to be the length of the longest proper prefix of p that is also a suffix of p.

2. Show the Knuth/Morris/Pratt prefix function for pattern aabaabcab.

   n	pi(n)
   1	0
   2	1
   3	0
   4	1
   5	2
   6	3
   7	0
   8	1
   9	0

3. For this problem, define the period of a string x₁...x_n is the smallest k > 0 such that x₁...x_n-k+1 = x_k...x_n. That is, removing the first k characters yields the same string as removing the last k characters. For example, the period of string abcabcab is 3, since you get abcab both by removing the first 3 characters and by removing the last three characters. (A string with period k is a prefix of a longer string that consists of the same k-character string repeated over and over.) Every string has a period. For example, the period of abc is 3, since you get the same string (the empty string) by removing the first 3 characters and by removing the last 3 characters.

   Describe an algorithm to compute the period of a length n string. Your algorithm must run in time O(n).

Suppose that x is a string of length n. To find the period of x, compute the KMP prefix function of x. The period of x is n - pi(n). This is because a periodic string with period k matches itself when shifted forward k characters. So the length n-k prefix of the string must be identical to the length n-k suffix.

4. Describe the main ideas behind greedy algorithms.

   Greedy algorithms are based on the idea of optimizing locally. When a greedy algorithm needs to make a choice, it chooses what will be best in the short term, without thinking about future consequences, and commits to its decision.

5. What problem does Prim's algorithm solve?

   Prim's algorithm computes minimal spanning trees of graphs.

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

   Dynamic programming algorithms generally employ principles including

   1. Optimal substructure: optimal solutions to problems are built from optimal solutions to subproblems.
   2. Memoization: answers to subproblems are remembered to avoid repeated computation of the same thing.

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

   This is not an efficient algorithm because it recomputes expressions. For example, computing h(4) requires computing h(3) and h(2). But computing h(3) requires computing h(2) again. The algorithm can be improved by storing the values h(i) in an array. For i = 1,...,n, compute h[i] according to the equation, looking in the array to find h(i-1) and h(floor(i/2)). Finally, get the value h[n] from the array.

8. Write the equations that are part of a dynamic programming algorithm for the longest common subsequence problem.

   Let X and Y be two strings. Notation X⁽ⁱ⁾ is the length i prefix of X, and X_i is the i-th character in X, numbering from 1.

   Let L(i,j) be the length of the longest common subsequence of X⁽ⁱ⁾ and Y^(j),

   1. L(i,0) = 0 and L(0,j) = 0.
   2. L(i,j) = 1 + L(i-1,j-1) when X_i = Y_j.
   3. L(i,j) = max(L(i-1,j), L(i,j-1)) when X_i =/= Y_j.

9. In class we described a greedy algorithm for the coin changing problem. Describe a dynamic programming algorithm for the same problem.

   Hint: Let coins(x) be the fewest coins needed to make x cents of change. For the rest, you are on your own.