DESIGNESANALYSIS

of
ALGORITHMS

unit-2

feedback korrections : vibha @pesu.pes.edu VIBHAMASTI

 Design and
Analysis of
algorithms

BRUTE FORCE APPROACH

-
When in doubt ,
use brute force -
Ken
Thompson

Straightforward approach directly based problem statement ( tends

°
: on

to to mind)
naturally come

Exhaustive search or
generate and test
°

candidates for
Systematically enumerating all
possible the solution
°

°
Check whether each candidate satisfies the solution

.
Inefficient approach

Q : Brute force find divisors of natural number

algorithm to a

.
enumerate all natural numbers less than n and check if

the number divides n

.
I to n must be checked exhaustive
;
Os : 8 board ,
queens puzzle : in a 64×64 all 8
queens
and
placed such that
they do not dash ( diff
diagonals ,
rows
,

diagonals) .

•
check all enumerations ( possibilities) of the S
queens

(6478 possibilities inefficient

; very
•

Q : Brute force search : linear search

( grows linearly)
void search(int *a, int n, int key) {
for (int i = 0; i < n; ++i) {
if (a[i] == key) {
printf("%d found at index %d\n", key, i);
return;
}
}
printf("%d not found\n", key);
}

for 100,000 elements, n 0.3 milliseconds

for 1,000,000 elements ,

~
2.5 milliseconds
BRUTE FORCE
sorting algorithms

selection sort

see unit 1 3
,
page

can -
-

Ei :& .
' =

:{ cnn.it#=i..En-i-i
= (n t ) -
+ ( n 2)
- t . . .
t I

un) = n Cn -
t)
E Ocn
'
)
2

bubble sort

adjacent comparison sort

Algorithm
for i -

-
O to i -
- n -
2 :

for j
-
- o to j
-

- n -

i -
l :

if arrcjtl ] Carr
Cj ] :

arrcjti and arrcj ]

swap
 Example : 5
,
3
,
2 , 8,3
ee

a
5 2 8 3
pass
I 3
j : O to 3
-
-
, , , ,

3 2 5 8 3
, , ,

3 ,
2
,
5 ,
3 ,
8
I

→
3 5 8 to
pass
-
- 2 2 , , ,
3
, j : O 2

2 ,
3 3
,
5 ,
8
,

2 3 3 5 8
pass =3 ,
, , ,

=4
2 3 3 5 8
pass ,
, , ,

5 2 3 3 5 8
pass
-
-
,
, , ,

efficient bubble sort

if swaps done in iteration the array is

no
any
°

sorted and the is terminated

program
. worst-case time
unchanged ; best -
case time improved

flag for sorted (assume sorted

.

using a to be at

every iteration ; mark as unsorted once a swap

is made)
Algorithm
for i -

-
O to i -
- n -
2 :

sorted = true

for j
-
- o to j
-

- n -

i -
l :

if arrcjtl ] Carr
Cj ] :

arrcjti ] and arrcj ]

swap
sorted -
- false

if sorted is true :

break

Time
complexity

can .EE?Ei-iz--Ein.i.i
=
(n -
t) t (n - 2) t . . . t I

Ccn) =
nC# E O ( NZ )
2
BRUTE FORCE
searching algorithms
search for in text
a
pattern a
given
°

seaential search

linear search
page 3
-

string matching

"
) text )
"

