COMP2721程序代做、代写Algorithms程序、代写Java，c++编程

日期：2021-03-16 10:16

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.