ECS 122A – Algorithm & Analysis Homework 04 Solution
Question 1 (30 points total)
Read Section 4.2 Strassen’s algorithm for matrix mltiplications in the textbook Introduction to Algorithms
1. (10 points) Use Strassen’s algorithm to compute the matrix product 3 2 1 9
Copyright By PowCoder代写 加微信 powcoder
A12 =[2] A21 =[4]
B12 =[9] B21 =[3]
S1 =B12−B22 =[1] S2 =A11+A12 =[5] S3 =A21+A22 =[9] S4 =B21−B11 =[2] S5 =A11+A22 =[8] S6 =B11+B22 =[9] S7 =A12−A22 =[−3] S8 =B21+B22 =[11] S9 =A11−A21 =[−1]
S10 = B11 +B12 = [10]
P1 = A11 · S1 = [3] P2 = S2 · B22 = [40] P3 = S3 · B11 = [9]
P4 = A22 · S4 = [10] P5 = S5 · S6 = [72]
P6 = S7 · S8 = [−33] P7 = S9 · S10 = [−10]
A11 =[3] B11 =[1]
A22 =[5] B22 =[8]
C11 = P5 +P4 −P2 +P6 = [72+10−40+(−33)] = [9] C12 = P1 + P2 = [43]
C21 = P3 + P4 = [19]
C22 = P5 +P1 −P3 −P7 = [72+3−9−(−10)] = [76]
3 2 1 9 9 43 4 5 · 3 8 = 19 76
2. (20 points) Write the pseudo-code for Strassen’s algorithm. Answer:
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
strassen(A, B): n = number if n == 1: return
Let C be a
Partition A, B, and C into
A11, B11, C11 ,
A12, B12, C12 ,
A21, A22, B21, B22,
S10 = B11 + B12
of rows in A A * B
n * n matrix
– B22 + A12 + A22 – B11 + A22 + B22 – A22 + B22 – A21
P1 = strassen(A11, S1) P2 = strassen(S2, B22) P3 = strassen(S3, B11) P4 = strassen(A22, S4) P5 = strassen(S5, S6) P6 = strassen(S7, S8) P7 = strassen(S9, S10)
+ P4 – P2 + P6 + P2
+ P1 – P3 – P7
C22 as in equations (4.9)
(You do not have to specify how to partition the matrices using indexing.)
Question 2 (40 points total)
Given an array of strings, we want to find the longest common prefix of the strings.
1. (20 points) Provide a brute-force algorithm for the problem and analyze the time complexity of your algorithm. Write your algorithm in pseudo-code.
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15
2. (20 points) Provide a divide-and-conquer algorithm for the problem and analyze the time com- plexity of your algorithm. Write your algorithm in pseudo-code.
[Hint: The divide-and-conquer algorithm for this problem does not improve the time efficiency.]
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16
LCP(words[0…n-1]): prefix = words [0] for i = 1 to n-1:
prefix = common -prefix(prefix , return prefix
common-prefix(w1, w2): prefix = “”
m = w1.length
n = w2.length
while (w1[i] == w2[i]) and (i < m) and (i < n):
prefix += w1[i]
i += 1 return prefix
Time complexity: O(n × m), where n is the length of the input array of string, m is the longest string in the array.
• The for loop goes through n iterations.
• The runtime of common-prefix is O(k), where k is the length of the longer input string.
LCP(words[0...n-1]):
if words.length == 0:
if words.length == 1:
return words [0]
return common-prefix(LCP(words[0...n/2]), LCP(words[(n/2)+1 ... n-1]))
common-prefix(w1, w2): prefix = ""
m = w1.length
n = w2.length
while (w1[i] == w2[i]) and (i < m) and (i < n):
prefix += w1[i]
i += 1 return prefix
Time complexity: O(n × m), where n is the length of the input array of string, m is the longest string in the array.
Explanation: T(n) = 2T( n2 ) + O(m), where n is the length of the input array of string, m is the longest string in the array. We didn’t learn how to solve the recurrence. But every character in every string in the array will be checked so the runtime is still O(n × m).
Question 3 (10 points each, 30 points total)
The algorithm we described in class for the activity selection problem is not the only greedy algorithm. For each of the following alternative greedy choices, either prove or disprove that the resulting algorithm has the greedy choice property.
1. Pick the compatible activity with the earliest start time Answer:
The resulting algorithm does not have the greedy choice property.
Activity Start time Finish time a1 0 10
The greedy solution is {a1}. The optimal solution is {a2, a3}.
2. Pick the compatible activity with the shortest duration Answer:
The resulting algorithm does not have the greedy choice property.
Activity Start time Finish time a1 5 7
The greedy solution is {a1}. The optimal solution is {a2, a3}.
3. Pick the compatible activity that conflicts with the fewest other activities Answer:
The resulting algorithm does not have the greedy choice property.
Activity Start time Finish time a1 0 2
a4 6 8 a5 1 3 a6 3 5 a7 5 7
The optimal solution is {a1, a2, a3, a4}. Let the greedy solution be B = {}.
• Step 1: Randomly pick one from a1 and a4: B = {a1}.
a1 a2 a3 a4 a5 a6 a7
number of activities in conflict with 1 2 2 1 2 2 2 • Step 2:
a2 a3 a4 a5 a6 a7 number of activities in conflict with 2 2 1 1 2 2
a5 is not compatible with B. Pick a4: B = {a1, a4}. • Step 3:
a2 a3 a5 a6 a7 number of activities in conflict with 2 2 1 2 1
a5 and a7 are not compatible with B. Randomly pick one from a2, a3 and a6. Pick a6: B = {a1, a4, a6}.
None of the remaining activicities is compatible with B. So B = {a1,a4,a6}, smaller than the optimal solution.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com