ALGORITHMS AND DATA STRUCTURES II ASSIGNMENT 4 - WRITTEN

1. Write a pseudocode description of the printLCS() algorithm, which prints the longest common
subsequence of two strings � and �. Your algorithm takes as input the completed llcs[][] integer
array of longest common subsequence lengths, and the two strings � and �. (So, you do not have the
path[][] array - see Lecture 17, slides 98 and 99.) Your algorithm should start at llcs[n][m]
and work its way down to llcs[i][j] where either i = 0 or j = 0 and it should run in �(� +
�) time where � is the length of � and � is the length of �.
2. Let � be a flow network, and let � be a flow for �. Prove that for any cut, , of �, the value of � is
equal to the flow across cut , that is, |�| = �().
3. Consider the following graph �. The edges have costs and are undirected. There are 7 vertices and 10
edges. The edge list � is as follows:
(�, �) (�, �) (�, �) (�, �) (�, �) (�, �) (�, �) (�, �) (�, �) (�, �)
The Bellman-Ford algorithm makes |�| − 1 = 7 − 1 = 6 passes through the edge list �. Each pass
relaxes the edges in the order they appear in the edge list. As with Dijkstra’s algorithm, we record the
current best known cost �[�] to reach each vertex � from the start vertex �. Initially �[�] = 0 and
�[�] = +∞ for all the other vertices � ≠ �. Run Bellman-Ford on the given graph, starting at vertex
�, and using the order of set � above, show me the contents of array �[] after each iteration (6 arrays
in all.)