elasSMA

Date
Page 1 C
imon Ansari 272
Space ime coOmpleai
Alorithnn:It is a proceolure to Solve
aproblenn io finite numbeu a
SHeps
Theue may be more Thon 1 olgorithm
fo peufornming he Same tesk
Eq: Sorting.
Hence,E isnecebsau to ole cicle
which algorithm s bette in wuhich
Sitvatton.
Alqorithns OMe
oUnalySeo with_2
factor-Space tinneiit tak es
less Space thenits executom_tim0
is hiqheu
Geneually, time analys/'sKi S as qivenmon-
importance while hmakin9 COmparitjcn
of algorithna of SOme
 ASSMAte
Date
Poge
Aiman Anari 272
Space CompCxily
fs is olefined os Ommovnt f memony
memony
mqveut an algorithm to run.
Space Compleri s conmpute d
uSing
USin
2 factos Constant charactoristfcs
i I n stan Ce characteristicg
S Ct Sp
C Constoant
Sp Voujable
Example 1:
h e Space req uirement for this ctaement
i s S C+Sp
Heue, Sp 0
Sp
9 C+0

Example. 2
SuUm 0
or i 1 n

Sum Sum + ali]

The Spate reqviroment othis Statennent is
1 unit Space eqvired for Sum
1 vnit Spate rvired
1 unit Space required o n
n vnitSpd ce reqvied r an1
Thus, th total space reqvie dd is Cn3)
3 = Cn+3)
 elAsSMAte
Date
Page 3
AimanAnsari 272
*ASymptotio Notations

Asyneptotic AStraight Iineclosely atpreaches

but nereu me by a C ve

Three asyntptolic notalions OMe uoeol 7o find

he ime Complexi by.
iOmego Natatien (2)
i i Thea Noteution (o)
ii Biq-OhNotaliom ( o )

iOmeqa Notatcn (): CBeot case Analysis)

giveo theminimum amoun oy time
an algorithm neeola to u n .
Let
Fln) and 9ln) be two non-
neqain
tundions.
no and c _be wo
jntegeLA Svch hoct
no £ n and C>0.
Then
Fn)2 c
9 Cn) for cau n2 no

Heue, Fn)is denote a C gCh))

The C Mwe netation is
Tn)

Fn)

Cagn)

Mo
 elASSMAte
Date
Page
Aiman Ansari 2722
i. ThetaNotedicrn (o) (Aveaga Case Analysin)
J giA the areuage amovnt a ime an
algorithmn neeods.
Let
FCn) and 9(n)_be twonon-negatie functions
C and cz aue wo postrvne constrcdints,
Svch that
C 9n) 5 Fn) s Cz 9(n)
Heue, Fn) solenoted os oCgh))
The cuve for nortalon is
Tn)
Cgln)
Fn)
C n

n
no
 classmate
Date
Page
Aiman AnNari 272
i. Biq-Oh Notation (0) (werst Case gnalys)
qired he niaximunm Omovntoyie an
algorithn necels
Heue,
h) C 9(n)

Heue, Fln) Isdenoteol as olgtn2)

The CLMV for Big -Oh noteution
on_i's
Tn)
C qln)

Fn)

n
hs

While analyoing an algorithm, nly worst

Caseis Consideued.
The weret Ce onalysis9venuntees that
the algoci'thm willlnot Lake mern tinne
than the Calculateo One.

Rules o Biq Oh hatation

i Conutant eums Oe expresse.ol cus olL).
eMeuy extLutable Qtcutenuent wi take
Unit cuout o nle, c9orellus o he
Si 2e o heolouta i t pro ceAs es.
for Sone Conutnt C

OCc) oC1)
 lASSMALe
Date
Page 6
Aiman Anan 272
a at5
stalement reguins 2 time unit.
This
One fur additon onol Secono for
s siqnMent je ol2 ol2) = OC1)
i.Multiplicativ Constants 0re OMi tteol.
each ask nnsIn tinue TOn)= n, thn
4 tasks will run in O(4), which
Sinnplie to Oln) ie. olc n)-c.0[n)
oln)
ii. Addtien s perfermeol by -oaking Meadume
Maximum. e4:If 7 (n): n Om ol
Tn) onc two n
tasks to be executed seqventialy,then
he vebult is O(n)+oo')
on)
ie. olT): o(1) olT +T)
max fof)s ofr.)]
iv. Multiplicoction is use d when one task
Couuse Cnothon task tu b e exeoiuted
Some numbers otimes for cach
cach
iegrotion fitsel. e nedeol_loep
om).ofn) lmn)
 elasSMAte
