Discrete Mathematics
Project
PROJECT NO: 9
A Project Submitted
in Partial Fulfillment of the Requirements for the
Degree of
Bachelor of Technology
in
CSE/ME/EComE
SUBMITTED BY: GROUP NO: 10
Group Members: 1. Mehak Kumar (240536)
2. Manya Awastha(240932)
3. Anshika Rawat(240387)
4. Aakriti (240354)
SCHOOL OF ENGINEERING AND TECHNOLOGY
BML MUNJAL UNIVERSITY GURGAON
May, 2025
Contents
●Problem statement
●Introduction
●Analytical Solutions
●Results of Simulations
●Conclusion
●Acknowledgement
● Reference
Problem Statement:-
The goal of this project is to analyze five problems that utilize the
Divide and Conquer Strategy, along with five corresponding
applications, respectively. Each chosen problem will be expressed
through recurrence relations. For every selected issue, we intend to:
● Define the recursive framework of the problems,
● Establish the associated recurrence relation,
● Evaluate its time complexity by applying the Master Theorem,
● Implement the algorithm in Python to showcase its functionality.
Introduction:-
In the design of algorithms, the divide and conquer strategy is a key
method employed to tackle intricate problems effectively. It involves
decomposing a problem into smaller subproblems, solving each one
through recursion, and then integrating the outcomes.
Divide and conquer algorithms typically follow homogeneous
recursion.
Key Concepts Applied:
1. The Master Theorem
It is a mathematical tool used to determine the time complexity of
divide and conquer algorithms that follow a specific type of recurrence
relation.
2. Time complexity
It is a way to describe how the running time of an algorithm increases
with the size of the input.
It gives you a mathematical estimate of the performance of an algorithm
— especially when the input becomes very large.
We often express time complexity using Big-Θ notation, which gives
an upper bound on how the time grows.
General form is :
T(n) = aT(n/b) + f(n)
In this equation:
● a represents the number of subproblems,
● n/b indicates the size of each subproblem,
● and f(n) denotes the expense of splitting the problem and merging
the results.
Application Recurrence Relation Explanation
1. Merge Sort T(n)= 2T(n/2)+n Divide into 2 halves,
merge takes linear
time.
2. Binary Search T(n)= T(n/2)+1 One subproblem of
half the size, constant
work.
3. Quick Sort T(n)=2T(n/2)+n Partitioning and
sorting two halves.
4. Strassen’s Matrix T(n)=7T(n/2)+Θ(n^2) 7 recursive calls on
Multiplication half-sized matrices
and matrix
additions/subtractions.
5. Karatsuba’s T(n)=3T(n/2)+Θ(n) Splits each number,
Multiplication combines using 3
multiplications and
linear-time additions.
Analytical Solutions:-
Write mathematical solutions of the problems
Strassen's Matrix Multiplication
Q4. A fintech company needs to multiply large matrices
(512×512) for machine learning models that detect fraudulent
transactions. Traditional matrix multiplication would take O(n³)
time, but Strassen's algorithm offers a more efficient O(n^log₂7)
≈ O(n²·⁸¹) solution.
Given sample 4×4 matrices:
[ ] [ ]
1 2 3 4 16 15 14 13
5 6 7 8 12 11 10 9
A= 9 10 11 12 B= 8 7 6 5
13 14 15 16 4 3 2 1
Sol:
Step 1: Split the Matrices
Divide each 4×4 matrix into four 2×2 submatrices:
Matrix A:
1 2
A11 = 5 6 [ ] A12 = [ 37 48]
A21 = [ 139 1014 ] A22 = [ 1115 1216 ]
Matrix B:
[
16 15
B11 = 12 11 ] B12= [ 1410 139 ]
B21 = [ 84 73] B22= [ 62 51]
Step 2: Compute Intermediate Matrices (M₁ to M₇)
1. M₁ = (A₁₁ + A₂₂)(B₁₁ + B₂₂)
¿
[5+15
1+11 2+12
6+16
×
][
16+ 6 15+ 5
12+ 2 11+1
=
][
12 14
20 22
×
][
22 20
14 12 ]
[ 12× 22+ 14 ×14
= 20 ×22+22 ×14
12 ×20+14 × 12
20 × 20+22× 12][
=
460 408
748 664 ]
2. M₂ = (A₂₁ + A₂₂)B₁₁
¿
[13+15
9+11 10+ 12
14+ 16
×
][
16 15
12 11
=
][
584 542
808 750 ]
3. M₃ = A₁₁(B₁₂ - B₂₂)
¿
[ ][1 2
5 6
×
14−6 13−5
10−2 9−1
=
][
80 70
184 162 ]
4. M₄ = A₂₂(B₂₁ - B₁₁)
11 12
[ ][
8−16 7−15 −120
= 15 16 × 4−12 3−11 = −176 ][ −128
−192 ]
5. M₅ = (A₁₁ + A₁₂)B₂₂
[ 1+3
= 5+7
2+ 4
6+8
×
][ ][
6 5
2 1
=
76 54
188 134 ]
6. M₆ = (A₂₁ - A₁₁)(B₁₁ + B₁₂)
[ 9−1
= 13−5
10−2
14−6
×
][
16+14 15+13
12+10 11+ 9
=
][
240 224
352 328 ]
7. M₇ = (A₁₂ - A₂₂)(B₂₁ + B₂₂)
= 7−15 [ 3−11 4−12
8−16 ][
× =
][
8+6 7+ 5 −112 −96
4 +2 3+ 1 −224 −192 ]
Step 3: Combine Results
Compute the four quadrants of the result matrix C:
C₁₁ = M₁ + M₄ - M₅ + M₇
[
460−120−76−112 408−128−54−96
= 748−176−188−224 664−192−134−192 ]
¿
[152
160
130
146 ]
C₁₂ = M₃ + M5
[
80+76 70+54 156
= 184+188 162+134 = 372 ][ 124
296 ]
C₂₁ = M₂ + M₄
[
584−120 542−128 464
= 808−176 750−192 = 632 ][ 414
558 ]
C₂₂ = M₁ - M₂ + M₃ + M₆
[ 460−584 +80+240
= 748−808+ 184+352
408−542+70+ 224
664−750+162+328 ]
¿
[196
476
160
404 ]
Final Result Matrix
[ ]
152 130 156 124
160 146 372 296
C= 464 414 196 160
632 558 476 404
Karatsuba Multiplication
Q5. A fintech company needs to multiply two large bank account
numbers efficiently as part of a secure transaction hashing system. We'll
use Karatsuba multiplication, which is faster than traditional methods
for very large numbers.
Given:
X = 12345678
Y = 87654321
Sol:
Step 1: Split the Numbers
We divide each 8-digit number into two 4-digit parts:
X = 1234·10⁴ + 5678
Y = 8765·10⁴ + 4321
Where:
- x₁ = 1234 (high part of X)
- x₀ = 5678 (low part of X)
- y₁ = 8765 (high part of Y)
- y₀ = 4321 (low part of Y)
Step 2: Compute Three Products
1. A = x₁ × y₁ = 1234 × 8765 = 10,812,810
2. C = x₀ × y₀ = 5678 × 4321 = 24,536,538
3. B = (x₁ + x₀)(y₁ + y₀) = (1234 + 5678)(8765 + 4321) = 6912 ×
13086 = 90,476,742
Step 3: Compute Middle Term
Middle = B - A - C = 90,476,742 - 10,812,810 - 24,536,538 =
55,127,494
Step 4: Combine All Parts
X × Y = A·10⁸ + Middle·10⁴ + C
= 10,812,810·100,000,000 + 55,127,494·10,000 + 24,536,538
= 1,081,281,000,000,000 + 551,274,940,000 + 24,536,538
= 1,081,832,276,496,538
Final Result
12345678 × 87654321 = 1,081,832,276,496,538
Results of Simulations: -
You need to present all results of simulation in C/C++/Python.
Conclusions:-
Acknowledgement:-
Reference:-
Here you can write all references including text book or any other
reference which you have used.