eg :
pattern : TEXT (
length m : below Clength n
- -
-
-

° I 2 3 45 6 7 8 9 10 11 12 13

R E A D T E X T B O O K s

i -
- O T E X T

i -
- l T E X T align and
slide until
i -
- 2 T Ext
match found
i -
-
3 TE XT s

i -

- 4 TEXT
i -
- 5 T E X T

iterations
worst case text
length pattern length -11
°
-
=

•
0 to n -
m or n -
Mtl trials
String matching
int find(char *text, char *pattern) {
int n = strlen(text);
int m = strlen(pattern);
int i, j;

for (i = 0; i <= n - m; ++i) {

j = 0;
while ((j < m) && (pattern[j] == text[i+j])) {
++j;
}

if (j == m) {
break;
}
}

if (i > n-m) {
return 0;
}
return 1;
}

output
EXHAUSTIVE SEARCH
set of all
.

generate a
potential solutions
systematically
compute cost of each
permutation
.

•
find optimal solution
by comparing every solution with
solution
every other

travelling salesperson
°
a
salesperson has to travel from source to dest with
distances)
minimum tour cost (
weights (
find every of
°
brute force solution -

possible permutation
I]
n -
l cities [ I ,
.

-
. . . .
n
,
-

all possibilities

exponential growth -
NP
problem (n D !
-

Hamilton ial Circuit visit all in

vertices a
graph
.
-

start and end

exactly once
,
on the same vertex

°
Find shortest Hamiltonian circuit in a
weighted connected
graph
O : Find optimal circuit
start q end
I 2
A b
5

3
3! = 6
permutations
8 4

c d
7

a → b → c → d → a =
2+31-71-5=170
a → b → d → c → a =
2+4+7-18 =
21

a → c -7 b → d → a =
8-13+41-5 =
20

a → c → d → b → a =
8-171-4-12=21

a → d → b → c → a
=
5-14-131-8 =
20

a → d → c → b → a =
5 -17+3+2=170

Optimal paths :

a → b→c→d→a
a → d → c → b. → a
O : Find circuit
start qeud
I 2
A
b

7
5
38
c d
l

a → b → c -7 d → a =
2+81-1+7 =
18

a → b → d → c → a
'
-
2+3+1+5 =
④
a → [→ b → d → a =
5-181-31-7 =
23

a → c → d → b → a =
5-111-31-2 =

④
a → d → b → c → a = 71-3+81-5 =
23

d b → a
=
a → → c →
7-11+8-12 =
18

Optimal solution
a→b→d→c→a
a -7C -
id Sb
-
→a
KNAPSACK PROBLEM

with M objects with

weights and values
bag capacity
•

°
0/1 knapsack ; object either picked up or not [no fractions)

Optimisation : maximise profit due to objects

eg
: a thief tries to maximise profit with finite
bag size

l and
weight value)

☐
exhaustive search call subsets found ,
value and weight
calculated , optimised subset found)

•
2^ subsets

0 :
knapsack capacity w= 16

value
Item weight
1 2 20
2 5 30
3 10 50

4 5 10

subset weight value

1 I} o o

2 { I} 2 20

3 {21 5 30
4 {3} to 50
5 {4 } 5 10

.
 6 { 1,2} 7 50
7 { 1,33 12 70
8 11,43 7 30 optimal
←
912,33152€
10 { 2,43 10 40
it { 3,4} 15 60

12 { 1,2133 17 not feasible

13 { 1,2143 12 60

141123,4 's 17 not feasible

1512,3143 20 not feasible

16 { 1,213,43 22 not feasible

•
Exhaustive search : run )

Iof Assignment PROBLEM

There people need

are n who to be
assigned to
.

n
jobs

The cost of ccisj ]

assigning
is
job j to a
person i
°
a

Minimisation problem
°

J, Jz - . . .
.
Jn

P, C
,,
. i '

: . .

"

<

-
(

Pn '
Os : Jl J2 Js 54 n ! permutations
Pl 9 2 7 8
P2 6 4 3 7
P3 5 8 I 8
124 7 6 9 4

fit n people into n

jobs Chl?

4! 24 possibilities
-

Ji -
J2 -53-54

I -2-3-4 3-1-2-4
I -2 -

4 -

3 3 -

I -

4-2
I -3-2-4 3-2 -
I -4
I -

3-4-2 3-2-4 -

l -

4 -

2-3 3 -
4 -
I -2

( -
4-3-2 3-4-2 -
I

2- I -3-4 4 I 2-3
-
-

2- I 4-3 -

4 -
I -
3 -
2

2- 3 -
I -4 4 -
2 -
I -3
2- 3 -
4 -

I 4 -
2
-
3 -

I
2 -
U -
I -3 4 -
3 -

I -2
2-4-3 -
I 4-3-2 -
I
DIVIDE u CONQUER
divided into smaller sub problems of
big problem
° -

same nature

°
solve smaller
problems recursively
°
combine the solutions

instance of
size n

sub -

problem sub -

problem
of size 42 of size nlz

of of
problem problem
size I size 1

Solution
to
original
problem

time spent
T
Tcn) = at Tcnlb) tfcn>
on
and
dividing
n
combining
lb instances
Master 's theorem

i÷÷÷÷÷÷÷÷÷÷
35 unit I
pg ,

for the recurrence

Tcn) = att TCM b) t fln)

if fcn) E O Cnd ) where d ZO