Data
Page
Aiman Anur 272

Exanmpleo
main C)
int a2
vnits
2 uniEs
1 adodiHon
1 a s sig nament

ot)to(2) of1t2)
ol2)
ol1)
main C)
int_i, n, aj
n 5
O 10
r i O; ien itt)l
tt

Time take The progrona

n 5 execued once j:e 2unit
i exe cute c
on e 1vnit
J<n executed (ntl) time
(n times when the conditian
tnue onol 2 inne when
the conditon is olse )
iv. exe teel h times in 2n unib
V. tt exe cuteel n mes in 2n unibs

Totod ime taken by the program.

1 + 1 + ( n a1) +n 22nn
F
o (4n) ol3)
On)
 claSSMAte
Date
Page
Ainan Ansari 272
main C)2
int j.n, aj

fer Cio ich_ itt)

fer lj: ojahjtt,
atEj

To tal ime taken by 7he prag ram

+o+ 1) + n +n+ 1)+ht 2n
a>lo lvop (for) 2nd loup (tor) att
= 2n 4n t5
0l2n)+ 40 n) + o (5)
O(n) aln)+0(1)
o(n2) oln)
on)
Thu fuc single r laop hime complexily_is
always0n)arnd or nested for loept,
time Compexi isalrays Oln)
Thw,
ol1) Constent Hme
0 (n) time
Linem
0(n) qvaclrolic inne
0Ln) Cvbic me

o(log -) olalogn) -legarithm Hime.

 elassmALe
Date
Pege
Aiman An sori 272

Recuenceo
When an algorithm containsarecMrSire
Call,its running inne s_desCribe d
by a e Currence egvation on recurrence
Mathe moutical tools are useol 7p olve
hese e curences
i. Subsituition Method
i. Kecursion Tme Method
ii Maoteu Yethod.
j. Substiturion method:
The Solution s 9ves sed onol mathematica
incluctions vsed to prone that h e
esE9UASis Coe ct o incoreet
tranap le 1:
Recumence rlation: Ttn) TCn-1) +
InitialCondition Tlo)= o
Sal:
na1, then Il1) -[1-1) + 1
T(O) +1
O 1

n:2,hen T) =7(2-1) +12

T(1)+2 n Tn)
1 1+22
3 2 3
h 3,-Hhen T (3) T (3-1) t 3 6
T(2) + 3 So on
3+ 3
6 T(n)n (nt1)
2
 elAsSMALe
Date.
Page 10

Aiman Antari 272

Enampe 2:
Recurrence relatten T(n) = T (n -1) t1
Initialconolitions T(o) 0

n- then T() rl-1) 1

T lo)+1
1

h 2 , then Il) T(2-1) 1

T(1) 1
1+1
2

n-3, hen T(3)=T(3-1) +1

T(2) +1
2+ 1
1hvs
Tn) h T
o (n)
2 2
3 3

i. Subrtitution method 80 on.

We odrouw arecursion ree_ancl calculate
the ime taken
by eveuy
lerel of
the tree
inay, weSvn the work done
all he lerels.
l o drauw he recursion r e , w e start om
m
the gln rncurena relation anol kap
olrauin4 lwe find a patteun among
olrawo levels Thispatteun tpically
a authmelic
On geometric Seuieo
 elassmAte
Date
Page

Aiman Ansari 972

Example 1:
Kecurence relaton: Tn): 27 (h/2) +n
So
n h

(n/2 n/2 2nh=n

(n/4) (n/4) (n /4):: 4*nla n

n/8 (n/8) nl8 n/a hl8) (n/8 n l8) (nl8)8n/8=n

Thedepth a he ree islog n

Hence,he to tal cosSt nlo9
Example2 Tln)
onlo9n)
Tln/3) + 7m/a)+n
S

n/3 n 13 h/34 2n/3n

b/ (2n/9 (2n 1) 4n 19 9n/n

hl27 2.,/222/2 Anl27) n274np) An/27 (8n/27
27n/27=n

he olepth o t h e tree is Joq n

Hen ce, toteu_Cost n lo9 n
on logn)
 ASSMALe
Date
Page 12
Aiman Angari 272
Cxample3: To). 3I(n/a,) tn.
Sol"
n
n/4) n/a) n/a)

bMs/1616

