CS & IT 20 25

ENGINEERING
Algorithms

Divide & Conquer

Lecture No.- 06 By- Aditya sir

Recap of Previous Lecture

Topic
Quick Sort
Topic Code

Example
Timscomplexity
Topics to be Covered

Topic Imp Questions 148

Topic
MatrixMulliptication

3
Quickly
Time Complexity

Bestead Ohlogn ungodinput

random
to

01m Sorted input

Case
Worst
ase desc
4
Spacecomplexity
Recursion
Bastase of logit Stack

6 07
worst case O n

Stewdaursionstacke

5
[MCQ]
PYS
#Q.Let P be a quick sort program to sort numbers in ascending order. Let t and t2
a 1
be the time taken by the program for the inputs [1 2 3 4] and [5 4 3 2 1]
respectively. Which of the following holds?
Tm
t iPI ase order 7 4
to ip2 desc order n 5

A t1 = t 2 B t1 > t
it
C t1 < t 2 D t1 = t2 = = 5 log 5

Ans
Asc order ip Sort
worst case of Quick
Desi order ip

Asymptotically 01m

Absolute ti 7 4
H
ti 72 5

5
[MCQ]
Using
#Q.Let P be a Quick Sort Program to sort numbers in ascending order suing the
first element as pivot. Let t1 and t2 be the number of comparisons made by P for
the inputs {1, 2, 3, 4, 5} and {4, 1, 5, 3, 2} respectively. Which one of the following
holds.

A t1 = 5 B t1 < t 2

C t1 > t 2 D t1 = t 2

AE
01m 5
Inputs 12,34 to n 5

med
5 as 2 to 5
Inputa 4,1 5,3 Me

unsorted
nlogn

Best Case to

worst case to

5
[MCQ]
#Q.Quick Sort is run on two inputs shown below to sort in ascending order
taking first element as pivot
i. 1, 2,3To....N
ii. n, n – 1, n – 2, . . . , 2, 1 n
i

t
n
TE
Let C1 and C2 be the number of comparisons made for the inputs (i) and (ii)
respectively. Then,

A C1 < C2 B C1 < C2

C C1 = C2 A D We cantsay anything for arbitrary n

C N n N ase order Sorded
Impett 1,2

N N I I n N
de order sorted
Input 2

Worst Case
II Input of
Quick Sort
n
01m

5
[NAT]
Im Numericalamante
#Q.Assume that merge sort takes 30 sec to sort 64 elements in worst case. What is
the approximate number of elements that can be sorted in the Worst case using
merge sort using 6 minutes?

É
Q

In Given In worst case

t 30sec

n Eminutes
Am 512
TE O n loan t c n1
nelems in worst case sort
Solni of merge
T O nlogn
n elems TC In loan

C
I nlogn
t nlogn2 sec
sec

7 64 t 30sec
given

C 30sec 64 6 1 30
nlogy
64 109,164 30 c

64 109 26 30

5
2
fC I
6min
Ed t
6 60 see
Ohlogn
o
2

6 60 sec nlogn
K 2 4608
61 6 60
nlogy
f
12
12 8 8 28
nlogy 6 60
6,1 if
8 256 4608
29 nlog.sn 4608
D
we
29
Left 4 9 512 5120
512
Kx 2 9 512
460
Have n 2k 29 13512 4608

5 Ins 114 92
why 1092 bases in lost
nunge

tf
n n b n 1 n
751 7153 75110

n 5k k 1o
A
170 or

5
[NAT]
#Q.An array of 25 distinct elements is to be sorted using quicksort. Assume that
the pivot element is chosen uniformly at random. The probability that the pivot
element gets placed in the worst possible location in the first round of partitioning
(rounded off to 2 decimal places) is ___.
WI Ami
0.01
Soli
25
D n

elem to
prob of any
Ptolemy
be picked
111252
Worst position location

n
T

on the basis
Divide After Partition 5
gets placed
wherever pivot
of or elem
Mtn met
Favorable elements
2

Pros 5

0.0 0

5 ayy
Problem
5 Matrix Multiplication
we

size
w.net Swanton of

5
Basti Ann Brian Can

Ingued Arne Braxes Crixes

multiplicable only if 14 22
AIB are

5
req Matrixaddition

