(8-10) matks

-Ajinkya- Rane
28/4425

ALGORITHMS Date
Page.

to solve qiven oblem,

Apxioxi Analysisy : Betut ning he

+ t A o tAnelyai
#Apcsemom n t : Notneketkle
detemine the time of Alga
ander Anrio Anayswe e.

&tatent
to the
Count the undamcntal
Operhon the Statemsnt Istkp
ch apeation

fhe hais ohË ectve of Anxioi Analy.

Cabtain) the
Hme (mmpleihy
He algantthm by
mathematicol thneta urt Int size
fime Congtnt )s

xponsnta tunet

unetton hove. leser

 Date
Paga

The objctive is chvays to develop

Alyo' pr pzobla m havingpolsynmial
me compley LEcisnd
An
*An algn h is e7iient if it h
ti me

aast Cae i fhe flP clas toy cohich

Aleyo toukey Hme
Algo
)Best Case : he le cass faz ohiche
he Algo take,. min: time
ilp& B'c time.

Tme
Bn) AC ) w n )

Avq
= A n) = w() Sort
)Bn) Mexg
Seletíon SoYt
Hep Sort

2) 8cn <{An) = wla)iLinto Seamch.

Gincay learch
B(n)= coln) CluicieSart
 Poge

#Asymtotis Hotatíons !- (ASN)

ASN

tppebanl
ISna) 1tte poper
U.B
-Oh: (O) ’ He oh: o
oweY

poper

tght eound
be fnetionsam he
of inic ges to Reay numbe

Upper bound
fln) i her
Some Conetants and
such that

COheneuer i itisedeterilnei
L'B çwe should nd thet
tnetion. ushi ch closest
to givien nétton.
 Date
Page.

flo) is Acgla) i4t

&uch

fn)cgín) hencwer nzno

fheta (o): tgkt Bound':

Bcnd
fCn) is fn). is

& flo) is 2

Log kopetiesi BASIC3

egzy og2egy

2
agAoga

b
og
 Date
Page

the geDmettie Im omula tor init

given.
nta.
Conatcnt
Sp= 4(I-yn)
Ang dngn
(|-)
n.

Sn = arh-)
n
oheee
nk
(ommooatio 2n
nn
21

Commany LASe d sérielieelts

i 20

2(2n1) 2
2

giometic

So
 Date
Page.

Fominanee Relatton
<taco
oleyeain jange To Pele
Ja b9
< xponntiad

<n²<n3

n(n+1)
B) £)
2

A
n(04) en+) o(n3)

fCn) 2

2 ( 2n2l-2)o(20)
) fln)

S i 2 - (n) 2n +2
 Steing93 ApproRlmation:
n n (m Date
Page

9)f =

n
=|:2.3...n) =n= nl)n-)...

o(nlngn) Log n
#Sinalllitle notatHons
the bousd avid od by Bg
may
not be igkt
the bounds peovicled by s al)
not atony
Asymptghcaly aliay
hgktLobse
NOT.
bound.
5T

Smalloh (a) popex Oppe Rond

2oheie\eY (nono)

gor al'c'
 Date
Page.

d mall mega co): fpe Lawex Bound

aheneey (nn)

Paspecej ot Asyoiptotic Notet'or

I Analey blo Ria) o!s &ASN:
Let b real
inctong

is qsb
2

ab

Gnencxa Popeches ok Big-ob -(o)

g: dCn) is ol£(n)o any congtont

2: it dco) is of( ) and etn) is o(gln

then

and e Cn) is oCgln))

+hen d e ( n ) is ofgln)
 Date
Page.

4 Ik dis ofth and flo) is

thon dn) is oCa Cn) (tansitive)
5 palynomtal
d (Hhut is fn)= ta,n+
hon 0 Cod).

on)_tor x>o& y>0.

TIT Dìrerccte Poopeheo As:
As

|ReftexieV
KIk X

Synmee X X WX X

rtans
ive
is og X
Symmehthun goiseofy

IV: fi Cotorny Poropexty

to

gunca
 Data
Page

NOTE AsNASF' doey not sohity tticotoy

opexty

GArE
2022

ohich f the ollouo' ngtun is fRUE

Lon) = o (ca)2) cohen f (n)s
poynoml a.

( fn)

(c) Fn3) - 0 (L)uohen ftn) is an. expo.

let n be a
pot

goegn

(Aog)
g ) is oPn).
 Date
Poge,

faxing
Ang
2n. -

-Aeg n
2
2

=0
e) Fn) =

Takingng
Ang (L)
2
 Date
Page

Let co(o) and A(n) Te geipeetiy

the
algoithn
Input Sine ot hj ohich is

a)

An) =
kno

FALSE
then
A(6) co(cocn)

Ttme Complexihy Egameaoxk o

RecusiveL Algashmsi
Saluine Rezuencis

1) 8ack. 2) Mas ter 3) Recusion

metlod Tree
<uniUs Ksuortut
method
Repeated
Sbstittion.
 Date
Poge.

retunDo

TO)= 27(n-1) td d eatbl

Tn) - 2(n) td -0.

t(o-)=21cn2)+ d-2

22T(n-2)+d d.

-g2.7l n-2)+ (22-)

23:7(n-z)+(2'-) d.

[Link]-k+ (25-1) d.
k=n-1
 Data
Puge

= 2 n - c + 2h-.d-d

Tln) e2?-d

