Mansoura University
Faculty of Computers and Information
Sciences
Department of Computer Science
First Semester- 2020-2021
Analysis and Design of Algorithms
Grade: THREE
Prof. Samir Elmougy
Chapter 4
Divide and Conquer (Part III)
Based on: Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, “Introduction to Algorithms”, 3rd Edition, The MIT
Press, 2009.
Last Lecture
◼ Review for Recurrence Relations
◼ Divide and Conquer Design Approach
◼ Binary Search
◼ Merge Sort
◼ Recurrence Relation for Merge Sort
◼ Analysis Merge Sort Recurrence
◼ Solving Recurrence Relations
◼ Recurrence Tree
◼ Master Theorem
◼ Iteration Method
Page 2
Contents
◼ Matrix Multiplication: Simple Divide and Conquer
◼ Analysis of Matrix Multiplication
◼ Strassen’s Algorithm for Matrix Multiplication
◼ Analysis of Strassen’s Algorithm
◼ Solving Recurrence Relations
◼ Changing Variables
Page 3
4.2 Strassen’s algorithm for matrix multiplication
P.75
Matrix Multiplication
◼ Compute the matrix product C = A x B, for two n x n
matrices
4
Matrix Multiplication: A Simple Divide-and-Conquer
Algorithm P.69
◼ Suppose that we partition each of A, B, and C into four n/2 x n/2
matrices:
◼ So, C =
5
Matrix Multiplication: A Simple Divide-and-Conquer
Algorithm P.69
How to use the above equations to create a straightforward,
recursive, divide-and-conquer algorithm?
6
Matrix Multiplication: A Simple Divide-and-Conquer
Algorithm P.77
T(n) =8 T (n/2) + (n2)
7
Matrix Multiplication: A Simple Divide-and-Conquer
Algorithm P.78
◼ T[n] = (1) + 8T[n/2] + (n2)
◼ T[n] = 8T[n/2] + (n2) if n 1 else T[n] = (1)
◼ T[n] = ( n3 )
8
Matrix Multiplication: A Simple Divide-and-
Conquer Algorithm
, where T(1)=1
Matrix Multiplication: A Simple Divide-and-
Conquer Algorithm
Now
Also,
Hence,
Matrix Multiplication: Strassen’s Algorithm P.79
Z = A1 x A2
T(n) = 7 T (n/2) + (n2) = (n 2.81 )
11
Solving Recurrence Relations:
Changing Variables
How to transform the given recurrence to one you had seen before
T(n) = 2T( n ) + lg (n)
First Step: Assume a new var. k = lg n n = 2k
Then, T (2k) = 2T(2k/2) + k
Second Step: Rename: S(k) = T(2k)
S(k) = 2S(k /2) + k S(k) = O(k . Lg k)
T(n) = T(2k) = S(k) = O (k lg k)=O(lg n . lg lg n)
12