merge sort
EBoETaotZgEgaggggg
Mfa
°

Merge :
merge a sorted sets to form a
larger merged set

SI S2

10 30 50 20 25 26

F TTPT T TTY X IT out of

① ②③④⑤ ⑥ ①② ③ ④
bosuonds
10,20 , 25,26 30,50 ,
exshaetusted

Divide : size of
keep dividing into halves until array l
-
• -

(each element is a sorted array of size D

25,1548
/
,
16
-

25415 8,116
/ h
④ ⑤⑧ → elementary case ( size =D
Algorithm Merge sort CAIO . . . n -
D)

H recursive
11 input ACO I]
:
array n -
. . -

I]
11 output : sorted array Aco . . . - n -

if n 70

copy
A CO . . . Lnlz) -
I] to B [0 .
.
.
Lnlz) -
I ]
I]
copy Al Lnm I ] to CCO Lnlz ) -

n
-

. . . . . . .

Merge sort CBCO . . .

.hn/2J 1) -

Merge sort ( CEO . .

.hn/2S 1) -

Merge CB C A) , ,

Algorithm merge ( BIO II )

p IT ,
CCO
g- IT , ACO ptg
-
- . . . .
. . . . .

11 Merge two sorted arrays

into one sorted
array
11 input :
arrays 1310 p IT
-
and Cco I] both sorted
q
. - -
.
-
.

,
-

11 output :
array Alo . . .

ptq I ]
-
of both
arrays
'
elements ,
sorted

i K
O
j O O
- - -
- -

,
-

while icp and jcq

if ( Bci ] E
Ccj ) )
ACK] =
Bci ]
i = it 1
else
ACKT -

-
Ccj ]
j -
jet
K -
- K -11

if i =p
ACK
copy Ccj . . .

g- IT to . . .

ptg
-
I ]

else
BC i p IT to ACK I]
copy ptq
- -
. - . .
. .
Q: Show sort of 8,3 , 2,9 , 7,1 , 5,4
merge
low -
- O

7
O l 4 5 6 7 high
-

3
-
2
8 3 2 9 7 I 5 4 mid -
-
lo -177/2
, , , , , ,
,

I I =3

8
,
3 2 9 7 I 5 4
, , , , ,

I t t t
8 3 2 ,
9 7
,
I 5
,
4
,

d d t t t l l l
8 3 2 9 7 I 5 4
↳ t b d → ← → ←

3, 8 2
,
9 I, 7 4,5

- I → a
2 3 8 9 I
,
4 5 7
, , , , ,

→ a
1 , 2 3 4 5 7
,
8
,
9
, , , ,

← merge S
,
71
, 712×3
time
Tcm 217427 t I
11/2/34/15
=
n
-

(
comparisons) Sz Ky " s "6
5
comparisons
Mater 's theorem: a 2 d I b 2
- - -
- -
-

, ,

a = bd ( 2=27

← improvement
tch) E
Olnlogn)
:
.
over 01h27
implementation in C

void merge_sort(int *A, int l, int h) {

if (l < h) {
int m = (l + h)/2;

merge_sort(A, l, m);
merge_sort(A, m+1, h); for 1,000 elements
merge(A, l, m, h); ~
0.2ms
}
}

void merge(int *A, int l, int m, int h) { for 10,000 elements

int B[MAX]; ~
I -7 MS

int i = l, j = m + 1, k = 0;
while (i <= m && j <= h) {
if (A[i] <= A[j]) { for 100,000 elements
B[k++] = A[i++];
~
20ms
}
else {
B[k++] = A[j++];
}
for 1,000,000 elements
}
while (i <= m) {
~
200 MS

B[k++] = A[i++];
}
while (j <= h) {
B[k++] = A[j++];
}

k = 0;
for (i = l; i <= h; ++i, ++k) {
A[i] = B[k];
}
}
 quick sort