(2°)
(2 Exgonental
GATE

Algoithm

atunCAn;

= 0t

ta

ta

+ q fa
Tín)+ 2a
T +24

T2)+ K-a
(ne 2 6 (n=2 given )
og Jogi tAogn1 Oate
fage

Tlo)=2 n=2
=nT(O(o

+n

To=n
2 i91o99+n2 +n.

314-n+2n
TD) = n

+ 3n

+ k-n

2.

To) - 0(ntog lagn

 Data
Page.

#Loop Compleihexs

Qfoz i -1 ton

) B)
b) fo < 1to9)2

cohile CK<=n)

: n g n t oln) + o(n))
Pes it os ii'

fota time = n* Ling22n2

n
-nlngn

Q0forielto n 6n)

for ( 4 t o n.
for /t to nl2nl2
2

for / i to n.
on
for K 1 to n,
break
 Date
Page.

(4) for (i=l; <=n +ti)

for (=l;j<=0 ++j) n
for (ken|2; k<=0 kt=nl2) 2.

oktle(ic=n
let n6.

x2 ix2 2'x2,2k
=2=n.
K do4
Time

LLhile i>o)
i-il2;
Sama

oAng)
for( i=l; i<=n i=ita)
Date

lo op uitl nepeat tor nla Page

fo7 (i=l; iK=ni ++i) n)

for Ci=L; isn; tti) yo)

for
C=c+|

fime. ndo
ing 2
fime

O(n)* oco)
 Date
Page

GiATE
int fun (int o)

lntiff-4=
o7 (isl;iken; t+i) in
Totat

fax Ci= nij>i- jl2)

adleg for (kl; K<ejk= kt2) leg

fhe walue
he qntian

fime compleiy

#SPACEICOmPLEXITY: (rbri menoy af

(Cntst Addihbnal Spae,
is SeACE CompLEXITY

Tn) is time com

cemplescty and
pacece comple'ty
thon 6(n)oT(0)
 Date
Page.

+LDESTGAN 6TRATEIES -

OOivde &Conques (D&c)

Said to be
ganexal
iç it be AolVed in one
basc opexaion

Person lized ftme Compleihy i

CASE-T
b>1

si2e ot

to symnettic size ony

CASE-TT T(n) I(an)+I(-a)n) +go)

CASETIL

¢oY symnetic ize

nl 2

Tnl4 n4
 -b o(n)
Tme lonplenity -t
-so(ogn) Date
Space Comptenity Page

Max-Miy : Protedwee to ind mDe

Min Csimutaneowaly

Agpsi Non -Dc CA,n,max,min)

2:foT t 2 tO n

fAlil;
ee
itAli] < min
min ATi1:

() Best Cae (n-)

decseasing ovdez i2cn~)
C) Avexagg cae an aug 'ist:(o-) +a
[Link] son tailiftf-e 3n
Eloma Co) 2.

D'vide an maa min

Take an
2 3 4 5
A -615 |20 33 649
 Date
Paga

'/9,fmox,fmin
64 3

1,5,9mom amin 6,9,fmomfmin

13(12, o)T455,-9 6a243)| ,9,64,3)

A
D'&C T
242,9B.3,(o)

* PexkoIm anse ok D&c- max min

No ot elnen conpaisons in D&c

3n -2
2

Non -DC

gn -2
2
bettex

2) Decea Orclox 2(n-i) 3n -2

betr
3n 3n -2
3) Avq Random
2 2

bette
 Time Compkenity oogn).
lomplexty o(logn) Date
4 Bpaue Page.

Btnaxy Seaxch The pximey

is that the list ok n- elenets mt
be in

I | 2 3 4) 6
R.
mìde-|b
Key=

height |h-olioga
Comolet | Fuu 8-T.

#Mexq Sort: CConquex oce4)

Given too SoTtediss Licnd Leln2)

whesee n n2 quittd
meg hen ?ntoa Single
Sorte d hav'ng (nitn2 elements
mexging s 6.
12> La: <9)4)1115;18;252.

Li<34,5, 7,- . (5,1 &, 252

He
 Metge Sort Time Complexty - . (ngn)
Space comp lenity 0(D Date
Page

Given tuo &0Jed Sk Llo) &Le (^2)

the min:& man: Compaxisoy

needed to tthem to get

4inglesorted ist C n+02) is

Minimuo: |Ll <Gst l L2l

min: comps:LniIKn2]

mamim

max:
Comps: (ni-) +n2

T: Aeauitd to
Meg
& L2 (n2) ie blw

i s n ) &Ca,n2-)
4
min. mat.

olnt2)

) fime Cample rity

het tín) e fime compleety
DCndC-ms (0

2-1(o2)thnnbo
Tmao o(ndogn), degn) ie: s(og).
 Date
Page.

A T(n).

Line) n]2) Le
T(O2) T(n}2,

mexn BestCale

n-)
Bottom Op mexge Son

)79 254 . 285310 351 4 23652 861|

149 285 310 652] J254 351 423 861]

PASS-) T285 8]o ] 19652] 35| 4257 254 86n

C310] 285] [ 1 ] T6s2]I3510[423] [ 861 T254]

n=2k

Time ampleety ogn

 Time Complenity -t g-c olnsogn)
Dats
Space Comp leaity t B-c-ongoO

# Quick Satt Paxition - Exchongg sottli