A
f's B
15,8

a f
I L
D L
2X
2 2

Ann Bnxn Cnxn

5
Time Complexity Previous Method
of
Matrix Addition
Of
for i i n
A B
nxn
for j l n

Cfi j Ali j Bfi j

TC 0 matrix Addition

5 matrix subtraction
Matrixmultiplications
each man
Two Square Matrices
given
A B
5 2 7 107

3 6 4 8
3 5 4 7
2 2

5
Matrix Multiplication
ingeneral
Non
A B c
b biz on 42
a 912

921 922 bar bar Ca Cin

Add mud 4
then G An bit 9,2 52

92 b b 2
8
62 Az but 922 321 1 Multi

18 22 Azix biz 922 522 1 2

Code Prov Matrix Multiplication logic II
of

AEEE i ten
e

For l n
j
Can art for
l n
for k

do
i j Afi k B k
j
better
using Dn
TC 0 m
approach
18
Divide
Conquer based Approach
Eg B12 n
An
Az B1
A 2 3 4 3 4 56
Ci Liz H
8 mat mul
Ii

t I a mat addith
5 7 24 16 1678 8
An 4 4
20
2

Safdie em add Mal

ftp.conomn
where G EM 0 1
AII 2

4sub matrix Adding

J
62 A
AIB E2 112

Ba AIR
Keeffe
1,2

A Bn AIR 1,2

A B Subprobloms
18 nan Died
Divide an subproblem

Original Problem
72 7
nxn

Tin 8 71 12 01m
gate

18
Let Tin represent the Time Complexity to multiply
Two Somare matrices A B_ each of size nxn

Somare
Matsitrocurrance
T n C n 2
Dnc
for matrix
based
win
2k n

Tin 818T N2
b1 b n
4143
m

a mxn 82T In 2 2bn bn 23k m

K
18 8 T n 2 2 3bn 23 m
Term 8k
Gamal m

Tin 8k T NK 2k 1 bn

Let I
Me 2 K 1092
2k n

8k m T In n T 1 n 1 bn

n C In 1 bn

n C bn bn 0
simple Dnc based approach
TC after using this
18 is also 01m
Observations i

there
In Dnc based matrix multiplication
sub matrix multiplication
are sub problems
Ca Cis Ca 622
involved in getting
the
Time Complexity will only be reduced if
multiplications are reduced
no of sub matrix
8 to a smaller value
from logic
H
Ab

18
Research
agffa
Topic : Stras Sen's Matrix Multiplication
Result Strasser's Research
P = (A11 + A22)(B11 + B22) of
Q = (A21 +A22)B11 1 on matrix multiplication

TIBE.in
R = A11(B12 – B22) 1
original
S = A22(B21– B11) problem­
T = (A11 + A12)B22
U = (A21 – A11) (B11 + B12) YAij
Bij.cij Max
V =(A12 – A22)(B21 + B22)
created used sub matrices
C11 = P + S –T + V Additionally
C12 = R + T P Q R S V V 12
T 72
C21 = Q + S
C22 = P + R – Q + U
Let T In represents the TC for the matrix

multiplication using Strassen's Approach

Tin c n
Strasson's
Recurrance
THE bae n
I

Tin 2 7 T 1 2 b
MY
Tin bn
717T 722 bnf
72T 7 22 7b bn

18
General term
Effy

7kt Mar bn
Tn
i O

GP a a 2 21 22 23
I I
2 4 8
14 2 24
162
Tin 7kt In 2k bn

7 1 bn
912k I

2k n
2k n

uk 74C bn 12
18
10922
TIM 74C 6
7 n N
VII
Pln 7 TR b

7
I Let bted const

ITIN dx 7
I­R logan
Tin 017k 7K 711091
I
MÑ

06 plog
18 2816
1097 n
Time Complexity Summary
Completed matrix mud esomare I
Hon
I 01m

Simple Dnc 01ns

81
0 n2
Strassen's based Dnc

20
Speedy
Non Dnc Old Constant

Simple Dns Reunion stack

011092
Strassen's Dnc P.GR ST U V
O logn net in
I n'I­T1

Oln3 0 n281 01m

20
THANK - YOU

Telegram Link for Aditya Jain sir:

https://t.me/AdityaSir_PW

19