•osoEsaoooogFB

5 3 1 9 10 4 6 28

°
Hoare's partition method
.

pivot element
•
variations of as
pivot
pivot : first element in
array !
°

divide into 2 Ali 's and Acis >

groups
:
Lp p
•

5 3 1 9 10 4 6 28 n -
-
8

p i j

is low -11

j high
-
-

p
-
-

pivot
5 3 1 9 10 4 6 28

p i i i
j j j
355 K5 975 455675 2875
✓ ✓ r
stop stop
v

swap
5 3 1 4 10 9 6 28

i ij j
j 1075
stop
495 1075
r
Stop
swap jth and pivot when i and j cross
 P i j
4 3 I ⑤ to 9 6 28
partitioning
-
- T successful
LHS RHS
pivot
sort from quick sort from
quick
low to
j I jet to
high
-

I 3 4 6 9 10 28

g. sort

Q : show qsort for the

array

5 28 7 14 10 3 2 I

i j
p
stop stop
2845 145

icj →
swap iqj

5 1 7 14 10 3 2 28

i j
stop stop
745 27/5
icj →
swap ieej

5 1 2 14 10 3 7 28

i j
stop stop
1445 345
icj →
swap
 5 I 2 3 10 14 7 28

g- stop i top

jci →
swap p and j

3 I 2 ⑤ to 14 7 28
- -

3 1 2 10 14 7 28

i i
p ji p i j j
✓
j stop stop stop stop 28710

swap jeep swap ieej

2 I 3 10 7 14 28
-

j i

ij stop
stop stop
p > 0013

j stop swap pg j

swap jeep 7 ④ 14 28
-

I 2 3 14 28

p ij

Final array

I 2 3 7 10 14 28
 HI )
Algorithm Quick sort CALL . .
-

11 Sorts sub
a
array by quick sort
11 Input : a sub
array ACL . . - h] of ACO .
. .
n -
I]

11 sorted in
Output : a sub
array All . . . h]
ascending order

if L C h

s = Partition ( ACL . . . HI )
Quicksort CALL . . .
s D)-

Quick sort LA[ Stl . . - h'd )

Partition CALL h])

Algorithm - - -

11 Partitions first element pivot

a sub
array using as

11
Input : a sub
array ACL . .
h] . of Alo . . .
n
-
I]

11 Output : a
partition of ACL . . . h] ,
with the split position returned

All ]
p
=

i -
- L

j
-
- h

repeat
repeat i it I until ACIIZP
=

repeat j j I until AGT Ep

-
-
-

swap Cali ] , ACJD

until izj

if j t l

swap CALLS, ACJI)

return j
IMPLEMENTATION in C

void quicksort(int *a, int low, int high) {

int j;
if (low < high) {
j = partition(a, low, high);
quicksort(a, low, j - 1);
quicksort(a, j + 1, high);
}
}

int partition(int *a, int low, int high) {

int pivot = a[low];
int i = low + 1;
int j = high;
can also

while (i <= j) { ← be

0
while (i <= high && a[i] <= pivot) {
strict
( repetitions)
++i;
} ←
O
while (j > low && a[j] >= pivot) {
--j;
}
if (i < j) {
// Swap
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}

// Crossover
if (j != low) {
a[low] = a[j];
a[j] = pivot;
}
return j;
}
efficiency class

best CASE

°
Best case : split 50-50

5 4 6 8 9
②2③
3 10 9 n
-
-

i
stops

comparisons of pivot)
htt Cho
repeating
-
-

5 ① I 2 3 5 6 10 9 8 n -
- 9

comparisons n
-
-

a -_ 2

←
basic
op b -
- 2 a
-
-
bd
( Ch) = 2 ( ( M2) t n d -

-
I
best best

Oln
Tcn)
login)
=
worst CASE

On
2 4
④3 6
5
⑤ ③

[
comparisons = ntl

C.
=
CHI ) t ht -13 = CntDCnt# -
3
worst
.
. .

Tcn) = 0cm )

