BHARATIYA VIDYA BHAVAN’S

SARDAR PATEL INSTITUTE OF TECHNOLOGY

Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

Name SOHAM MANISH PARIKH

UID no. 2023300160

Experiment No. 3

AIM: Divide and Conquer: Maximum Sub-Array, Closest Pair and Strassen’s
Matrix Multiplication

Program 1

PROBLEM: To implement Maximum Sub Array and Closest Pair algorithms and pass
through batches of 1000, 2000, 3000, …, 10000 and analyse best case,
worst case and average case time complexities for two cases: Divide and
Conquer approach and Brute Force approach.

THEORY:
Kadane’s Algorithm (O(n))

Kadane’s algorithm optimizes the approach using dynamic programming:

1.​ Maintain a variable maxEndingHere, which stores the maximum

sum of a subarray ending at the current index.
2.​ Maintain another variable maxSoFar, which keeps track of the
highest sum encountered so far.
3.​ Update maxEndingHere as:

maxEndingHere=max⁡(current
element,maxEndingHere+current element)

4.​ Update maxSoFar with the maximum value of maxEndingHere.

Closest Pair Algorithm (O(n log n))

A more efficient approach is based on sorting and recursion:

1.​ Sort the points by x-coordinates.

2.​ Divide: Split the points into two equal halves.
3.​ Conquer:
○​ Recursively find the closest pair in each half.
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

○​ Find the minimum distance (d) from the two halves.

4.​ Combine:
○​ Check for a closer pair where one point is in the left half and
the other in the right half.
○​ Consider only points that lie within d distance of the
dividing line.
○​ Sort these points by y-coordinates and check distances in a
restricted window.

ALGORITHM: Pseudocode Max SubArray:

int maxSubarray(int arr[], int n) {
int maxSoFar = -∞; // Stores the maximum sum found
int maxEndingHere = 0; // Tracks the sum ending at
current index

for (int i = 0; i < n; i++) {

maxEndingHere = max(arr[i], maxEndingHere + arr[i]);
maxSoFar = max(maxSoFar, maxEndingHere);
}

return maxSoFar;
}

Pseudocode Closest Pair:

float closestPair(Point P[], int n) {
sort(P, P + n, compareX);
return closestUtil(P, n);
}

float closestUtil(Point P[], int n) {

if (n <= 3)
return bruteForceClosest(P, n);

int mid = n / 2;
Point midPoint = P[mid];

float dLeft = closestUtil(P, mid);

float dRight = closestUtil(P + mid, n - mid);
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

float d = min(dLeft, dRight);

Point strip[n];
int j = 0;
for (int i = 0; i < n; i++) {
if (abs(P[i].x - midPoint.x) < d)
strip[j++] = P[i];
}

return min(d, stripClosest(strip, j, d));

}

float stripClosest(Point strip[], int size, float d) {

sort(strip, strip + size, compareY);

float minDist = d;
for (int i = 0; i < size; i++) {
for (int j = i + 1; j < size && (strip[j].y -
strip[i].y) < minDist; j++) {
minDist = min(minDist, distance(strip[i],
strip[j]));
}
}

return minDist;
}

PROGRAM: DIVIDE AND CONQUER:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>

// Brute force method to find the Maximum Subarray Sum

void maxSubArrayBruteForce(int arr[], int n) {
int maxSum = INT_MIN;
for (int i = 0; i < n; i++) {
int currentSum = 0;
for (int j = i; j < n; j++) {
currentSum += arr[j];
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

if (currentSum > maxSum) {

maxSum = currentSum;
}
}
}
}

// Brute force method to find the closest pair

void closestPairBruteForce(int arr[], int n) {
int minDiff = INT_MAX;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int diff = abs(arr[i] - arr[j]);
if (diff < minDiff) {
minDiff = diff;
}
}
}
}

// Function to generate random numbers in an array

void generateRandomArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
arr[i] = rand() % 2001 - 1000; // Random numbers
from -1000 to 1000
}
}