T[h) nt 3h/4)+ aln/16)+

n
t
3 nt3n/4 qn/16 +
n 1 +3/4 t9/16+ f
o (n)
Example4 Tn)» 27 (n /2) + n

n 2) n /2)

n14) a)) na)

1)Co/8
Tn)n?2(nl2) (n4)+
n 2 n / 4 + 4n /16
h2 1+ 2/4 4//6
n 1+ 2 + 1/4+
 lAsSMAte
Date
Page 53
Aiman Anyari 272
Cxample 5:
T()3r(n/a) + cn
So1"

Cnia) na) a)

6A)otn)'(otn
rn)h' 3/n/) +9(nlue)*
n' 3n'/4 + n'/16 p
n 1 t 3/4t 2/16_t
oln)
 elASSMAte
Date
Page-
Aiman Ansari 272

ii Masteu MMethod
to get he
I t s a direot way
Souttcn.
Mau method Lwarts Gnyorthe
ruMHendLA
ellow ing tpes
Tln) a (nlb)i FCn)
wheue a Sonstant a n da z
n zd and d i s Same constant
FCn) must be positie

T(n) QT (n/b) +Elh)

ase 1 I Fn)is nwhere d20 hen

i a < ,To) =e(n)
b ia Tb) e(n logn2
C abTO) =_o(n'y)
Car 2 EC) s 'b then
T(n) (n'gb)

Cae 3 f Fln) is (n log n)

To
n)
 clASSMAe
Date
Page IS

Aiman Ansari 272

Excanaplel: Tn) 4T(nt2) tn
wWe han, Tln) al ln /b)+F(n)
Heue a:4, b 2 Ond ECn)n lase 1)
e n ,hente d:1
Now, 2 2
Thvs,a b /Case 1C]
Tn)
OCleg)

Example 2: T(n) = 2T (n/2) +_ blogn

Sal :
T (n) aT(nlb) F (n)
Heue
Heue, a 2 b 2 an FCo)nlogh lase3
T(h) nlosyb log n
Alow, og b log2
lokt lo 141
2

.T(n) lg2 nloq*k+l

e (n log
O n lo9 h)
nample 3 : Tn) 4T(n/2) tn2
Sol
Th)a7T(n/)+ Fh)
Heut, a 4, b9 and Pn) -n?lCase 11
ied-2
Nou),_b 2
Hene a :b
T(a) o (n log n)
Tlase 1b7
e n lon)
 AsSMAte
Dofe
Page16

Aiman Ansari 272

Example1 Tn)2T (n/2) tn
SoP:
Tn)a 7(n/b) tFn)
Heae oa= 2 b:2 anol Fn)=n
ie d=3
flaoe 1]
Now, b =22
Heue a<b llase 1a ]
TCn) b')
= eln)

Example5 TCn) 2 T (n/2) t n

So)"
Tn) aT (nlb)tFln)
Heue a 2", b-2 and F(n) =n°
ie d n
a and bd shod be Canstant
Hence, maoto methOd is not
pplico be.

Example 6 : Tn) 2T (n/a) tn°

Sol"
Heue, a 2 b :a n d d 0:SL Case
Now, b 2 03
a<b
Case 1a]
Ia) Cnrd)
 Pge 7

iman Anori 272

Example 7: Tn) 0-5 T(n 12) t 1/
1/n
Soth
Hene, a 05, b : 2 and F Cn) / n
Sin ce
Since, as1 , ma0tM Metho d not
applicable.
Example &TCo)- 9r (n3) »'logn
Sal"
Hewe, a:9, b 3 and Eln) : 'bgnlase3]
TCn)= =o(nagb lagki l_n)
loq log3
tth
lag
TCn) (n log
Eomple : Tn)64T(n (8)-h'logh
Sol:
Hee, a: 64, b :8 and Fln).-h2 logn
Maste method is not appliceble sine FCn)
is negati n

Example 10: TCn 2T (n /2) tn

Sal":
Heue, a z 2 , b : 2 ano Cn) . h [Case 1
): d 1

Alow, b 2 2
hus a b TCase 1b]
T(h) ( loq n)
(nlogn)
 18
Airnon Ansari 272
Selectton sort
Sort,the. Ourroluy interpre tel
interpre ted
In
In selecttor
as diriclec into two ports
Sorbeopart
Unsocteol pdct
Initi oully,
The socBeol part sempty.
The
The vhrorted partsThe entire amy
neyey pass itemation) the clteat
elemen1 S FovholOut (selec ked) and
i t is Swappea with the etmost
elemenb
Examp le 70 30 2 05 0 60 10 A0
Initially
Enply 70 30 20 50 6 0 1 0 A0

