Matrix multiplication
COMP 3270 Introduction to Algorithms Homework 2
1.(20 points) Calculate the result of multiplication between following 2 matrix with strassen’s algorithm.
(𝟓 𝟏𝟎) (𝟏 𝟐) 𝟐𝟏𝟑𝟒
Quicksort
2. (20 points) Using pages 4-16 of lecture notes of Chapter 4 as a model, illustrate the operation of PARTITION on the array A = [2, 5, 1, 18, 12, 8, 7, 21, 33, 8, 9, 11].
3. (20 points) Show that the running time of QUICKSORT when the array A contains distinct elements and is sorted in increasing order.
counting Sort
4. (20 points) If Counting Sort is applied to the array of numbers [2, 1, 6, 6, 9, 3, 1, 5, 7], show how these numbers will get rearranged, you also need to show each step of sorting process.
Divide and Conquer & Algorithm Design
5. (20 points) Consider the following algorithm
— Precondition: S is a sorted list
index mystery(index low, index high,
const Array S[], number x)
if low ≤ high then
mid = (low + high) / 2
if x = S[mid] then
else end
return mid
elsif x < s[mid] then
return mystery (low, mid-1, S, x)
else
return mystery (mid+1, high, S, x)
return 0
What does the recursive algorithm above compute? Explain why?