CASE
average
take different locations
partitioning can place at n
.

Cavgcn) ht
-

f [ Cn -117 t
Cavgcs ) t
Cavgcn
-
I -
s )] for n> 1

( (n ) = 2n lncn) = 1.38 n
logan
avg
E'iiiiiitttYEEHiitt.it
'

I size decreases
(only I sub instance)
decrease and
conquer
a

•
two conditions
1- the elements must be in order ( sorted array)

element ( not linked list)

2 .

every randomly accessible

example

21 8 21 32 89
key 65 72 100
-

0 I 2 3 4 5 6

Low high

mid -
-
low
thigh =3
2

array (mid ]
L
key

binary search on sub

array

-
8 21 32 65 72 89 100
0 I 2 3 4 5 6

Low high
Algorithm Binary Search ( Allow . - -

high ] ,
K)

11 Implements recursive
binary search
11 Input array sorted
: ACO n I] in
ascending order
-
.
. .

11 Output : index of element K ,

if found ,
or -
I otherwise

if low s
high
mid -
-
(high-low ) 12
if AC mid ] =
-
- K

return k

else if A [ mid ] 7k

return
Binary Search ( Allow mid I ] K)
-
. . . .

else
return
Binary Search ( Acmidtl n I ] K)
-
. . .

else
return -1

Algorithm Binary Search ( ACO n IT K)

-
. .

,
.

11 Implements non -
recursive
binary search
11 Input array sorted
: ACO n I] in
ascending order
-
.
. .

11 Output : index of element K ,

if found ,
or -
I otherwise

while low E high

mid -
-
(high-low ) 12
if AC mid ] =
-
- K

return k

else if A [ mid ] 7 k

high mid I
-
-
-

else

low -
- mid -11
return -
I
 TIME COMPLEXITY

d
Tcn) = Tcnlz) t t a =L a = b
b -
- 2

d- - O

Tcn) OC )
log n
-

unsorted set

Tcn) = Max (Tsortln) , TBS ( n))

Tcn) =
nlogn

IMPLEMENTATION IN C

iterative recursive

int bs_iter(int *a, int n, int key) { int bs_recur(int *a, int low, int high, int key) {
int low = 0, high = n - 1, mid; int mid;

while (low <= high) { if (low <= high) {

mid = (low + high)/2; mid = (low + high)/2;

if (a[mid] == key) { if (a[mid] == key) {

return mid; return mid;
} }
else if (a[mid] > key) { else if (a[mid] > key) {
high = mid - 1; return bs_recur(a, low, mid - 1, key);
} }
else { else {
low = mid + 1; return bs_recur(a, mid + 1, high, key);
} }
} }
return -1; return -1;
} }
binary trees

°
non -
linear data structure disjoint sets
( both binary
°
finite set of nodes T t trees)

( root left subtree

°
either empty or 3 subsets
, , right subtree )
•
faster insertions and deletions
.
traversals : refer Data structures
,
Sem 3

height of a
true
of empty
height = I
-

height of tree = It Max (

height cleft) height (right))
,

Algorithm Height CT )

if T= 0 11 empty tree
return -
I

return It Max (
Height LTD Height Ctr)) ,

Recurrence Relation

basic operation : addition

←
Acn) =
Acn
, ! + A
Cnn) + I

non -

symmetric ;
not
straightforward
 basic ( F- 0)
operation : comparison

external node : empty set

internal node : non
empty
-
set

D one internal node

int
f
n → int -
-
l

x → ext -
- 2

c- ext

2) two internal nodes

n = 2

x =3

x -
- htt

total nodes = ath

total comparisons = ath

=
ntltn
= 2h -11

= Ocn)

number of additions = n
MULTIPLICATION of LARGE INTEGERS

"

42
IX - l
X 3 5
total : 4 multiplications
20 o

(basic
I 2 6 0 operation)
I 4 t O

axb

divide
it digits
a -_
9,90 ( even) 9=91×10%+90 pad with
← zeroes

b -

- b , bo b -
- b, X 1042 tho if odd

ax b = Ca , x 10^12-190) ( b xlonkt , bo )