Sorteol Uhsorteol

10 70 30 2050 60 0

Sortecl un Sorted

10 20 70 30 $0 6 0 40

Soc ted
Unsor led
10 2030 70 S0 60 40
Sorteo
Un.Sorbed
 ciassMAte

Aiman Ansari 272

10 20 30 0 70 50 60

Sorteol
Unsor ted
0 20 30 40 50 70 6bo

Sorteo Unsorted
O 20 30 40 5O 60 7O

Sorteol Unsorteol
20 30 40 50 60 70 Sorteol
arrouy
Analysis ofSele ction Soct
Heue, or Selecting he Smalleotelement
homthe Uhs arted parz equines
SCanhing oll he 'n elements
. ie (n-1)COmparisdns

Findin9 the next Shmallest e

elemeht requires (h-2) CO p.arisons
Ond So an
Thus,
Number Comparcons(h-)+
+[n-2) +.2 +1
nln-1) /2
oln)
Thus, he Complexitiy Selectton SOrt
is o(n)

Worst BeJt cnd Areuage Case

 Paoe20
Aiman Ansari 272
Insertion Sort
Sort the array is
In insertlon
as if isolividel
ioterpreteol
into two parts
Sorted porE
Unsortecl part
Initialy, part S emptiy
heSorteol
Unsorted port s 7he_entie
he
Orrou4
ln iosertion Sort, he ee ments
are inserted at Their proper plare,
hence The name Insertion Sort
ereuypuSsPcLSs (ituatian) on
element rom he hSarte.d port
SinSemteol in h e Sortcd port
appropricute place
Example: 30 70 20 50 40 10 60

Initially 30 7 0 20 S0 40 10 60
Enopty
Sorted vneorteo

30 70 20 50 40 10 60
Sor teol unsarteol

30 70 20 50 40 60
10
SorEeel on
8ortte
 elas5MAte.
Date
Page
Ariman Angari 272
20 30 70 9O 50 60

Sor teod Unsorteol

20 30 50 70 0 10 60

Sorted unsorteol

20 30 0 5O 70 O 60
Sor ted unsorte ol

O 20 30 40 So 70 60

9orted unsoreol

10 20 30 10 50 60 70 sarte c
orra1
 alAsshA
Dete
Pege 22
Aiman Ansari 272
Analysls ayinseytio 90rt:

worst case, inserting he eleme

at it's PropeM place will olo
oll n eehn enZs.
Scanning
- 1 )n-1) Comparisons
Findin9 the hext 9mallea 2 element
reqvins In-2) CompaLisOnSancd
SO On
Thus,
Numbe ocompalisons
(n-1) +2-2)t+2+1
hln-1)/2
0lb+)
This s the LwarS Case ond
Oveucge Case Complex

Bes Cose
When he aMucuy s alueady Sored
In ereuy pais(itation), Single
Compouisans S hmoode.
Hence, the to tal humbey a
lompoujsons OMe n
Thus, the tamplexil in beot Cae
s0/n)
 elassmae
Dake
Bege 23
Aiman Ansor 272
Complexit class
oC) Constan ime
O(n) Lineartime
atogn), on logn) etc Logarnthmic -ie
o(n) uadratic time
o(n) Polynamial ime
0(kh) Exponential time
O(nl) Factorial Hme

wheue,
k constant and
n s h e input sizee

P, NP NP-Comple te NPHard Prablems

NP-Had Hordeat
P
NP-Complete Hard Medivnm NP
Hard NP--
Cornplete
NP Medium
P
Hardeat NP-
Hard
taay
 acsmate
pote94.
Fege2
Aiman Ansari 272
*|P Class of Problemc
P-Polynomioud ie Solving
s Se Problenos that
Qun be 9olve o in polynomic
time
P proble m take 1inne hke O(b),
0ln). 0(n)
Exaople: inding marimum clement
in onOrray or to check.whetber
aSting s palindrame Or not
NP Class a Problemd
NP
Non-deer ministic fblynomial tinme
It
Saluing
ic a et_opcoblemA t h a t cant
be Saveel Palynonmial time
Example Sum o Svlbset Given0
Set umbeuS, do eo tbeue exis|
Subset whose SumszeMo 2
NP pabems
NP
OMe cbeckable in
palynamial ime
ie.given a Solutton
we Can Check
o_aprablena,
thot whetheu the
Solut io S COrre.ct on not i
palynomial ime
 efasSMAte
