Computer Science 3650
Spring 2004
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?

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

  3. For this problem, define the period of a string x1...xn is the smallest k > 0 such that x1...xn-k+1 = xk...xn. 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).

  4. Describe the main ideas behind greedy algorithms.

  5. What problem does Prim's algorithm solve?

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

  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.

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

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