CSE310 HW05 Thursday 04 01 2010 Due Thursday 04 08 2010 Please note that you have to typeset your assignment using either LATEX or Microsoft Word Hand written assignment will not be graded You need to submit a hardcopy before the lecture on the due date You also need to submit an electronic version at the digital drop box For the electronic version you should name your file using the format 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 root node 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 array structure of the sets you have to show the rank of each root node after these operations are performed 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 1 Let s not worry about how we obtained this structure From now on Find Set must be performed with path compression and Link must be performed by rank If we perform the operation Find Set 5 what would the structure look like express it 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 Instead 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 A4 where Ai has Pi 1 rows and Pi columns and P0 50 P1 20 P2 40 P3 30 P4 10 Use dynamic programming to compute the best way to compute the product A1 A2 A3 A4 You need to compute all entries of the table 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 2 1 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 parenthesization 4 10 pts You are given two sequences X ABACD and Y BCA Use dynamic programming to compute the LCS of X and Y You need to show all entries of the table with X on the left and Y on top Solution The LCS is BA 3 Grading Keys 2 pts will be cut off for each incorrect row 2 pts will be cut off for not writing the LCS 4
View Full Document
Unlocking...