( Dole
925S

Aimon nsari 272

NP- Hard and NP- (omp lere Proble ms :
Re olucbili
7oke two
wo problemg AOnol B. Both Or
NP prsblem
we Can Convert One ins ance
Q problem A )otopre bem B, he
Emeans hat A iseducible to
to BB
NP- Hard: If _we fovnol hatA is
reolucible o B hen i2_meanA hat
Bis ctleas as harol a20 A
NP Complete: 7he grovp a prObehoS
which a both Jn NP anol NP-hard
ar known a NP-Conmplete probbm
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
 classmat
Date
Pege26
Module 2: Divide 1 Conever Approa ch
n this approach, the problem sdiride l
jnto SmolleP4
ea ch
Sub-prablems and then
Sub-problem is solve d indeperde ntly.
The Solution of
inally merqeol allsubproblems S
to abtain The olutiun
of the Origina peb lem.

a b e problemn
Divide a b C e
Svbproblem
A
Conqier D E
svbsoluton

a b e 9olutlon

Divide This step breaks he problem into

3maller Sub-problerns.
angver: hisStep Solvesa lot of Smaler
Subproblems , #0 get Sub-Solution

Merge This step recursi vely Combinea au

Hhe
the gub-Soluian to ger
get
inodSolui'on.

DSE2O- Aiman Ansari

 elsssate
( Pege
27
Airan Anar DSE20 (272)

Merge Sort divide ond conquer

Merge ort vses

gtrategyy
Consists ot 3Seps
Divide4 hearrayinto
Divide Sub-arrouys 2 elermen ts
with_ 2elernents

the Sub-arrou
two
ii) Congver: Sort two sub-aro
in)Combine:Merge the orteol Orouy
into a Sinqle
Example
L18 2 o Is12 a I S 6
Divide
pi LBl 2 ol15
Divide IS 6
pass2 18
Dividle
poss3

Divide
pogs 4

Nupe
pat 5 9 12 6I5
Merg
purd6 6 912 Is
Mrge
paus 7
o 211is1 6912s
Nerge
ps& LO216 112 1S 51
Numbe0pa n-1
 efasata

2
Aiman Anrori 272

Algor1thm for he merge Sort

A1n]is the arrauy to be Sarted
Mergesort C) sthe onctionsorwhich
te
IS
e-ettene recursiveuy Caleokto
to
divide he
array
CombineC) isthe-funcHonn
Sartsand then m egea h ewhichb
diridec
array
meygeSort (AJ1n low, high)
if Clow high)
mid Clow 1hiqh) /2
meugeSort (A, low, high)
meuge Sort (A, mid 1, high)
meuge Sort (A, low, high)j
3
Analysis 0f mexge Sort
Let T(n) be the ime required by nmerge Sort
to Soct
n_elero en
Then TCn) 2T (n/2)+ n
Now, Veing Mast Methoc
we h a e Tn) aT (/b))+F (n)
a 2, b 2 and FCn) nwheue d 1.Case1|
b 2 2
..
L Case 1b1

Thu, T(n) o (n"loqo)

0nlogn) )
 cfASSMAte
Dote
Page29
Aiman Antari 272

Combine (Al1.n]
n],low, mld, high)
k i lawj
midt1
while Lis:mid &d jsehigh){
ifALI] <e AljI)
temp lk] Alil
+t

J else
temp Lk] ALjl
k 4t

while Cir mid)

tempLk] : Alil
k+

while (j< mhigh) {

tomp [k] ALjl
ktt)

tor k : louw k<= high k t )

A LrJ = tenap lr];
 elassMAte
Dote
Page 30
Aiman Prngari 272
Quick Sort
Quick Sort vseo olivide canqve
Strate99
Quick Cort Cons)s 1s of thepe Seps
Divide Diride he arrouy into 2 sub-
array Svch hat each element
in hhe eft sub-arnoy is
lessthan or
cgua to the
middlle element Cncl ea ch
element in the rlght Sub-
arrouyis9reatou han The
mldodle elemert Th/s
oivisian is based On pirat
eAement
i)Conqve hecurssively Sor the 2
Sub-auay
ii)Combine Lonbineoau theorteol
Svb-ar ra into a Single
arroy Sorteolelements.
In meuge art, he aivisian is based
On t h e pociions of elements
arrouuy
wheueas in qvick Soct, the division
bosed on actvo value of he
element.
 cassmate
