Practice Questions for Exam 4
CSCI 3650

1. What principles characterize a greedy algorithm? Answer

2. What principles characterize a dynamic programming algorithm? Answer

3. Why would you choose a dynamic programming algorithm instead of a greedy algorithm for a particular problem? Answer

4. A substring is a contiguous part of a string. That is, it cannot contain any gaps. For example, ogr is a substring of photograph, but grp is not. Every string is a substring of itself.

   A suffix of a string is a substring that occurs at the end. For example, graph is a suffix of photograph. Every string is a suffix of itself.

   A longest common substring of two strings X and Y is a longest string that is a substring of both X and Y. For example, the longest common substring of photograph and tomography is ograph. (There can be more than one longest common substring of two strings. For example, both aa and bb are longest common substrings of aabb and ccaaccbb.)

   There is a similar notion of the longest common suffix of two strings, namely, the longest string that is a suffix of both.

   Suppose X = x₁…x_n. Define X ⁽ⁱ⁾ to be the length i prefix x₁…x_i of X. For example, if X is gravity then X ⁽⁴⁾ = grav.

   Define L(i, j) to be the length of a longest common substring of X ⁽ⁱ⁾ and Y ^(j). For example, if X is gravity and Y is photograph then:

   • L(4, 7) = 2 since the length 4 prefix of X is grav, the length 7 prefix of Y is photogr and the longest common substring of grav and protogr is gr.

   • L(7, 10) = 3 since the length 7 prefix of X is gravity, the length 10 prefix of Y is photograph and the longest common substring of gravity and photograph is gra.

   Define S(i, j) to be the length of the longest common suffix of X ⁽ⁱ⁾ and Y ^(j). For example, if X is gravity and Y is levity then:

   • S(4, 3) = 1 since the length 4 prefix of X is grav, the length 3 prefix of Y is lev and the longest common suffix of grav and lev is v.

   • S(7, 6) = 4 since the length 7 prefix of X is gravity, the length 6 prefix of Y is levity and the longest common suffix of gravity and levity is vity.

    

   This problem is to develop an efficient algorithm to find the length of the longest common substring of two given strings X = x₁… x_n and Y = y₁… y_m.

   1. Write equations that tell the values of L(0, j), L(i,0), S(0, j) and S(i, 0) for all i = 1, …, n and j = 1, …, m. There should be four equations.

      Answer

   2. Suppose i > 0 and j > 0 and x_i = y_j. Write recursive equations that define L(i, j) and S(i, j) in this case. There should be two equations here, one for L(i, j) and one for S(i, j), each for the case where x_i = y_j.

      Hint: A common substring of X ⁽ⁱ⁾ and Y ^(j) is either a suffix of both or it is not a suffix of X ⁽ⁱ⁾ or not a suffix of Y ^(j). When it is not a suffix of X ⁽ⁱ⁾, it does not include the last character of x_i of X ⁽ⁱ⁾. When it is not a suffix of Y ^(j), it does not include the last character of y_j of Y ^(j).

      Answer

   3. Suppose that x_i ≠ y_j. Write recursive equations that define L(i, j) and S(i, j) in this case. Be sure to define both of them.

      Answer

   4. Using your equations, write an efficient algorithm to compute the longest common substring of two strings X and Y. Strings X and Y are the inputs to the algorithm. Write the algorithm so that it is easy to understand.

      Answer