Coursework 3
COMP2721 Algorithms and Data Structures II
1. We are given six matrices A1, A2, A3, A4, A5 and A6 for which we wish to compute the
product A = A1 · A2 · A3 · A4 · A5 · A6 where Ai
is a di−1 × di matrix. Since matrix
multiplication is associative we can parenthesise the expression for A any way we wish and
we will end up with the same result. What is the minimum number of scalar multiplications
we have to perform if d0 = 3, d1 = 4, d2 = 5, d3 = 6, d4 = 5, d5 = 3 and d6 = 2? How do
we parenthesise the expression for A to achieve this number?
Present your partial results in a table. Give the diagonals as lists of 5, 4, 3, 2, 1 number(s)
separated by a blank space.
Give the product with parantheses such as ((A1A2)(A3A4))(A5A6).
[0:30 h expected time] [6 marks]
2. Consider the following directed graph with edge-weights.
Execute the Floyd-Warshall algorithm on the above graph. Recall that the algorithm calculates
distance di(u, v) between any pair of vertices u and v, where for every i ∈ {1, . . . , 6},
di(u, v) is the length of a shortest (u, v)-path in the graph G[{u, v, 1, . . . , i}]. For instance,
the following matrix shows the distance di(u, v) for i = 0.
Fill the following table with all updates (of distances) that occur during the execution of
the algorithm. Each row of the table corresponds to one distance update. The first column
shows the index i such that the new distance is a distance di(u, v). The second
and third column show the vertex u and v, respectively. Finally, the fourth and fifth
column should contain the old distance (di−1(u, v)) and the new distance (di(u, v)), respectively.
Fill the table in the order in which the updates occur, i.e., increase i and for
each each assume that the algorithm updates the distances in the (lexicographical) order
(1, 2),(1, 3),(1, 4),(1, 5),(1, 6),(2, 1),(2, 2), . . . ,(6, 6).
[0:30 h expected time] [6 marks]
3. The context-free grammar (V, T, P, S) with variables V = {S, A, B, C}, terminals T = {a, b}
and the productions
S → AB | BC A → BA | a
B → CC | b C → AB | a
generates non-empty strings in T
∗
. Execute the Cocke-Younger-Kasami algorithm for
this grammar on the input s = ababbab. Give a table of all sets V (i, k) computed and a
parse tree for s. The table is encoded as in question 1, where {} is the empty set. The order
of variables is S < A < B < C. The parse trees are endoded as strings, obtained from s by
inserting brackets, sorted in alphabetic order where a < b < (<). For example,
[0:30 h expected time] [8 marks]
Submission: Submit in Gradescope.
Deadline: Monday, 22 March 2021, 10am.
Credits: This piece of summative coursework is worth 10% of your grade.