Date
Page31

Aiman Anari 212

Algurithnm or Quick Sort

last)
quickort_(Alz..n], hrst,
Cirst<lost)i

pivot first
first
last
while (isj)f
while(Ai]<:AlpiratJLk i s las)
it J
while (AljjèAlprvet]k4 j2irst) f
if
tennp Alil
Ali) Ajl
Aljl temp
3
temp Alpivat 1
Alpivot Aljl;
Al] temp
qvick Sort A, Arst, ji-1)i
gvick Sort (A, JA1, last)j
 alssmate
Date
Puge 32
Aiman Rnaari 272
Pnalysis of Quick Sort
Yorst Case
hlost Case OCCure when the key
elements 9e placed CAt One end
and he O oy Size is (n-1-1parr
In 2 pass, h e key 9ets plarel
one end and Si2e
(n-2) remainA, andSo on
Hence, 7he to tal numbeu
CompauiSion s to Sort he Cumple te

(n-1+ (h-2) 2 1
nin-V2
0:5n - 0:5n
0 Sn
Oln)

Best Cale
he array 1s aluway Partiioned
ot he mid h e n h e olgorithm
gires the beat Cose effeciency
LDeuivotlan ic Sanme as thad o meuge Jort

Thus, he comple.xiy02vick Sort is

Beat Case o ln logn)

Aveage Case O
Onlog)
C n n

Worst Case
 elassmate
Date
Pege33
Aiman Ar3ari 272
Examp le:51,26, 93, 17, 77, 31, 44, S5, 20

54 26 93 1772 31 94 S5 2 0
pivet

54 26 93 77 31 49 55 20

pivot
ikj, s wop Ali] ond Alj1
54 26 20 17 77 31 44 55 2e-93
piro
ij Swop A[i and Aljl
S4 26 20 17 4 4 31 77 55 293
pivot
54 26 20 17 44 31 77 55 3
plret
ikj wop ALj] and pivet
31 26 20 17 44 59 77 S5 93
pirat pivel

31 26 20 17 44 54 72 93
pivvt
plvat Swap Aly] Alpm
SwopIlj] and Alpivet)
 ASSMALe
Date
Pge
Poge 341
Aiman Ansari 272
17
pircd
26 20 31 44 511557792
17 26 20 3194 54 55 77 93
pivet
J
SwapAljland Alpiret
17 26 20 31 44 64 55 77 93
piret
Swap Alj]and Alpiret
17 20 26 31 44 5 4 55 77 93
 elasSMALe
Date
Page 35S
Ainan Antaui 272
Univeusity Queation
P L,E
E, X A, M,
A M P L E
pivot
ijSwopAli)_ond Aljl
P L
E E A
pivet
X
E E M P
pivat
ij Swaplj] and Alpivet]

E E M P
pivet pvot

A E E Pivet P X
pivet
pivet
SwapAlpiret and alj] Swapiand Alil
A E P
pivet
Swap Alpivel and Aljl
A E L M
pivot
A E E L M P
pivrt

Sup Alplvot]_ond Al
AE E L M P X
 elASSMAte
Date
Poge 36

Pinding minimunm imanAnsuri272

Onol moarimumi
min and max
valuea from an
armoy Can be founod
Using-
mar main (A (n), m ar, min)
L
max min A [O]
for (i 1
to n i
if ACi) > mar)
ma Alil
i

ALi] < min) }

min A i]
J
Nomber of cumpauisons = 2 (n-1)
This min Qnd max voue can be fovnol
vsing recuSive method.
The e cuSive methocl vses divide
and ConqueL Strategy
The numbe o Compaulsicns heue
3 /2- 1
he list o elements i divideol out
the mlcddle to 9er two Sub -arrouy8
trom his Sub-qray m a xim unm and
minimum elemenk oe S ele cred.
This proress S Carried out foc h e
entir arroy
 elasSMAte
Date
Page 37
Aiman Anori 272

Algori thm
maxmin li,J
ili:j)
mar min:AlIJ

Jelse
i
i lAi] A lj])
max AGI
min A ( i J
else
mar Alil
min Alj
3else i
mid (itj) 2
maxmin imia) /cc
new h20x m a x
new n in min
moaxmin (midt 1,jj
ifmax newmar){
mor = newmax
Jif min newmin)
min newmin
 elassmate