BaLsecl onPivot nsocea

Paxttionug pxncegsi Ldiviee]l

2 6

A65 10 45 85 60 55 50 45:

piuot (6o 55 S0 45) 6) ( 40 15 go S5).

elemert

Pertormante

o fime omplesy
an.
paxttian; o (n)

o(n2)
T)-o(nLogn
8EST CASE WoRST CASE

NoTE OS hehauiowke elomets

Sete ol Odolo.
 Dote
Page.

Quck sost Suppase the

ing
(entta element
i chersen he Pivot
than the compleity
may be
+he Qick

fhe meolicn
Can be tound 'oo) 6me.
median is Selected Pivot,
han +he Cae complexity ot
Soyt is o(nog n)

TlO)= o() + oln)+ 2T(n2)

me

fn appling, Qick Sort to an (oted.

(ol4) the eloment
Selected. iot ther t e Tim.
Comp le ity
 Date
Page

+MateÌx Matiplicaion
A*8= time complerihy locn3)

Ttme cornplexity ug DOndC mehod

n mlhiplication of 2 mateiA is

-lo (n)

Tme complety of STRASSEN'S

iMATR|x MUTIPLcATLON |S

Space Camplexlty ngntn

oCn2)

Majtex fhinnem Cmethod)oy Solving

and

4+Ve

or some
E>athen T(n) is
 Date
Page

CASE-I gn) is oCn,Auga) to7 âoSome

Such that
ktl
) K)o thes

CASE-TIT lk gn) is 2(ngsE)or Some Eo and

tazgome kthen
To) is o f l )

Hoo to_&olve

t(n =47(n2)t n
a= b =2 (n)=nn
4 = 2.

for CASE I !

is 9 (n2).

Ta)= 2T(nl2) tn ogn

(S-2)
 Data
Page.

Heee CASE 1is tcjected.

.for CASE-1

nloga
ndog'nl

tn.

b= 3 r(n)= n

Aog
Here ASE 1 is jecte d also CASE 2:

for cAsE-3:

af n|b) 6.(n)

S)a-9, bs3 n)= n2s

?22
og?
 Date
Page

CASE
n 2-s
is i+ oln2-e) x.
CASE-2 n2-5
G(n ogn)

CASE-3 is it

2-5

Tr): (n25)
JUSTPR oVING
mo-min
t2

-a= 2 b2 fn)= C.

CA3E

:.Ttn) isoo)

Tn)- 2-Tnl2)t 0.

CA3E-|:n is i+

CABE-2 Kn)
 Datx

for Matir Multi plication

CASE-)

b) stossen's iTo) - 1 (nl:) +n?

CASE-1: n2 isi o2t1-)jG:02

for Linay seosh

CASE -2 : n),K=0

T(r) is e

atiplyng
0-digth eash.
 Date
Page,

)tbn.

AlgoatAm (Anataly Kaxadtsba)

Ak
T()= 3-Tln2) + bn.

GIATt

G1enAatised quaiong o time Aomplehe

Keuwau
) v i d e and Congu0N

Andal Kax atyub

ro) Ck):T(N})+ bn

3
To) (2K-1) I( n])+bn.
 Data
Page.

# GREEDY METH OD

Used qox dol ving xthlems whose

n
Kltion víewed
making 8Rt| sequence ot decis iong
fhose decisio in a

Step-usise manne
A+ each Step optios
Greediy seleet hat Oph'on ohich.
Satisie the qiven critei a
proslem.

Efouroinalog
Constt ai nts Cconditinna)
Req uitements
(Gounday
Solution Space All possibe ays of
o2ganizln inputs saisging ony
epiicit constaints

Feasible Soltions (came ct)

those SOtìoN he
Sal^ipase
costs cçnts O
hat sahigies impliit
the pmble m.
prohlemny may howe multip le
qcoible. solitions

Objeetixencion feu toblem

meut have abËecthye aohich tie to
mìnma a given. eiteon ot he.
pnblemn
 Date
Page,

Optma Salution is that teasible

Soln which satises he obiectire
Solunon:

Aluasge to and
hence

Rme cenaple xity at Gireedy MeHod.

ateayt QCn).

KNAPSA CK KNAP) Pblenm

Given KN'APSAck of Capaiy

hiven. obje ct

cweigkt Deision.
(ei)

nto he KNAP hen KNAP get iled.

p by the
pa't
Mezimí2e the fmtt Subjeet to
thei Condn hat the total
into the kNAP Does.
loein put
npaeit
 Date
Page.

KNAPSACK Prsbem.

Faactioad TBnay ol)

Rea < eithey incuce it
enntinous tot aLu 0T cude it)
Ronge
for Solvina the pnable hen.

Swi2M. Expi'cat

KNAP SACI definit

Max P: Xi 06jtunt

Subjectt +Implicat

ohere

Saution Spacee

Fracttonay
n
 Date
Poge.

find the opimal soltien to the

Inst ance
n=7 ME 15
knapsacks
CePa n.. Pa) = (o, 5, 1Ss, 2,6, 18,3)
(W, w2, w) =(2,3,S, t,1,4,).

P1:5 7
1:66-P2
6 6

M= 1S <1+2t 4t 5 +l+ 2

) Prot 55:33

2: 213

Job -sequancin oth De oLe line

Ji

Prot, PE
8T Deoatlie
Lunt
finiegea >o)
AT Aivalfime.
Bt Burst fime

