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  = 2, d1  = 5, d2  = 4, d3  = 10, d4  = 2, d5  = 5 and d6  = 3?  How do we parenthesise the expression for A to achieve this number? Present your partial results in a table.                           [0:30h expected time]  [7 marks]

2. Execute the FLovD-wARsHALL algorithm on the directed graph below. For every pair of vertices u and v give the distances δ(u, v) and δ(v, u). Give the shortest paths from

1 to 6 and from 6 to 1 as sequence of vertices.              [0:30h expected time]  [8 marks]

1   4   2   3   3 

−2          −1          −2 

4   3   5   4   6 

3.  The context-free grammar (V, T, P, S) with variables V = {S, A, B, C, D, E}, terminals T = {a, b} and the productions

S → AA | BB | a | b E → AB | BA | EE

A → AE | BC | a

B → BE | AD | b

C → AA | CE

D → BB | DE