” COMP2721程序 写作、 辅导Algorithms程序Coursework 3COMP2721 Algorithms and Data Structures II1. We are given six matrices A1, A2, A3, A4, A5 and A6 for which we wish to compute theproduct A = A1 A2 A3 A4 A5 A6 where Aiis a di1 di matrix. Since matrixmultiplication is associative we can parenthesise the expression for A any way we wish andwe will end up with the Same result. What is the minimum number of scalar multiplicationswe have to perform if d0 = 3, d1 = 4, d2 = 5, d3 = 6, d4 = 5, d5 = 3 and d6 = 2? How dowe 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 calculatesdistance 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 ofthe algorithm. Each row of the table corresponds to one distance update. The first columnshows the index i such that the new distance is a distance di(u, v). The secondand third column show the vertex u and v, respectively. Finally, the fourth and fifthcolumn should contain the Old distance (di1(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 foreach 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 productionsS AB | BC A BA | aB CC | b C AB | agenerates non-empty strings in T. Execute the Cocke-Younger-Kasami algorithm forthis grammar on the input s = ababbab. Give a table of all sets V (i, k) computed and aparse tree for s. The table is encoded as in question 1, where {} is the empty set. The orderof variables is S A B C. The parse trees are endoded as strings, obtained from s byinserting 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.如有需要，请加QQ：99515681 或WX：codehelp
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