completed uithin.
the deaa ne. +hen you get it
 Date
Page

size ot Sohon space :

Kdi, dsz= K2,3,4,2,4,32

<Pi, e = Kl418,12,l0, 8,)S)
JtJ6|T2 J3
2 3 4.

<dids K 2,1, 5, 1,2,3?

<PL,': P6 -<28, 12, 5, 83020>.

J3
2

<ey P7 E KTo, 85,12 l8, 5o, 6o,l0)

Js J6 Ji
2 3
265:
 Date
Page.

ophmal MeXae Patexnst Corderng

Parreuclon
Ghien set otles <h,En)
Eoeh ile contein Set of RCody
Sorted
I+ ii eguhtod to meg the given
niles to geta single fle ihin
Sovde d o o y
n=3
uing 2-coay megin
E <2,2,9,1S,12)
Re cod moement)

Fn:K23,S,,.i
Cntm)

f=5F2=20

Patkm ):
<L2,3>

F3 lota eeorel
movmet 35t4o
=75

Potem

Ts]
i,
<2,8,|>
[26 |5 Tortal
f2 F3 254 lyo
frovement
=65
 Date
Page.

# Ditkesent pattems have diktt

mo vements

\We have to Se lect thatpatteyo, that

genecte, minimLuro. Coptimcl.
Moements)

Soutior Space

# The moyenents =
coeigated 2xterna path length as
Bnany tree

root to Fifle)
am
die dist ance tom
Fta Lsize ot
(30
> 2+ lotlx15 2 5 45

5
A

# Tae caaplexity gngile

t depencd on. ist
inmplementa+^ og

eap trior-tfnea)
n'elements n'elemeots
-Insext
least:n Delote
Inyet: - doclInc
Key.
Total: o (dog)
 Date
Pgge.

Huttman coding :

KAn applicatian of apt mexae paten

CDetaGncoding t Data Comesion
fechni qu
elomenN
(Esneseting an eomer uith some code)

Data Compneaíon is neves _passible

eoith encoding
Compreaion is passible oith.
unigoo ancadiná
L= 2Ca,b, G,d,e). = <o23, O-o5, 648, O- 15,oo)

o48 (o52) a 1 o C2bits)

b’1lbo (4 bis)
623) 21
d’LC3 blts)
(014)

Cophmaj 2-ony tinay

T e t t <cc acccabdc.
Hman coding t o0lo O0ololloo||10
 Date
Page.

Minimum Costy Spanning free cmesT).3-

CGraph [Link])
for Adiacency i6t:
Size os Cnditected
cindected genph nt+2e)
Si2e of ditected aph ’Cnte).

ne
Time conplenity -tolne)
for undiecteel qaph -t le-a-)n
2. T
for dlsected paph
Gaaphs
Derse Spawse.
Graph. Saph
Kalmot Complete) <ot compete>
e o(n2) -’ Adi' list
on+e)
be Her)

ointe.

Sponning Treei A Suhnaph. T(V E) o¢

given gnph Gly,E)hexe e'CE
Tree is
REA.
apanning
 Date
Page

GATE Given garaph

then
havins
thea
hat mwt be the
Graph to get Spanning Thee
is e-nt|.

Tota edee
Spanning T sitth n yez hces oill
. have
ealg
Remod edge =e-(n-)
=e-nt}

oith n -/tice Coill have

Solution Spaei for jven paph with

he max

foeomaplete
graph (Kn).

AlgoithmA COnatottonOtmìntmuy

) Pohm-Jaxinik Algo
CH) koruUhkalls Algo
ti) Diesera's Alga
 Date
Page.

28

14

25 24 18 12

22

krLskals Algo
Kto, 12,i4,16.L8, 22, 24,252)
14 16

4 2. 16

22

Time Com: oCh2)

Time Comi

Poimmethod acy maintain

Step
Cozt o¢ Gpan aing
Span ning tee ith both.
be Same.
appmaches
The
alucay
eeeuetuo may may No
be Sane
The also be Same itt all
edges have unlqu Cost Cdistinct)
 Date
Page.

DiKstbos Algarithm:

I6 14
25 24 25
l2
22 22

y23
lG

X18 12
22

TRme complexig
14
tocoe)
25
12

22

Heap in the implementat?

Paimy A
loo
Tirnei lo Cnte)"dogn
Gompk.
 Data
Page.

Let G bea cOmplete undirecel graph

toith 4 vetices
Rl23,4, S,63 The maÌ
m mum
and
edges caeights
possible selght that a minimm
weightepanning treeCan have 's
2

# Single Saurce Shortet Pathy Csssp):

mayetwomt
idh-ve wt
(Singe Poig' Shozket
Shoztest Path
S

Dijestras Alg
(9Singe Sowtce Shortest Poths
Bellmao-fore
S >de (n-)
dn
-Ve

GD) A paid shoaest paths

<Floydlls Oashal Algo Dynamie
prs)
 Date
Page.

Mattix method
45

26
5 35

t5

Vee
seleckee 2 3 4 5
S-I
S-2 50
S-3 f,4,5
S-4 l,2,4,64
S-5 2,34,5}

Vetex
setected 2 3 5
S-I
S-2 38
S-3 0 23

S-S s62,354 (3
 Date
Page.

Relaxahon Procesji
Kold)

if (Cz < ) then