=
(a , xb ,) x 10
"
t ( a , xbutaoxb ,)x 10^12 t
aoxbo

10h12
"
10 t
=
Cry x C, X + Co

① Co = aoxbo
② ca
-
-
alibi
← rewritfedtuoce # of multiplications
③ C
,
= Ca , -190) xlbitbo) -

Ccztco)
Q: 33×24 n -
- 2
A , ao bi bo

Cz = 9, X b, = 6

Co =
aoxbo = 12

C, = Ca , tao) x ( bilbo) -

Ccztco)
= 6×6 -
18
= 18

33×24 = 6×102 t 18×101-12

= 600 t 180 C- 12
=
792

Q: 1233×1124
A, ao b, bo

12×11 → (1)
Cz
=

Co = 33×24 → (2)

c, =
(12-133)×(11-124) -
C 12×11 -133×24)
=
(45×35) ( 12×11 -

+33×247

→ ( 37
(1) 12 X 11
9 au b , bo
,

Cz 1×1 I →
(4)
-
- -
-

Co = 2×1 = 2 → (5)
C
,
= 3×2 -
( I -12 )
(6)
=
6-3=3-3
12×11 = 1×102-1 3×10 t 2 = 132
 (2) 33 X 24
a
, ao b, bo

Cz = 3×2 = 6 →
(7)
Co
-
-
3×4=12 - 7
(8)
c, = 6×6 -
( 12+67
=
18
#(9)

33×24 = 6×102-118×10 t 12

= 792

(3) 45 X 35
91 90 b, bo

Cz = 4×3 = 12 → (IO)
co = 5×5 -
- 25 → 41 )
c, = 9×8 -

(12-125)
= 72-37-42)
=
35

45×35 = 12×102+35×10 -1 25 = 1200 t 350 t 25 =

1575

12×11 =
132
Cz
=

Co = 33×24=792

(132-1792)=651
1575
c, = -

1233×1124 = 132×104 t 641×102-1792

=
1320000 t 64100 t 792
=
1385892
 K
Mln)=3MCn/2) n -
- 2
k=
logan
Mll) -

- I

Monk)
"
=3 M( 2 )
"
2)
-

=3 3 -

Mca
3.3 ( 2K 3)
-

= -

3 M

't i
mean )
-

=3
"
i-k =3 MCD
"
=3

31092N ) 10923
Mcn) E O( @ (n ) O ( ht 585g
.

= ,

Acn) =3 Acnlz) t ch for n > I

,
All )=1

-585
Acn) E O ( ht )

fttasfen 't MATRIX MULTIPLICATION

°
For two 2×2 matrices ,
seven
multiplications
instead of 8 ( brute force) ( 21-2-121-2)

K: ::H:O: ::H :O: ::L

( Mit my My Mzt Ms
) 8 additions
= -

Ms +

Mzt My M, tmz Mz TMG

-
 M, = (aoo -1911) * (boot bn)

Mz Caio t 9,1) * boo

-

Mz
=
doo * ( boi -

bi , )

my =
all
*
( bio -
boo)

Ms = (doo t Aoi)
*
bi ,

law doo)
* ( boot bo , )
Mo
-
- -

My =
Cao , -
ah ) * ( bio tbh)

.
10 additions t 8 additions =
18 additions

FOR ANY nxn MATRIX

pad zeroes if not square

°
divide matrices into sub matrices

K : i :H : : :÷H :O: : :L
Mln) - 7 Mcnlz) MCI ) =/
2K
n K
logan
-
-
- -

""
MC2
"
) = 7 Mca ) theory :
7.7 M ( 2K 2)
can
get
✓
-

=
n2 not
i
'
2K ) ,
-

= 7 MC yet
807
7109 an n' 0927 nd n3
-

= 7k = = = c found

807
m2 )
-

Tcn ) f @(
°:
x
shown steps
.

A B

M, = (A oo t
Aa) * ( Boo t Bil)

Ht : H : :D Cl : :3 xl 's :D *

e-

lO
-
-

I'm imminent, minima :minimal

'
-

(O ll ll

boot bn)
M '
I % off ? "

mi
: as :{ 717 ? iz

'

and so on
Q: to find of
Design an
algorithm the max elements
using
divide and conquer strategy .

Find Max C ACO D)

Algorithm n -
. . -

11 input : of elements
array
n

K output : max element

mid -
-
(Ot n -
1) 12

if size CA ) -
- I