Date
Page 383

Aiman Ansari 272

oExample
20 10-4-21s50 45 Is 40
20L1o1l-zlis 50 151540
2010- -81s 50S 1s0
may:S mar: 550 max 46
Eelrol min s 8 min: 4S min / 5

max 20 max -
m i n : I0
min:-1 max 50
min IS
n o r 20

m i n : -4

mox 20
min - 6

mar 50
min -8

Analysis
For each half divided svb-arrmy, theue are
two reCursiveCalls ma de.
Hence, time required r conoprting
T[n) 27 n/2) 2c to Combine
2 0n/2) 2 olc)
o (n/2) o (c)
o (n/2)
=On)
Thua,
Thud he ime Complexity 1S O(n).
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
 Date
Page 39
AimanAnsari 272
o Binary Search

The elemeniS in the array should_be

in SOrtcol orcleu
The elemer _be Searched is ooled
he KEY e men
Let A Lm] b e he midolle elemeni
ua4- A
key=_Alm], then h e dedinedelenment
key
spreaent_in h e Cirroy-
1 key <_AlM), then s e c r c h The le-t
Subarr
key > Alm] then searCh the right
Subarrog
Duringthe Search CuLOLy ls cliricdeo
into two parbs hence he name binany-
8Carch
Example
11 33 37 2 45 9 100

Let the elemen to be searcheol

Find the midde elemen in he array

ancd CompauAe it with 99

11 3337 42 4S 29 100

lesubauu Middle right SVb -Qwua

element
 elASSMAte
Date
Page 4o
Aiman Ansari- 272
Since 97 z42, the righ Svb-auy iS
searche d.
45 IO0

middle eleme Elemcn founa)

Anclysis 0 Binouy Search
binauyeareh(alLw], element)
irstO
last n-1
whiletirsb <= last) i
mid(tirst + las?)/z
i elemen a[mid1)
break
else i element almid))
break
eAse
irst midt1

