COMP 3270 Introduction to Algorithms
Homework 3
1. Use Strassen’s algorithm to compute the matrix product. Show detailed procedure of your work.
1 3
7 5
6 8
4 2 :
2. Using pages 4-16 of the slides (which can be found under the file section on Canvas) of Chapter 4 as a model,
illustrate the operation of PARTITIONon the array A = [13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11].
3. Consider the following algorithm
Algorithm Mystery(A: Array [i..j] of integer)
i & j are array starting and ending indexes
begin
if i=j then
return A[i]
else
k=i+floor((j-i)/2)
temp1= Mystery(A[i..k])
temp2= Mystery(A[(k+1)..j]
if temp1<temp2 then
return temp1 else return temp2
end
What does the recursive algorithm above compute?