int main() {
srand(time(0)); // Seed for random numbers

FILE *file = fopen("brute_force_times.csv", "w");

if (file == NULL) {
printf("Error opening file!\n");
return 1;
}

// Write CSV header

fprintf(file,
"Array_Size,MaxSubarray_Time,ClosestPair_Time\n");
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

// Loop for array sizes 100, 200, ..., 1000

for (int n = 100; n <= 1000; n += 100) {
int arr[n];
generateRandomArray(arr, n);

clock_t start, end;

double time_maxSubarray, time_closestPair;

// Measure time for max subarray brute force

start = clock();
maxSubArrayBruteForce(arr, n);
end = clock();
time_maxSubarray = ((double)(end - start)) /
CLOCKS_PER_SEC;

// Measure time for closest pair brute force

start = clock();
closestPairBruteForce(arr, n);
end = clock();
time_closestPair = ((double)(end - start)) /
CLOCKS_PER_SEC;

// Print and save results

printf("Array Size: %d | MaxSubarray Time: %.6f sec |
ClosestPair Time: %.6f sec\n",
n, time_maxSubarray, time_closestPair);

fprintf(file, "%d,%.6f,%.6f\n", n, time_maxSubarray,

time_closestPair);
}

fclose(file);
printf("\nExecution times saved to
brute_force_times.csv\n");

return 0;
}

BRUTE FORCE:
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>

// Function to find the Maximum Subarray Sum using Kadane's

Algorithm
void maxSubArray(int arr[], int n) {
int maxSum = INT_MIN, currentSum = 0;
for (int i = 0; i < n; i++) {
currentSum += arr[i];
if (currentSum > maxSum) {
maxSum = currentSum;
}
if (currentSum < 0) {
currentSum = 0;
}
}
}

// Comparison function for sorting

int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}

// Function to find the closest pair in an array

void closestPair(int arr[], int n) {
if (n < 2) return;
qsort(arr, n, sizeof(int), compare);
int minDiff = INT_MAX;
for (int i = 1; i < n; i++) {
int diff = arr[i] - arr[i - 1];
if (diff < minDiff) {
minDiff = diff;
}
}
}

// Function to generate a random array

void generateRandomArray(int arr[], int n) {
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

for (int i = 0; i < n; i++) {

arr[i] = rand() % 2001 - 1000; // Random numbers
between -1000 and 1000
}
}

