DESIGN AND ANALYSIS OF
ALGORITHMS
UNIT - II
(21CSC204J)
Presented by:
Dr. Juhi Singh
Assistant Professor
CSE
SRMIST ,Ghaziabad
OUTLINES
Maximum Subarray Problem/ Largest
Binary Search
Subarray Sum
Complexity of Binary Search Time Complexity analysis of Largest
Merge Sort Subarray Sum
Time Complexity Analysis of Merge Sort Master Theorem Proof
Quick Sort and its time complexity Masters Theorem examples
analysis Finding Maximum and Minimum in an
Best Case, Worst Case, Average Case array
Analysis Max Min Array - Time Complexity
Strassen’s Matrix Multiplication Analysis - Examples
Strassen’s Matrix Multiplication and its Algorithm for finding closest pair
recurrence relation problem
Convex Hull Problem
OUTCOME OF SECOND UNIT
Analyze various algorithm design techniques to solve polynomial time
Solve Problem using divide and conquer approach
Analyze time complexity for algorithms using divide and conquer approach
Binary Search
Linear Search and Binary Search are the two popular searching techniques.
Binary search is the search technique that works efficiently on sorted lists.
Binary search follows the divide and conquer approach
If the match is found then, the location of the middle element is returned.
Complexity of Binary Search
Space O(1)
Complexity
Merge Sort
Merge Sort Algorithm
Time Complexity Analysis of Merge Sort
Quick Sort and its Time Complexity Analysis
The divide-and-conquer strategy is used in quicksort
Choose a pivot value
Partition
Sort both parts
Apply quicksort algorithm recursively
Quick Sort Algorithm
Best Case
Worst Case
Average Case
Basic Matrix Multiplication
Suppose we want to multiply two matrices of size N
x N: for example A x B = C.
N
Ci , j ai ,k bk , j
k 1
N N N
Thus T ( N ) c cN 3 O ( N 3 )
C11 = a11b11 + a12b21 i 1 j 1 k 1
C12 = a11b12 + a12b22
2x2 matrix multiplication can be
C21 = a21b11 + a22b21 accomplished in 8 multiplication.(2log28 =23)
C22 = a21b12 + a22b22
Strassen’s Matrix Multiplication
A B = R
A0 A1 B0 B1 A0B0+A1B2 A0B1+A1B3
=
A2 A3 B2 B3 A2B0+A3B2 A2B1+A3B3
Strassen showed that 2x2 matrix multiplication can be
accomplished in 7 multiplication and 18 additions or subtractions.
.(2log27 =22.807)
This reduce can be done by Divide and Conquer Approach.
•Divide matrices into sub-matrices: A , A , A etc
Matrix Multiplication and its recurrence
relation
Divide-and conquer is a general algorithm design paradigm:
Divide: divide the input data S in two or more disjoint subsets S1, S2, …
Recur: solve the subproblems recursively
Conquer: combine the solutions for S1, S2, …, into a solution for S
The base case for the recursion are subproblems of constant size
Analysis can be done using recurrence equations
Strassen’s Matrix Multiplication Algorithm
Strassen’s Matrix Multiplication and its recurrence relation
P1 = (A11+ A22)(B11+B22) C11 = P1 + P4 - P5 + P7
P2 = (A21 + A22) * B11 C12 = P3 + P5
P3 = A11 * (B12 - B22) C21 = P2 + P4
P4 = A22 * (B21 - B11) C22 = P1 + P3 - P2 + P6
P5 = (A11 + A12) * B22
P6 = (A21 - A11) * (B11 + B12)
P7 = (A12 - A22) * (B21 + B22)
Strassen’s Matrix Multiplication and its recurrence relation
void matmul(int *A, int *B, int *R, int n) {
if (n == 1) {
(*R) += (*A) * (*B);
} else {
matmul(A, B, R, n/4);
matmul(A, B+(n/4), R+(n/4), n/4);
matmul(A+2*(n/4), B, R+2*(n/4), n/4);
matmul(A+2*(n/4), B+(n/4), R+3*(n/4), n/4);
matmul(A+(n/4), B+2*(n/4), R, n/4);
matmul(A+(n/4), B+3*(n/4), R+(n/4), n/4);
matmul(A+3*(n/4), B+2*(n/4), R+2*(n/4), n/4);
matmul(A+3*(n/4), B+3*(n/4), R+3*(n/4), n/4);
}
Strassen’s Matrix Multiplication and its recurrence relation
Maximum Subarray problem/ Largest Subarray Sum
•The maximum subarray problem is the task of finding the contiguous subarray within a one-
dimensional array of numbers that has the largest sum. (Kadane’s Algorithm)
Time Complexity of Largest Subarray Sum
Time Complexity of Largest Subarray Sum
Master Theorem Proof
Finding Maximum and Minimum in an
Array
Max Min Array - Time Complexity
Analysis - Examples
Algorithm for finding closest pair Problem
Algorithm for finding closest pair Problem
Convex Hull Problem
Thank You