25

30

So
20

2s

SSsp Sp Trte:

75 <42
55

60
<2)

85 < )
mcsTi
 Date
Poge

#Dynamic Proogamming
Designstkp03tel hy
Richome) Bem

O coIN CHAN GE PRO GUE m:

iven Coin valees

Conttuct
posible cue

Taxget mensy
CN=12) Coiny - il2,53
5+5t2 =12. (Geedy methed).
GREEDY MEHOD FALS HERE

#inciple of the phsnlihy Statea that

initia S+ cte && dec`ion
+he
mut
aining ongtitute
optimcl dectsion Sequence
Aegard the State.

ist clecision.

* Dittenene blw and Dp is that

Gteeedy aivys garaeaony One
decision in De.
enmeeahon. cdecisiong dequenced
COn
maat
geneated:
 Date
Page.

Featr ok D:P; ’ optimal tolnS O the

Sub ohlemi e tetained Ccached
table to avoid.
t h e value

campd,-omplag Memoiz0tion
(top-Douon Anoach
DP implementat
A Tabuati on
Ceottom -UpAnnxeack

Eboncci Numben LCompuiag

EibonaCAiNo
Ath.

Fil Cn) AFib (n-1) + Éib (n-2)nz

Time comp kauity: T ) 0(2^)

Bute fotce)

op- DoO- Memized tmplementaion Qt

fiblo):
mem hb (0)
Alga
(m fntis unde7ined
itCa - ) tegult = n
ele
tesut = memf6 Cn-+ memfi6 Cn-2
3 &etun (mLnD;
 Date
Poge

2 3
m.

L2 35

mem Ab (s)
memfib (4) Yes3
memffb(3) ey 2
memfb C2)e
memfb ()
mem fb(o)=o
mem f h ) l.
mem fib (2) =
memfb ()2.

fb (5)

fb (u) fb (3)

Tme
-IocoPlexiby

Abo)
Space Comp lesity
 Date
Page

BottomUp Appreach o DP bí0):

mem Eb (n)
Algo J 2 3
mlo] =0 m.ol235
m[L] -1
{or ie2 to n.

mL1] = m[í-1] + mIi-2];

fime Complexity :-o

Spatc lemp leaity i- olo

Biilding n ot the
Sol he Ablemn clone
maonei Cindepenclent) by
analying locay opions OAI4y (loca

d& konquek BAcaK0ng

ncolems Cinclependont)
nto Bpaatt
thengolve eacb &ubnoblem iepakatey
Cin cepenclent y) & combine.
Aubnroslns to

BAceuking up of a.
Acoblen nto Geeies of "ovel apping
Sboblem & buildiNg wý Solution
1agex & tavge subo6lems.
 Date
Page,
Multistoage Graph
V V2 Vs

Cst ot path tomeLex

in Stag to teeh. Deh

Cas+ Cij)= io c Gk)+ CosT (i+l,k)0

kE Vitl

DCi)'k that mini mizei eqnO

k=3

ost (L,) = min? c (,2) +Cos+ (2,2), CCL,3)tcos(2,3)

cCi,4) t cost (2,4) c IS)+ Cost(2,5
3+18 2t.15.

Cost (4, lo)= cltot) 2

Cast ( 4, )= cl)1t) 5
Keg. k= \0.

6+4
[Link]
C41o)
5+2
 Date
Page

Cest (3)- 5.
D(3, 1) = 10
Cost (3, 8) = t:
D3, 8) - lo

Cost (2,2) - min 4+,2 +5; |+ 14

Cost 2,3) - min 2+7; 7+5 9

D(2,3) = 6
Cost (2,4) = 18

Cost (2,5) = |5
D(2,5) 8

minimnum cOst = 6

Path

<l-2 -1- lo -i2 7

fotlem TSp):
# Teaveleingy Satapexaan
fhe tou' ot TSP shoud staxt m
home &
Qnce &
visit Amaining
Co mes
baak to
Gties
home city Vo,S-T:ha Costot tout
is minimum.
 Date
Page.

gci)
KES

gi,)= cliVo)
i- Vo

21 34

2
6 13 12
3

Vo =|.
5l=3
K=2

ghi438)- min,c02)(2,fri),
K-3 10+25
c,3) +g l 3, f2; 43), c(1e)+g(4, 2,33) 26+23.
= 35 |S+ 2S

J I iz3,43) -2
.

2i33) -c (4,3)+gC3,+)

g3,d= c(3,) =6
g C3, i23) = 13+5- I8
C3,43)= 12+8 -20.
4,23) = +s=13
 Date
Page.

Ist=2

(2, i3,4 25
3(2,3,43) = 4
9(3,i2,43) = 25
3C3;2,42)
g(4nie,33) =23
J( 4, 2,33) = 2

Toux Constuctioo:
1-2- 4-3-1 = 85

gC, i2,3,43).
K=2 3

3)
(2,83,43) g3, R2,43) 9(4, 2,33).
44 k= 2 K= 2
4K=3
4
c(2,3)
g3,¿41) g(939a(z4) g423) 43,83) (3,:23)
ca4)ck,2 c23)
t + +

g(4,)

Recuxsion Toe

Al-faixJ Shortyt Paths Eloyd- WWavahats

algothm)
&olung by Geedy method oluo
st So|^.
son
by Elayd-arshas Algo
Time Comi On)) Spate Comi o(n
 Date
Page.

Let A*I) sanx cost of th path

om Wertex to ve ttex
Coest)oith l being the kigheit
intexmediak Vetea
alng the path
K-.

ACiS)

Base tion
Condition ACi) =ccij)
(o no intemealiate
Verte)

ACt) ( ) +A CHi),A(Ga)4

AKCi)

Ak-i
A (K,i

Ai) A i,k) Ak-l,j) Ai) Ai,k) A(k-))

Recuaon Tbre
C I 23

2 66 o 2
3 3 o0
 Date
Page

A A)A ) A°:

A 2 3 A 2 2

2 O 2 6 o 2 o

3 3 33
via
A2. 2 3 A3 23
46 fna madtiz.
6 O 2 2 5 o2
3 33
3 o
GATE

Alajo Can be eicd to

# Eloyd-(Oaxshalli matix (renx
obtap anaithve ot (7enr the
then he tme comple. o(n3)

to KNAPSACKY CBinan knap satk):

kNAP Cap acity M

Co:)

Suh: to Cand Tota

igh)

Space Comple: 020)

ime Comp: Oln M)75pace. Comp: 0(n m

 Date
Page.
tongut).
Laxoest Common kubsequence (LcS):
Kstsing Manipulat)

iven Stting ot Aength. character

then the no
o7 Substeings posible
KA 8CD
t2+3+4 ie n(n0
KA<BS<> KAS<RC <ABCD>
Subsequence ? A mp ct One
charactes takeo tom
tem a qiven ting
het m a yn o t be contieuels but
howevex theiz
theiy elotive
malotainedi

<A B G>
<ABC

Ficzy Suhsting SubseqANce

Substing
Giveo SA2ing t length n- chagacte
the no o subsequences
oc2):

Longat Common Subsequonce CISS

Gaiven Too gtting X &Y of Length

chaxacte4 a subsequence.
hat ammo. -to both &Y!
ts knouon Common Subsequence
y= <8D)
LCS? <BC 2.
 Bse cond’
- 0,fo /e-j=-I,o, l2/
Ll-!JJ Date

LC i,- o,forj=-,i -), o,1,2, Page.

Les Cnm)

Lcs (n,m -) Les (n, n-) LcsCn-l,m).

ma mar
LS(n-2,mm)
LCS n-2m-2) LCS(n-, LoCar LS (A-, m-)
m-l)

LCS,mcs (o,m-)
Lcs(n-, m)

RecuionRee LCS "ABBAB'"AC BAB4

t
LCs ("AGBA" "AceA)-3

LCS ("ABg' ACB') 2

Lcs("AB' "Ac')1

Lcs CAB "A"=1LGS "'A "AC).

Les ('Ae' ") LCS ( "A" A"cs('A"A") Lcs (""Ac") -0

LCS

A BA R".
 Time ompezity: o(n3)
Spare comp e xity o (n2). Date
Page

#MaiX hain Pan cut (mcP):

matitesARg
tuo Squate
The no o Scalax.
mutpli Cat neealed to multiply
then CAXB)
mcteix miltiplicat;
for Non- Squate
A mIK

Total Scalaz mutiplt Catf mx k

Total 00 o parenthesi2atn s
by Cat alon no 3
2n

(ht)

m>il mìn mlixit mlk+l,j) +PiXPrxPj

SLÀ]: kK point ot splt>

<AL A2 A3 A4)* = <2%3,3x5, 5* 8j 8x4)

-<144)
 Date
Page

<ALA 2 A3 A4)
K-l 2 3 (14L4)
(240 (230)
216
< A) CA2 A3,A)> <(AA2)(A3A <(AiA2A3) (A)
23'5 t S-g4+

K=2 K=3 2:
K=1
(220) T(216).
ka)(AA) <(A A) (A«) <A) (A2A3)> <A,A2)(A3))
3A5 S4 (3-5-8t +

3-5-4)
. nal. paenthasis
(AtA2) · (A3) (A))
k=2 K=g
=20 t 80 t 2-8.4

=14 4

(n= no' of matticesig

for i to n he chan)
do m ij] o
for -2to n is the chain dength
for i l t o

for kt j to /-1

if (qs mlij
then mIij]
 :o(nxM)
Time Conmp kxity
Spare (omplerity :0(nxm). Date
Poge

Su6Sek sos)
#Sum ot
A-ele ements
ments Cintegus)
Set of Coum ber) M!.
nothe elenment
is to
the problem exist a Subsets
dekemint ik thee
elemeots obose Sum
6f the given
equn to
50> M=50
Ex n=si A:K10, 20,30O

)2,3
) 53

Dexivot o Dp baded
SaS:

GATE nAKA A2 An) M

et Sos Cn M) repri -thecol to Sos cVHH

numbers & elements

Sos CoM)= TE I ihethes thexeexists

O8 gives neements
that Scm to
Sos (a,M)> Sosn- ) An>M
An SM
Bott
Base Condn.
 Date
Page.

n=5 ALl,, M

Sos (s,3)

Sos( 43 Sos(4r2)

Sos (3,3) Sos(3,2) Sos(3,2) Sos (3,)

Sos(2,0).
Sos (2,) Sos2)

n=5:MesA:{2,8,4, H,4)

2 6

Ai F F F

2 F.T
8 2|TI F
2 TF F
T F
STF F TFT

# Belmang Ford Alaothm LSingle ource

Shoxtest Patk]
() Dijkde Alga Lágeedy method aluay
woTk pmided the hay tve
graph.

Gi) the Gzaph ha -Ve c0t edges but

ut yele then Dijksada Algo
ma may not
 Date
Page.

Gi) ¢ the Graph ha -Ve edge &

wt cycle then Bellm cnn
ord aluays
) It the qraph bas -Ve
geachable m Sourte then NO -A La0

In Bellnon fozcl the melanation 0s

Caxsed
edge
uple jkration

intesicted path
Veties
n- vertices Cannot have
gapb, having
than
withoLLt loop l cycle
t

-2

()
 Date
Page.

.The time
Complexih os
Complet qzaph. having n! yertice
o(n3).

#RA PH TECHNI QUE S:

Gnaph TÝavexsalsi Corech

DES undiCtedtts (oTtot
dieoted.
GDAG.

BFS EIFO BFS

BES

gaphi
a) Gonnecteal Grophi
fenninola
)Stay o a nodei
E-Noclo : explomng Node
CNode ohichis eérentty
being exptored)
Livenods i Noce ohich is not
uly explored live nodey
a e Stoed -in Some Ds)
 Date
Page

Dend Node: Noe cohich. ha been

Oxplosed

b) Tinang-vaues cSAociatcd coth nodes,

ducing travesal
Dis(ovemy Time id(a): The me
cohtch the node Visited t y the
st ime

0) Finishing Tme f(): The time

ohich the noele becames ole ero
n0de

: A)

sho

H)
G=CyE). DFS Spanning Tre

Valid Invatd

A8, E HDE,G
A H G8D.

)H D B EA

HE CBA FG ve) GCFHEBD_A

 Datas
Page

DES n undiected disconnecteg ldisjoint

gcphi =DEI Depth Gxt Traveg sal

G1CV, E), |v\=2.

3connected components
A

1sl24 6l22
R1l2e

(9l2o Oís121

DES Spanning feest

GATE
eaith 4-ve ices
Cansidey a cincirec qraph
carie d init cegeneratihg
the lto caing

<32S) (5, 18) <&,)5> <o, 2) Connecteo

<12,25 *<5,10? <6,8) <152o) Disonneet

2)
.(oih 2 Compo.
0> (IB, 22)3,1) <612): Dislonnect ee
3)<
<2S,3o> :DiscO nneeteo
: 4 components
 Date
Page

DPS in dime ted Goahy

coheo Conicd onadire cted qoph
lkadsto the
) Tree edge portt DES Sp hee
famest

it child cleaceodeot in the Sp tree

3) Bak Leasl om Nodeto
its aneeto.

(ohtch is ne theg ancetoy noclerenelet

Back
fonDord

<AD)
<CA)
<DC)

2s

9
 Data
Page.

DES in DAG CoiaeCHCd AyetUC GLapb)

Topologeal sot: hincoux osde af
Of th
Ve riceSTenkesenteo he acivithe maintaioing
picce dences.
A ,A-D-CE-E
E-F
D-A-C
B
SouTe Sink

sl4

Ôs/s
3/2 lo]i!
Amag. elements in ginishing desending orel
(BO’’

#BPS CBreadth Fist Semch).i

EIFO -BES
A

Parons A A e 8 CC D.

GcVE).
UFO-BES live
Ptort A AC CG HHH
 Date
Page

GATE
Stronglñ Connectkdr Componets
Connected Campane nts
DDirected Gaphs

gtaph Connected if thexe is apath

and patt tom Vto
Sec2
Secl
E
T)

Seo3

secl

Sech.
Sec 2

GATE

P-OEve diectec qaph i a D

DA G o ts
SCC.
p 6e distinct SCc in clicced
gaaph nd (u',)ec
4hat 4hoxe is path ny! in G
 Date
Page.

then there cannot ago be a path Vlnv in G

c'and c!
edgc om a node in
incC to a
in cthen the highestpost no
Chnishing thne) in
in cCis bigg than tho
highest post in C1.

ACLution Points Cat Vesct) &Bico nncded,

Compononts

is hat Vestex the g2aph, the tenOVal

af cohich along aoitth
oith au its edga, paxtiio
the Gtaph into 2/mone n emphy
non-

AA gxaph is said to be Bi-connected ei7

t doe not Contaio axti anlation
point
Ghnh is not ELConected theo
ts maima) Cubgxaph ohich is
B-conne cte . is Biconne cHe d Component

lx Biconns cte d Components:

-.6 Biconnected Compo

3
.:5- Bico n
Compo
 Date
Pooe.

#Sorting SORTIHG TECHNLQVES

Classi7icarm;
’ totexna Extexnal Sort

<Rac'x Sort
Ns Itexative
In place VsNo-IN- PLACF.
<Meege sort
t Stable Vs Unstable

Tnvetsion of an AO
- e t AÏ|n] be
incices (i+j)it Ci<y) and CAIi1>A]
thon the paix S (know
inverÉon. the axy'
2

A 8|94 5 2.

K2,3).<24) <2,5> <2,6) 12-j0versions

<3,57 <3,6.
<4,5) 4,<7

on)
BUB BLE SoR

Algeithn Bubble-sort (A,n)

doon to
1'fa pass f n p a s t

2. fos i e Ito pass-i)

 Date
Pags

if (ALIJ >Atitg)

Soop (ALil, A\i+13);

2 3 S6
A: <&o 6o 20 |S 40 10>
<6o 2.0 1S
I4erat ’1
<6o 20 8o IS
<6o 20. IS 980
<6o 20

Time (oplerity
Coamp axison Suaps o (n2)
inc nn-)2
Deet n (n-)2 n(n)2 (n).

Optimined Bbble Sorti

i) Bet cale: o(n) : 1ocle

#SELECTION SORT

1Eind the SMalleat elemnt in theist

with the Value in 4he cuent
RSuoap jt
ith pasition.
3: Repc at H elemonts
until tho is Soyted.
 Seleetioo J04t is the ony S0vtin tcchniqus
Compason bayed Serth
least. no. ot Stoaps (o(n)) Date
Cye. Page

A 8o 60 2o IS. 40 |0
i=1; <o60 20 IS 40
4o go

Time amplfxity
4A
lomparisen
n(n)
2

#LNSERTIoN SORT
<Partt al Sorted list> usortcd list
Kaae a g Q K et 2

at thrend
(a, 42ag(-.-qk)
<patial &oYted list)

A:<8 2 49 3s2.
2. 3

Pass8 2 49
49 36
torn clmutj
P2 2 4 9 36 (n) ases
P3 2 4 9 3 6 quired.
p-t 23 4896.
 pne-Sorted then
time ot o(n td); d = number ot inversions
Date
Page

Time Comp
omp krity
eest cosc

RAD|X SORT (Non-Compaisonbascd soYt)

Base
2 3
A: 23 64 83 1 333 545)

PA SS I: :<723: 83 333.64 I24 4 65 545 7 44>,

PASS 2: 4 723 24 333 545 64 6S 83 49>
PASS 3: 65 23 q9 i24 333 54S 723)
SoYed (ist
4833
124
723
for PAS
2 3 6

for PAS ? t2tr

q23 333 s 64.

2 3

64

124 333 545 223

2. 3 6

Time Compl ~old * n)

de (No:oc hits digit gox lasgest

No').
 Date
Page

HEAP:

32 (13)

MAX- HEAP MIN-HEA?

Heap Constuction :

Inuettion method:huct 1 element t a

hme
startingm
MAX HEAP:

) BestcUE'
leatnede

iven tuith n-element he time

inset element fnto
complecihy
is

2Build Heap Heapify:

A: 10011q|8|1412) Si|132
2 3 5 6

2i 2it)
 Time Complexity ot Heap Sort is C(ndegn)
Date
Page.

(L14 (118 Heapigy ((19)

a13 (32

Time tosplexity ot Guild - Heap (Henpiby)

(tu)

(132)

for aolcte opi- Time (ompiezíh odngn

Sets Repasentcd ay paiwlse cisjaint
:S=L, t 8,91 Sz =2,5, to
S3=34, 65
Teprlertative

3T6

Si S2 S3
CA)e make any elenent ay oprasentativel

Operahon on Set

9nton ): 3, 9, 2,5, lo4.

 Date
Page.

2)Find (í): Repreyents the Tepreentaive ot

the

Find (a) I
Find a)

fnd (5)+|

Repreientahon Of s

Aay boied
Let o=l0
Reprelontation

Sy=,, 2,93 S2=f2,5,10y S =3,4,63

Sç =
2 3 4 5.6
5 33

L 2 3 4 s| a 8
3 6-|6 ’ 2
 Time compleaty '-0(edoye) Date
FoY complet Graph. Page

KRUSKALS ALAO RITH MI

28

Mintteap - lo 12,16, 18,222s

25,28
18 2

22

tl3,]
ttt,j <u,v) <2,3)
16
tl4,2] i-2ke3
25 +[32)
12 k2 kt
Et62] 22 t[2,2] <u,v)= <3,4>
I5,23 je-3, Ke4.
Kuv)= <45) <u,v) =(47
jt-3; k<-3.
it-3kS (we anit add edee).

jt-3 kt-l
Ku,v)= <5,+)
j 3 , ke-3

+ Optimal cost Binan Search ree KOBST

that the
binaxy Valee
4tee oith
each
the
node gteate
+han the valuee os ke7t chilcxon &les
than the Value ght children.
 Date
Page.

Paocedwe to deseimine Cost o¢ B5T ():

1) Cost(o cst( [Link] (Unsuces.

Search).
cost (ai)

3)| Cost(a) level (ar) Yrevel Cai)

=)
formwattcast Car) Pi leve) Cai)
ob of waing a in applicatn,

(n+)

) 2cost(E:)
) cost (Ei) Uevel (Ei)-)
-qi* (leve) (Ei)-)
pxoh, of ing the ideati7iei
in he set E

) Tta Cunsuce Searehes q; x(level (E)-)

2) Final formulo or Compuing mstot BST'

The is dipendant do 6oth

the height
 Trne Compkxity = o(n3) Date
Page.

# Congtucion 04 BsTi

Cost (T) = PytCost( + cost (R)

Let c(9n) be the Cost ot T n . Cornyt

P tcco, k-) +cCK,n)y +coca,n)

R.
|KK<n

t-hat is adlele d. to e
L:s-T & RsT to balonce it
TOot:

ptoblema Solved by Backtracking

G) N-Queeng

i) Gzaph Calauing
C) Hamilto oian cyele.
V) oll Knapsack