Please note: It is extremely difficult to understand algorithms that are not explained clearly. I may give no credit for something that I can't follow, even if it's basically right.

1. Viterbi in Action

   On pages 14 to 16 of the class notes, on Dynamic Programming, there is a description of Viterbi's algorithm. Your task is to run the algorithm by hand, filling in the appropriate table, for the exampe of page 15. If you are doing this in a group, I recommend that you all figure out exactly how the algorithm works, then each of you construct the table separately, then compare and correct the results.

   Also, it's conceivable that I made mistakes in creating the slides (though I didn't do so on purpose.) If there are mistakes, another part of the problem is to correct them.

2. Longest Common Substring for 3 strings

   Develop a dynamic programming algorithm to find the longest common substring for three strings. Remember, I will want a clear statement of what information is contained in each location of the table, and a clear statement of how to fill the table in.

3. Persnickety Snail Pairings

   (a) N snails numbered 1 to N are lined up in order against a wall. The snails all crawl around, looking for friends. As they crawl, they leave a trail of slime. No snail is willing to cross a slime trail. (They also are too lazy to crawl up or go around the wall.) Whenever a pair gets together, they stop. At the end, we have a set P of disjoint pairs of snails. Some snails may end up not being in any pair. In the example below, P={(1,7), (2,4), (5,6), (8,9)}.
   

   Suppose V is an NxN array that is symmetric (meaning V(i,j) = V(j,i) for all i and j) which gives the "value" of pairing snail i with snail j. The "total value" of P is the sum of V(i,j) for each pair (i,j) in P.

   Your goal is to design an efficient algorithm that, given V, detemines the maximum possible total value of any snail pairing P. You should express the complexity of your algorithm as a function of N using big-Theta notation.

   (b) A special case of the Persnickety Snail Pairing problem is the Persnickety Snail Mating problem. Assume we are given a snail gender function G such that G(i) is the gender of snail i. We'll assume snails have only two genders. The value V(i,j) of pairing snail i with snail j is 0 if G(i)=G(j) and 1 otherwise. Find as efficient an algorithm as you can for determining the maximum possible total value of a pairing that can be achieved by persnickety snails.