int main() {
srand(time(0)); // Seed for random number generation

FILE *file = fopen("optimized_times.csv", "w");

if (file == NULL) {
printf("Error opening file!\n");
return 1;
}

// Write CSV header

fprintf(file,
"Array_Size,MaxSubarray_Time,ClosestPair_Time\n");

// Loop for array sizes 100, 200, ..., 1000

for (int n = 100; n <= 1000; n += 100) {
int arr[n];
generateRandomArray(arr, n);

clock_t start, end;

double time_maxSubarray, time_closestPair;

// Measure time for Kadane's algorithm (Max Subarray)

start = clock();
maxSubArray(arr, n);
end = clock();
time_maxSubarray = ((double)(end - start)) /
CLOCKS_PER_SEC;

// Measure time for Closest Pair algorithm

start = clock();
closestPair(arr, n);
end = clock();
time_closestPair = ((double)(end - start)) /
CLOCKS_PER_SEC;
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

// Print and save results

printf("Array Size: %d | MaxSubarray Time: %.6f sec |
ClosestPair Time: %.6f sec\n",
n, time_maxSubarray, time_closestPair);
fprintf(file, "%d,%.6f,%.6f\n", n, time_maxSubarray,
time_closestPair);
}

fclose(file);
printf("\nExecution times saved to
optimized_times.csv\n");

return 0;
}

OUTPUT: DIVIDE AND CONQUER:

 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

BRUTE FORCE:
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

OBSERVATION
ANALYSIS:
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

CONCLUSION:
Maximum Subarray Problem

The Maximum Subarray Problem can be solved using:

1.​ Brute Force Approach

○​ Iterates over all possible subarrays.
○​ Time complexity: O(n^2) to O(n^3).
○​ Not efficient for large arrays.
2.​ Divide and Conquer Approach
○​ Divides the array into two halves.
○​ Solves recursively for left and right halves and finds the max
subarray crossing the middle.
○​ Time complexity: O(n log n), which is better than brute
force.
○​ However, Kadane’s Algorithm O(n) is the most optimal
solution.

Final Verdict:

●​ Kadane’s Algorithm O(n) is the best method.

●​ Divide and Conquer is useful if modifications are needed for related
problems.
●​ Brute force is inefficient.

Closest Pair Problem

The Closest Pair of Points Problem can be solved using:

1.​ Brute Force Approach

○​ Computes distances for all pairs.
○​ Time complexity: O(n^2).
○​ Simple but impractical for large datasets.
2.​ Divide and Conquer Approach
○​ Divides the points into two halves.
○​ Finds the minimum distance in each half.
○​ Merges results efficiently by checking only relevant points.
○​ Time complexity: O(n log n).

Final Verdict:
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

●​ Divide and Conquer O(n log n) is the best method for large
datasets.
●​ Brute force is only useful for very small inputs.

Program 1

PROBLEM: To implement Matrix Multiplication algorithm and pass through batches of

1000, 2000, 3000, …, 10000 and analyse best case, worst case and average
case time complexities for three cases: Divide and Conquer approach, Brute
Force approach and Strassen Matrix Multiplication Approach.

THEORY:
Matrix Multiplication Analysis

Matrix multiplication is a fundamental operation in computational

mathematics, with different approaches affecting performance based on
input size. We analyze three methods: Brute Force, Divide & Conquer,
and Strassen's Algorithm by evaluating their best, worst, and average-case
time complexities across increasing batch sizes (1000, 2000, ..., 10000).

1. Brute Force Approach (Classical Method)

●​ Concept: Uses three nested loops to compute the product of two

n×nn \times n matrices.
●​ Time Complexity: O(n^3), as every element requires a dot product
of a row and column.
●​ Best Case:O(n^3) (always the same, as every element must be
computed).
●​ Worst Case: O(n^3).
●​ Average Case: O(n^3).

2. Divide and Conquer Approach

●​ Concept: Recursively splits matrices into smaller sub-matrices,

solving smaller multiplication problems and combining results.
●​ Time Complexity: O(n^3) (without optimization).
●​ Best Case: O(n^3) (similar to brute force if no optimization is
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

applied).
●​ Worst Case: O(n^3).
●​ Average Case: O(n^3).

3. Strassen's Matrix Multiplication

●​ Concept: Uses recursion and reduces the number of multiplications

from 8 to 7 for 2×22 matrices, improving performance.
●​ Time Complexity: O(nlog⁡27)≈O(n2.81)
●​ Best Case: O(n^{2.81})
●​ Worst Case: O(n^{2.81}).
●​ Average Case: O(n^{2.81}).

Performance Analysis

●​ Brute Force: Slowest for large matrices.

●​ Divide and Conquer: Only useful when optimizations are added.
●​ Strassen's Algorithm: Faster but has overhead due to recursion.

By running matrix multiplication on batches of increasing size (1000, 2000,

..., 10000), we can analyze and compare execution times to determine the
most efficient method for large-scale computations.

THEORY:
Strassen’s Matrix Multiplication is an algorithm that reduces the number of
multiplications required to multiply two square matrices. It was developed
by Volker Strassen in 1969 and improves the standard O(n^3) complexity of
matrix multiplication to approximately O(n^{2.81}).

Key Idea:

Instead of using the conventional method, which requires 8 multiplications

for two 2×22 matrices, Strassen's algorithm reduces the number of
multiplications to 7 by using clever combinations of sums and differences
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

of matrix sub-blocks.

Steps:

1.​ Divide the n×n times n matrices into four n/2×n/2 submatrices.
2.​ Compute 7 special products (instead of 8) using these submatrices.
3.​ Use these products to construct the resulting matrix.

Strassen’s 7 Multiplications:

M1=(A11+A22)(B11+B22)

M2=(A21+A22)B11

M3=A11(B12−B22)

M4=A22(B21−B11)

M5=(A11+A12)B22

M6=(A21−A11)(B11+B12)

M7=(A12−A22)(B21+B22)

Final Matrix Computation:

C11=M1+M4−M5+M7

C12=M3+M5

C22=M1−M2+M3+M6

Since Strassen’s method is recursive, it works best for large matrices. For
very large matrices, further optimizations can be applied to achieve near
O(n^2) performance.

ALGORITHM:
StrassenMultiply(A, B, N):

If N == 1:
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

Return A[0][0] * B[0][0] // Base case: Single

element multiplication

// Step 1: Divide A and B into 4 submatrices

Divide A into A11, A12, A21, A22

Divide B into B11, B12, B21, B22

// Step 2: Compute 7 matrix multiplications (Strassen’s

formula)

