CSE310 HW05, Thursday, 04/01/2010, Due: Thursday, 04/08/2010Please note that you have to typeset your assignment using either LATEX or MicrosoftWord. Hand-written assignment will not be graded. You need to submit a hardcopybefore the lecture on the due date. You also need to submit an electronic version atthe digital drop box. For the electronic version, you should name your file using theformat HW05-LastName-FirstName.1. (10 pts) Suppose you are initially given 8 singleton sets, each containing the numbers 1, 2, . . . , 8,respectively. Show the array structure of the sets (you have to show the rank of each rootnode).Solution:i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |-----------------------------------A | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |Grading Keys:5 pts for correct solution.Now we perform Union(1, 2), Union(3, 4) and Union(2, 4), in that order. Show the arraystructure of the sets (you have to show the rank of each root node) after these operations areperformed.Solution:i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |-----------------------------------A | 2 | 4 | 4 |-2 | 0 | 0 | 0 | 0 |Grading Keys:5 pts for correct solution.2. (20 pts) Let the disjoint sets have the following structure:i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |-----------------------------------A |-3 | 1 | 1 | 3 | 4 | 3 |-1 | 7 |1Let’s not worry about how we obtained this structure. From now on, Find-Set must beperformed with path compression and Link must be performed by rank.• If we perform the operation Find-Set(5), what would the structure look like (expressit using the array representation).Solution:i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |-----------------------------------A |-3 | 1 | 1 | 1 | 1 | 3 |-1 | 7 |Grading Keys:4 pts for correct rank of root node;4 pts for other correct entries.• Suppose we have never performed the Find-Set(5) operation listed in the above. In-stead, we apply the operation Union(6, 8). Show the resulting set structure.Solution:i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |-----------------------------------A |-3 | 1 | 1 | 3 | 4 | 1 | 1 | 7 |Grading Keys:6 pts for correct path compression;6 pts for other correct entries.3. (10 pts) You are given four matrices A1, A2, A3, A4where Aihas Pi−1rows and Picolumns,and P0= 50, P1= 20, P2= 40, P3= 30, P4= 10. Use dynamic programming to compute thebest way to compute the product A1× A2× A3× A4. You need to compute all entries of thetable for the values as well as the table for the splits.Solution: Since s[1,4]=1 and s[2,4]=2, we have the optimal solution as follows:A1× (A2× (A3× A4))Grading Keys:0.5 pt for correct entries of m[1, 2], m[2, 3] and m[3, 4] respectively;0.5 pt for correct entries of s[1, 2], s[2, 3] and s[3, 4] respectively;1 pts for correct entries of m[1, 3] and m[2, 4] respectively;21 pts for correct entries of s[1, 3] and s[2, 4] respectively;1.5 pts for correct entry of m[1, 4].1.5 pts for correct entry of s[1, 4].2 pts for correct parenthesization4. (10 pts) You are given two sequences X = ABACD and Y = BCA. Use dynamic program-ming to compute the LCS of X and Y . You need to show all entries of the table, with X onthe left and Y on top.Solution: The LCS is BA3Grading Keys:2 pts will be cut off for each incorrect row;2 pts will be cut off for not writing the
View Full Document
Unlocking...