Program 3
Modify the code for Floyd-Warshall so that it prints both a matrix of all shortest path lengths, and all shortest paths, for all ordered pairs of vertices. For example, for the graph shown below, in addition to the final matrix, you would print these paths:
AB, ABC, ABCD, ABCDE
BCDA, BC, BCD, BCDE
CDEA, CDEAB, CD, CDE
DEA, DEAB, DEABC, DE
EA, EAB, EABC, EABCD
Note that each row should contain all those paths that begin with a particular vertex.

Homework 4
  1. Find by hand the edit distance between the strings POLITE and OLIVE. Do this by filling in the table as we did in class, showing the memos on that table, and then showing the optimal edit using hyphens to show insertions and deletions. These notes should be helpful.
  2. Find the optimal alignment between strings ACGCT and CGTC where insertions and deletions (that is, gaps) cost -2, mismatches cost -1, and matches cost +3. Do this by filling in the table as we did in class, showing the memos on that table, and then showing the optimal alignment using hyphens to show insertions and deletions.
  3. Run the Floyd-Warshall algorithm to find the shortest distance between all pairs of vertices in the digraph shown to the right. The first distance matrix is shown below. Your solution should show the next five distance matrices. For example, the first matrix you should generate will show the lengths of the shortest paths between all pairs of vertices, where the path is allowed to go through only 'A' as an intermediate vertex. Your next matrix will show the lengths of the shortest paths between all pairs of vertices, where the path is allowed to go through only 'A' and 'B' as intermediate vertices. And so on. . . ..  Note that this is a directed graph, so the matrices generated will not be symmetric, as they were in class for undirected graphs. Otherwise, the computations are the same.

    		 A
    		 B
    		 C
    		 D
    		 E
    A
    		 0
    		 3
    		17
    B
    		0
    		 4
    		 10
    C

    		0
    		 3
    D


    		0
    		 7
    E
    		 7


    		0

  4. In the game of Gem, you are placed at some position (m, n) on a checkerboard, and need to hop back to location (0, 0). Your hops may be only horizontal or vertical hops, and only in a direction that brings you closer to (0, 0). Scattered throughout the checkerboard are blue and red gems. You may never hop onto a square containing a gem, but you may hop over these squares. You get points for hopping over gems, as follows:
    1. If a particular hop hops over red gems only, you add to your score the number of red gems you hop over.
    2. If a particular hop hops over blue gems only, you multiply your score by the number of blue gems you hop over.
    3. If a particular hop hops over both red and blue gems, then you add 5 to your score, regardless of the number of gems

    Note that if your hop does not pass over any gems, then that hop does not change your score. Describe a dynamic programming solution to the problem of finding an path back to (0, 0) that maximizes your score when you arrive, assuming that you begin your hopping with a score of zero. Then use your algorithm to find the optimal score on the board shown below. (You start at "S" and end at "E".)