return ACO ]

left Find Max CALO mid ]) low G

)
- Max =
. . -

right - Max =
Find Max ( Acmidtl . . .
)
n -13
high
left
if - Max >
right - Max

return left -
Max

else
return
right - Max

52
O l 2 3 4
8 9 4 6 I

- -

° I 2 4 6 I
U
2 8 9 -

- u

4 6 I
Sy ! ↳
2
6

/
✓

q
c
\ g
 Code in C

int maxelement(int *a, int low, int high) {

int mid = (low + high) / 2;

if (low < high) {

int max1 = maxelement(a, low, mid);
int max2 = maxelement(a, mid+1, high);
if (max1 > max2) {
return max1;
}
else {
return max2;
}
}
return a[low];
}

O: Find key element in a set of elements

both
like
binary search
,
but search halves

Q: an brute force and divide and

Find
using conquer

brute force : a * aka . . -

a n times

a'" " am " '

divciodnequaenrd :{ a
*
,

,
n

n
>

- I
,
Q: Tch ) -

-
41742) th Tcl) =/
,

a -

- 4
b -
-
2
d- - I

d
a 7 b

4 72

logba )
Tcn) E OC n

Tch) E O ( m2 )

Q: Tch) -
- 4TCn/2) th
'
Tcl) =/
,

a=4 b -
-
2 d -

- 2

d
a = b

4=4

Tch) E O Cnd log n)

Ch' )
Tcn) E O
log n

'
Q: Tch) = 4 TCM 2) t n
,
Tcl ) =/

a
-

- 4 b -
- 2 d =3

d
a c b

Tcn) C- O( nd )

Tch) C- O(n3 )
Q : Given n
positive integers , partition them into 2 disjoint
subsets with the same sum of their elements (Partition
Problem)

I 2 3 4 5 6
eg :

2,4 4 6

1) 3,4 Eg 3,5

brute force : exhaustive search of all subsets and find

subsets with the same sum

Tcn) E OCI)

Q : Dutch white
flag problem : red , ,
blue balls to be
rearranged
into order of red white and then blue
,

eg :
input : O l 2 0 I 2

output : O O l l 2 2

Algorithm #I :
traverse
through array once and
count number of O 's I 's and 2 's and then
,

replace array with sorted no .s

#2: partition
Algorithm 3-
way
000 . - .
111 . . . Unknown 222 . .
.

low
high
start
mid
 acmid ] o → swap with low and increment
-
-

mid Ee low

I → correct
acmid ] =
partition
move mid
right
acmid 3=2 →
swap with end and decrement
end

https://www.geeksforgeeks.org/sort-an-array-of-0s-1s-and-2s/

D: Quick sort
using Dutch
flag algorithm (3 -

way sort)

2 6 5 2 6 8 6 I 2 ⑥ ←
pivot

=6
pivot

normal ⑥ _Qs

⑥ ⑥

QSO
Dutch

Index inversion
:
problem
if aCjJ=i
Output : count of II and act J j
-
-
-

0cm ) selsort and for

:
run 2
loops like check
condition
0 I 2 3
I O
3,2
, ,
 Ocnlogn) : hint -
use
merge sort

termination condition : o '

I O

O l 2 3 4 5 6 7
I O 3 2 4 6 5 8
, , , , ,
, ,

- -

f b t b
I O 3 2 4 6 5
,
8
, , ,
- -
- -

t b t b t b t b
4 5 6 7
I 0 3 2 4 6 5 8
i i
j i j i j j

if acid if acis j if acis j if acij j

j
- - -
- - -
- -

ago
-
- i acj ] -
-
i aged -
-
i aCjT=i
T T T
# inv # inv # inv # inv t

merge normally
3 4 5 6
7 18
°
I 2

3 2 O 4 ,
6 5
,
, ,

ini j
i
j
if ali ] else if ali ]
j Cj
-
-

acj ] -
- i inc i

# inv p

inc both