(a) Find a longest common subsequence (LCS) between the two sequences ZXYYZ and XYZYZ using dynamic...

Transcribed Image Text:

(a) Find a longest common subsequence (LCS) between the two sequences ZXYYZ and XYZYZ using dynamic programming. You only need to show the final contents of the dynamic programming table, the traceback path, and the LCS itself. [8 marks] (b) Apply the Floyd-Warshall algorithm to find the lengths of the shortest paths between any two vertices for the graph in Figure 3 below. You only need to show the contents of the distance matrix after every iteration of k (the predecessor matrix is not required). [12 marks] 2 b a 1 4 3 7 6 d (a) Find a longest common subsequence (LCS) between the two sequences ZXYYZ and XYZYZ using dynamic programming. You only need to show the final contents of the dynamic programming table, the traceback path, and the LCS itself. [8 marks] (b) Apply the Floyd-Warshall algorithm to find the lengths of the shortest paths between any two vertices for the graph in Figure 3 below. You only need to show the contents of the distance matrix after every iteration of k (the predecessor matrix is not required). [12 marks] 2 b a 1 4 3 7 6 d