i irst last)
Print ( Elemeni nav tound")
else
print(Element -found)
 IASSMALe
Date
Page 41
Aiman Ansari -272

Analysrs o Binary Search

Bes Case
The
The element to be SearcheelISpreent preentt
in middle pocisio0 ThuA, it is
tound in irst Search
h e searching ime 1S
Hence
indepen dent cf henumber o

elemens in he CArro

Worst Case
The elerment to be senrcheel is
i nt h e array
eitheua no PyebenL
Or ib is presenL et the enc
op the CUMo when Cnly on
elemeNt remains
For example, isize o he Carrouy
is 256 hen he Searching
Cohtinues with redluue ed `ze o

256 128 6 32 16 8 2 1
6

. Nurmbe osearched
J09, 256

thud n wors Caoe no. oSearche

i ollogn)
 elassMAte
Date
Page 42 C
Aiman Ansari- 272
AveMage Case:
On nunmbeu of searcheo LS
=

2logn
o(logn)
Camplexitieo O al divide and Conqueu
algarithms:

Algonthm Bebt (au0e Avq Case Worstare

MeryeSer1 O(nlogn) Olnlogn) Dnogn)

GuickSar Ofn logn) Onlogn) Oln)
Min Nax Alg Oln) Oln) olD)
BinarrSearch o(1) oflogn) O(logn)
 ASSMALe
Date
Page 43

Method Approach Ainan 272

Macdule Medy
3:
eneucl Method
Geecdy methols aue uoed-Jor obtaining
optiized Solutions.
the beat
An optimizedSotchiorn is
Svluction
Aqrecdy algorithrm a0
he hame
SVggests, always makes the Choicehat
Seem& o be h e besb al that
mamcni
Urtedy methoodperformA he ollowina
activihics
iSonne Soluian js Selkcted trom the
inpu domairn
ii. Theniischecked whetheu the
Solutian isfeasibk or no
ii. From the Sec feasible olutionA,
pauticukau Solution hadSactistieo
o he
neaulySotifiea Or neauly
Satistie he
objccties is ectisied
Sele cteo
Ln_oreecly methoc, we attempDt to
Constut CAn Opimal_Solllon in
Stageo.
At each gtage, we make CCicgrana-
deasion Th appear be
ho ime best at
A deis ian once made Cut Ohe tage S
not changed in a latey tage. So
each de iSion Should
oAS ure easibility
 elassM
Date.
Page
Airnan Ansani 272
Thus
At eCh Slep,
NexeM back track
a
beDt_choice is na de
choiceo
nor change the past
Neveu lookahead to
deeision wolol
SeeiCurrent
hare any hegati
impactio fucdur.
Single Source Shorteot path
(Dijkstra[ Algorithm)
geneuay a graph s Used to
represcs
the disance
between pwo Citeo.
lheSimple OurceShortcot Path s Used
to tind aPath from One city 7D
anctheu city qvickly
The ghortot distance trom a Single
atria vector callecl 7o
Source, all
he Otheu veuices is Obtained.
oblem stautement
iven a guaph and a Sowue veuter
in the gaph,indThe shorlest
pathsfrom hee
h SOLuCce Veute
to aU otheu Veutice in the given
guaph.
 SMALe
Date
Pege s
Aiman Ansari 272

Algorithmn
dijkstro lg, w, s) {
initializeSingle-Source (g,s)
9 v
while
U extract-in q)
S S uu

-tor each veutex v EG Adjfu

relax (u, V, w)

Analys is
Thetime Complexily a Dijkstra's
Alqonithmdependo on the wra how
he minimun priori 2Ueue S
wo
imple menteo y2
The Complexi is02) fur narmal
the priory qveue isimplementol
VSing binauy he ap then
heap he
Complexily s of log r)
 alASSMAte
Date
Page 46
Aiman Ansan 272
Example 1

2
2

Step1: A veuytex Step2: B veutex

z/A u/e
B

) 1/B

6/A
a)6/
Sep 3: E Veutex
2/4
1/8

A 4/B

Step 4 GVeuex
2/A 1/B

6/E
-

5
sle 10/
 Date
Page 47
Aiman Ansaui 272
Step 5: VeutexE
2/A

6
2

8/e
Sep 6 Veutex H
2/A 9/F
B
2
1/8 6/6
(D) 19/
5le
Step 7 VeutexC &/E
3/A 9/p

2 4/B 6/E
1o/H
2

8/F
Slep 8 : Veutex0
2/A

4/3 6/E
10/H

2
2
5/6
8/F
 elasSMALe
Date
Page 48
Aiman Ansari 272
Example2

2 70
6 10

Step1 Select Veutex A Step2: Veutx F

22/A 22/A

6 16/A
16/a
8/a 8/A 14/

Step 3: Veutcx G
22/A

22
16/A
16
(23/4
14/F

Stp 4: VeutexE
22/A 20/E

22

16 / J)23/G

8/A
 clASSMA
Page
Aiman AnsaMi 272
Veulex C
Step 5 20/E
22/A

76
23/G

8/P
14/F sirdt
Veutex B
Siep 6
22/A 20/6

22
23/4
AJl6
14/F

Step 7: Veutex D
22/A 20/6

23/4
z/a 14/E
 alAsSMAte

Date
Page SO
Aiman Ansari 272
example 4

Step1: VeuBer A Step2: Vertex D

7/p 1/D
B

s/p
Shp 3 Veutex E Step 4 Veutex B

7/D 1/D 7/D 9/B

B

3 3

3/A stb
7/0
Step 5 :Veu tex C /8

s/p
3/A
 Dote
poge SL
Aiman Andaui 272

Exarmple 4 2

9
Step 1: Veutx 2/a

Is/a

Step 2: Veuttx b
2/a

2/4a
Step 3: Veutex e
2/4
3
5 /5/b
12/a
Step 1: Veutex C
2/4
3
5 /5/b
6/a a) n/c
 elassMAte
Date
Page 52
fiman Ansari 272

Step 5 Veutex
2/4

5/6

6/a
119/c
 ASSMALe
Date
Poge 53

iman maaui 272

Example 5

6
9ep 1 Veutex0 Stcp 2 Yeuter 1
4lo 12/1
4/0

8/
8/0

Step 3: Veutx 7 Shp 3: Yeu tx 6

4/0 12/ 4/0 12/
2) 1 -2
IS/z

9/7

Step 45: Yertex 5

1/0 12/1

1S/7

1/6
 elassmate
Date
Page $4

Aiman Ansari 272

Step 6 Yeuter 2
12/1 19/2
-

21/5

9/7

9tp 7: Veutex8
4/0 1 19/2
- -
2s

SHep8 Yeutex 3
4/0 12/1 19/2
-
2

2 n/6
/7

Step 9 2/ 19/2
1/0

14/2 21/s
-
6
/7