M1 = StrassenMultiply(A11 + A22, B11 + B22) // (A11 +

A22) * (B11 + B22)

M2 = StrassenMultiply(A21 + A22, B11) // (A21 +

A22) * B11

M3 = StrassenMultiply(A11, B12 - B22) // A11 *

(B12 - B22)

M4 = StrassenMultiply(A22, B21 - B11) // A22 *

(B21 - B11)

M5 = StrassenMultiply(A11 + A12, B22) // (A11 +

A12) * B22

M6 = StrassenMultiply(A21 - A11, B11 + B12) // (A21 -

A11) * (B11 + B12)

M7 = StrassenMultiply(A12 - A22, B21 + B22) // (A12 -

A22) * (B21 + B22)

// Step 3: Compute result submatrices

C11 = M1 + M4 - M5 + M7
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

C12 = M3 + M5

C21 = M2 + M4

C22 = M1 - M2 + M3 + M6

// Step 4: Combine C11, C12, C21, C22 into result matrix

C

Return C

PROGRAM:
#include <stdio.h>

#include <stdlib.h>

#include <time.h>

void generate_matrix(int size, int **matrix, const char

*filename) {

FILE *file = fopen(filename, "w");

for (int i = 0; i < size; i++) {

for (int j = 0; j < size; j++) {

matrix[i][j] = rand() % 10;

fprintf(file, "%d ", matrix[i][j]);

fprintf(file, "\n");

fclose(file);
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

// Function to perform brute-force matrix multiplication

void brute_force_multiplication(int size, int **A, int **B,

int **C) {

for (int i = 0; i < size; i++) {

for (int j = 0; j < size; j++) {

C[i][j] = 0;

for (int k = 0; k < size; k++) {

C[i][j] += A[i][k] * B[k][j];

// Function to add two matrices

void add_matrix(int size, int **A, int **B, int **C) {

for (int i = 0; i < size; i++) {

for (int j = 0; j < size; j++) {

C[i][j] = A[i][j] + B[i][j];

}
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

// Function to subtract two matrices

void subtract_matrix(int size, int **A, int **B, int **C) {

for (int i = 0; i < size; i++) {

for (int j = 0; j < size; j++) {

C[i][j] = A[i][j] - B[i][j];

// Function to perform Strassen's matrix multiplication

void strassen_multiplication(int size, int **A, int **B, int

**C) {

if (size == 1) {

C[0][0] = A[0][0] * B[0][0];

return;

int new_size = size / 2;

int **A11 = malloc(new_size * sizeof(int *));

int **A12 = malloc(new_size * sizeof(int *));

int **A21 = malloc(new_size * sizeof(int *));

 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

int **A22 = malloc(new_size * sizeof(int *));

int **B11 = malloc(new_size * sizeof(int *));

int **B12 = malloc(new_size * sizeof(int *));

int **B21 = malloc(new_size * sizeof(int *));

int **B22 = malloc(new_size * sizeof(int *));

int **C11 = malloc(new_size * sizeof(int *));

int **C12 = malloc(new_size * sizeof(int *));

int **C21 = malloc(new_size * sizeof(int *));

int **C22 = malloc(new_size * sizeof(int *));

int **P1 = malloc(new_size * sizeof(int *));

int **P2 = malloc(new_size * sizeof(int *));

int **P3 = malloc(new_size * sizeof(int *));

int **P4 = malloc(new_size * sizeof(int *));

int **P5 = malloc(new_size * sizeof(int *));

int **P6 = malloc(new_size * sizeof(int *));

int **P7 = malloc(new_size * sizeof(int *));

int **temp1 = malloc(new_size * sizeof(int *));

int **temp2 = malloc(new_size * sizeof(int *));

 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

for (int i = 0; i < new_size; i++) {

A11[i] = malloc(new_size * sizeof(int));

A12[i] = malloc(new_size * sizeof(int));

A21[i] = malloc(new_size * sizeof(int));

A22[i] = malloc(new_size * sizeof(int));

B11[i] = malloc(new_size * sizeof(int));

B12[i] = malloc(new_size * sizeof(int));

B21[i] = malloc(new_size * sizeof(int));

B22[i] = malloc(new_size * sizeof(int));

C11[i] = malloc(new_size * sizeof(int));

C12[i] = malloc(new_size * sizeof(int));

C21[i] = malloc(new_size * sizeof(int));

C22[i] = malloc(new_size * sizeof(int));

P1[i] = malloc(new_size * sizeof(int));

P2[i] = malloc(new_size * sizeof(int));

P3[i] = malloc(new_size * sizeof(int));

P4[i] = malloc(new_size * sizeof(int));

P5[i] = malloc(new_size * sizeof(int));

 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

P6[i] = malloc(new_size * sizeof(int));

P7[i] = malloc(new_size * sizeof(int));

temp1[i] = malloc(new_size * sizeof(int));

temp2[i] = malloc(new_size * sizeof(int));

for (int i = 0; i < new_size; i++) {

for (int j = 0; j < new_size; j++) {

A11[i][j] = A[i][j];

A12[i][j] = A[i][j + new_size];

A21[i][j] = A[i + new_size][j];

A22[i][j] = A[i + new_size][j + new_size];

B11[i][j] = B[i][j];

B12[i][j] = B[i][j + new_size];

B21[i][j] = B[i + new_size][j];

B22[i][j] = B[i + new_size][j + new_size];

add_matrix(new_size, A11, A22, temp1);

 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

add_matrix(new_size, B11, B22, temp2);

strassen_multiplication(new_size, temp1, temp2, P1);

add_matrix(new_size, A21, A22, temp1);

strassen_multiplication(new_size, temp1, B11, P2);

subtract_matrix(new_size, B12, B22, temp2);

strassen_multiplication(new_size, A11, temp2, P3);

subtract_matrix(new_size, B21, B11, temp2);

strassen_multiplication(new_size, A22, temp2, P4);

add_matrix(new_size, A11, A12, temp1);

strassen_multiplication(new_size, temp1, B22, P5);

subtract_matrix(new_size, A21, A11, temp1);

add_matrix(new_size, B11, B12, temp2);

strassen_multiplication(new_size, temp1, temp2, P6);

subtract_matrix(new_size, A12, A22, temp1);

add_matrix(new_size, B21, B22, temp2);

strassen_multiplication(new_size, temp1, temp2, P7);

 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

add_matrix(new_size, P1, P4, temp1);

subtract_matrix(new_size, temp1, P5, temp2);

add_matrix(new_size, temp2, P7, C11);

add_matrix(new_size, P3, P5, C12);

add_matrix(new_size, P2, P4, C21);

add_matrix(new_size, P1, P3, temp1);

subtract_matrix(new_size, temp1, P2, temp2);

add_matrix(new_size, temp2, P6, C22);

for (int i = 0; i < new_size; i++) {

for (int j = 0; j < new_size; j++) {

C[i][j] = C11[i][j];

C[i][j + new_size] = C12[i][j];

C[i + new_size][j] = C21[i][j];

C[i + new_size][j + new_size] = C22[i][j];

}
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

for (int i = 0; i < new_size; i++) {

free(A11[i]);

free(A12[i]);

free(A21[i]);

free(A22[i]);

free(B11[i]);

free(B12[i]);

free(B21[i]);

free(B22[i]);

free(C11[i]);

free(C12[i]);

free(C21[i]);

free(C22[i]);

free(P1[i]);

free(P2[i]);

free(P3[i]);

free(P4[i]);

free(P5[i]);

free(P6[i]);
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

free(P7[i]);

free(temp1[i]);

free(temp2[i]);

free(A11);

free(A12);

free(A21);

free(A22);

free(B11);

free(B12);

free(B21);

free(B22);

free(C11);

free(C12);

free(C21);

free(C22);

free(P1);
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

free(P2);

free(P3);

free(P4);

free(P5);

free(P6);

free(P7);

free(temp1);

free(temp2);

// Function to perform Divide and Conquer matrix

multiplication

void dnc_multiplication(int size, int **A, int **B, int **C)

{

if (size == 1) {

C[0][0] = A[0][0] * B[0][0];

return;

int new_size = size / 2;

int **A11 = malloc(new_size * sizeof(int *));

 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

int **A12 = malloc(new_size * sizeof(int *));

int **A21 = malloc(new_size * sizeof(int *));

int **A22 = malloc(new_size * sizeof(int *));

int **B11 = malloc(new_size * sizeof(int *));

int **B12 = malloc(new_size * sizeof(int *));

int **B21 = malloc(new_size * sizeof(int *));

int **B22 = malloc(new_size * sizeof(int *));

int **C11 = malloc(new_size * sizeof(int *));

int **C12 = malloc(new_size * sizeof(int *));

int **C21 = malloc(new_size * sizeof(int *));

int **C22 = malloc(new_size * sizeof(int *));

int **temp1 = malloc(new_size * sizeof(int *));

int **temp2 = malloc(new_size * sizeof(int *));

for (int i = 0; i < new_size; i++) {

A11[i] = malloc(new_size * sizeof(int));

A12[i] = malloc(new_size * sizeof(int));

A21[i] = malloc(new_size * sizeof(int));

A22[i] = malloc(new_size * sizeof(int));

 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

B11[i] = malloc(new_size * sizeof(int));

B12[i] = malloc(new_size * sizeof(int));

B21[i] = malloc(new_size * sizeof(int));

B22[i] = malloc(new_size * sizeof(int));

C11[i] = malloc(new_size * sizeof(int));

C12[i] = malloc(new_size * sizeof(int));

C21[i] = malloc(new_size * sizeof(int));

C22[i] = malloc(new_size * sizeof(int));

temp1[i] = malloc(new_size * sizeof(int));

temp2[i] = malloc(new_size * sizeof(int));

for (int i = 0; i < new_size; i++) {

for (int j = 0; j < new_size; j++) {

A11[i][j] = A[i][j];

A12[i][j] = A[i][j + new_size];

A21[i][j] = A[i + new_size][j];

A22[i][j] = A[i + new_size][j + new_size];

 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

B11[i][j] = B[i][j];

B12[i][j] = B[i][j + new_size];

B21[i][j] = B[i + new_size][j];

B22[i][j] = B[i + new_size][j + new_size];

dnc_multiplication(new_size, A11, B11, temp1);

dnc_multiplication(new_size, A12, B21, temp2);

add_matrix(new_size, temp1, temp2, C11);

dnc_multiplication(new_size, A11, B12, temp1);

dnc_multiplication(new_size, A12, B22, temp2);

add_matrix(new_size, temp1, temp2, C12);

dnc_multiplication(new_size, A21, B11, temp1);

dnc_multiplication(new_size, A22, B21, temp2);

add_matrix(new_size, temp1, temp2, C21);

dnc_multiplication(new_size, A21, B12, temp1);

dnc_multiplication(new_size, A22, B22, temp2);

add_matrix(new_size, temp1, temp2, C22);

 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

for (int i = 0; i < new_size; i++) {

for (int j = 0; j < new_size; j++) {

C[i][j] = C11[i][j];

C[i][j + new_size] = C12[i][j];

C[i + new_size][j] = C21[i][j];

C[i + new_size][j + new_size] = C22[i][j];

for (int i = 0; i < new_size; i++) {

free(A11[i]);

free(A12[i]);

free(A21[i]);

free(A22[i]);

free(B11[i]);

free(B12[i]);

free(B21[i]);

free(B22[i]);

free(C11[i]);
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

free(C12[i]);

free(C21[i]);

free(C22[i]);

free(temp1[i]);

free(temp2[i]);

free(A11);

free(A12);

free(A21);

free(A22);

free(B11);

free(B12);

free(B21);

free(B22);

free(C11);

free(C12);

free(C21);

free(C22);
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

free(temp1);

free(temp2);

// Function to save matrix to a file

void save_matrix(int size, int **matrix, const char

*filename) {

FILE *file = fopen(filename, "w");

for (int i = 0; i < size; i++) {

for (int j = 0; j < size; j++) {

fprintf(file, "%d ", matrix[i][j]);

fprintf(file, "\n");

fclose(file);

// Function to write execution times to a CSV file

void write_execution_times(const char *filename, int sizes[],

double brute_times[], double dnc_times[], double
strassen_times[], int count) {

FILE *file = fopen(filename, "w");

 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

fprintf(file, "Matrix Size, Strassen ,DNC, Brute\n");

for (int i = 0; i < count; i++) {

fprintf(file, "%d,%.6f,%.6f,%.6f\n", sizes[i],

strassen_times[i], dnc_times[i], brute_times[i]);

fclose(file);

int main() {

srand(time(NULL));

int sizes[] = {2, 4, 8, 16, 32, 64, 128};

int count = sizeof(sizes) / sizeof(sizes[0]);

double brute_times[count];

double dnc_times[count];

double strassen_times[count];

for (int i = 0; i < count; i++) {

int size = sizes[i];

int **A = malloc(size * sizeof(int *));

int **B = malloc(size * sizeof(int *));

 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

int **C = malloc(size * sizeof(int *));

for (int j = 0; j < size; j++) {

A[j] = malloc(size * sizeof(int));

B[j] = malloc(size * sizeof(int));

C[j] = malloc(size * sizeof(int));

// Generate unique filenames

char filename_a[50], filename_b[50],

filename_res[50];

sprintf(filename_a, "matrix_a_%dx%d.txt", size,

size);

sprintf(filename_b, "matrix_b_%dx%d.txt", size,

size);

sprintf(filename_res, "res_brute_%dx%d.txt", size,

size);

generate_matrix(size, A, filename_a);

generate_matrix(size, B, filename_b);

clock_t start = clock();

brute_force_multiplication(size, A, B, C);

clock_t end = clock();

 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

brute_times[i] = (double)(end - start) /

CLOCKS_PER_SEC;

save_matrix(size, C, filename_res);

start = clock();

dnc_multiplication(size, A, B, C);

end = clock();

dnc_times[i] = (double)(end - start) /

CLOCKS_PER_SEC;

start = clock();

strassen_multiplication(size, A, B, C);

end = clock();

strassen_times[i] = (double)(end - start) /

CLOCKS_PER_SEC;

for (int j = 0; j < size; j++) {

free(A[j]);

free(B[j]);

free(C[j]);

free(A);
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

free(B);

free(C);

write_execution_times("execution_times.csv", sizes,
strassen_times, dnc_times, brute_times, count);

printf("Execution times saved in execution_times.csv\n");

return 0;

OUTPUT:
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

OBSERVATION
ANALYSIS:

CONCLUSION:
Strassen’s matrix multiplication algorithm improves the efficiency of
traditional matrix multiplication by reducing the number of recursive
multiplications from 8 to 7. This reduces the overall time complexity from
 BHARATIYA VIDYA BHAVAN’S
SARDAR PATEL INSTITUTE OF TECHNOLOGY
Bhavan’s Campus, Munshi Nagar, Andheri (West), Mumbai – 400058-India
Department of Computer Engineering

O(n^3) to approximately O(n^{2.81}), making it advantageous for large

matrices.

Key Findings:

1.​ Efficiency: Strassen’s method is significantly faster than the

brute-force approach for large matrices.
2.​ Overhead: The algorithm introduces additional overhead due to
recursive calls and matrix additions/subtractions, making it less
efficient for smaller matrices.
3.​ Practical Use: It is widely used in applications that require fast
matrix multiplications, such as graphics processing, scientific
computing, and machine learning.

Final Verdict:

●​ Best for large matrices where reducing multiplications leads to

significant performance gains.
●​ Not ideal for small matrices due to the extra computational
overhead.
●​ Further optimizations, such as the Winograd variant, can improve
performance even more.