Scribd
Upload
4 views32 pages

Algorithms

The document discusses various types of computational problems, including tractable and intractable problems, as well as optimization and decision problems. It covers concepts such as NP-hardness, complexity analysis, and algorithms like Prim's and Kruskal's for finding minimum spanning trees. Additionally, it touches on graph theory, including definitions of graphs, paths, and connected components.

Uploaded by

rishikriti23
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
4 views32 pages

Algorithms

The document discusses various types of computational problems, including tractable and intractable problems, as well as optimization and decision problems. It covers concepts such as NP-hardness, complexity analysis, and algorithms like Prim's and Kruskal's for finding minimum spanning trees. Additionally, it touches on graph theory, including definitions of graphs, paths, and connected components.

Uploaded by

rishikriti23
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
SDrss of problem :- 1 Titackable i= Pyaistams the can be sob able i a >tuhoneble CPolyho mick) Time Problems, 2- Thtnackable!-wsomete intractable ot they gots Loge We ote uhable. to telve” them ih tadsonable time B Helany prcblim is nek solvable by any compufe ho matter fow much time is given. E+ Opkimi zation + Aske Fr best Coptinel) solution fir a ven preobsim . Eg> spening bree Citinim aL) 4- Decisiohi= Yes. oy No problems, Sy The chad& Pom dows of problem that her ayo hms Proliting in pelyhomicl. time, / Adelarsmninig fic proba. > OCP 6h)) > Compleniby LY Sample problim in do 2 4- Fractional Knopseek 2- MST 3- Sarting. Ly The dath MP: Sstuate in potlypomiah Lime by defouministic, alyostithms. FS mel tcin) hon bens Neo cevrak air wed Ygyess sight ainuert > cjtvation an be meuuwed ih stashable time. Ly N-P -Noh-detorministt’s Posy pomiah sy Probluns, (14) Paadiionah — Khop heals czy MST “2 Po ee iB) aotheks pene © scanned with OKEN Scanner LS NP Hard := Prolite aoe rtoducenble Problem @ 1 atiduee be (A? FE given a Jodo fioh for | * Apsehtm is we Hard p ah problems Ih NP ane Polypemica Gime eaducabte te Jt Ex Hamittonian Ge. e Every prebam in NP iS wadvdable te HE ih poSy pom Bo se jis sudvakle to He . LF given & crolupion te A” © Wecan vedice B te A eolubion b°8'. We can ecarily Gens Ertuck by NO -comptete t- A piebtim js NP —compluke 1£ the powbtom is beth N-P Hatd and we, b> Gmpluxity Aralysia => Asympta ds Notation : @- Big-S @) 6-Meja Trek cay Gmall-9 oc) iy" @ Q? (SB) Smalh~ O mega (0) 4 A Fonckion Fin) 1s raid to be in artder of O(gcy) B al PPR Mae aan - iE Fem iz beund alnve by Asme constant tultifsle o2 @e gins a Lanye —7 Fount fen) << C- gem , Ww rsh, C= conekant C+ve) he = Fve int. egy Fin; Eps oCh*+4n) 5 9 Cn) LEPPePprree © scanned with OKEN Scanner 2) A Fonchon fihy is sald te be ih LC yeny iF Fe, is bended belaw by ame conck. muliple 9 9th) YM dogo oh + Formule Pind BO gy Monsn. c= tye conttamt en bo = tye int ee Est Fu = hh = i co) (3) A pndion Fihy js sold te be “@ Cgmy) iF Fem is bounded beth okeye abd below whils some tve conmtant frallipis 2 gthy large -0, ty rE there IS same tye constant C1 and G_ end some Se ee oe uch thal, : Fosenuhes Cc, gth) © fim) S C2. ythy pK ADA co) = in) 4 Cyiry) © scanned with OKEN Scanner Conhected Compshents: 2 Terns : * Graph Ca) : cy, &) 2 : [. Uy Edges = Vertisés Y Thdegyes Ltrcidenty Edges L ouk degre {out ger Edges i DS 2 © © ok = 2 © Pakh : Sapence of vertices connected by edges - €9- (12) <5) C89), Met CMinimin Spomning bul weighted Undowked Guroph He Spanning THe! eo A wbeck % the Edges YP a Gumph thet omnes ak youces Withedé -fatrhy aw yyche, 10 pe lo Le ® H Oo, @ = Te w withougs vel Spamming, THs, _ «& © scanned with OKEN Scanner a Mibimem Spanning Tree (MST. AL Spanbing Ther vith the minima pescibl sum 2 Edge base. => Abgo rithm of Prins 1c step-t- Stank with aby verdix as be xoot o MsT skep-2: eect the! Edge With the trinfinum Weight that — cormecs a vette aluady ih the MsT toa Verte eukside it. \ MH step-3:i Add that edge» ahd the hew vert tothe MsT ‘t ckep- +: TF nd edge fens a lm then exiyde | ctep-S* Repecte rb ath VeHttices ane ihcded. Grroph, Vleighted O. Adjozehey Mabstixe 2 = = = = = - = Az © scanned with OKEN Scanner 4:2 G34) 2245 a= Ct ++ CLS) s= (%4) : ‘ peop D's -_ ~~ Max, Parr Node Max, > Minh 35 paint Node mae A“ 2 tin Heap S36 a te might Fill + The Gmpluxity x Prims, Algosifhm '~ A- Usihg Adjacsncy Mabux chat Liheax seach — oCv2) z= Using Min, Heap — OCE leyv) PEHCOHRO RESET CHER EERE CEO OSs ae ke pwskalr 5 Abguulhm -Mst § ehep-h ~ cork ali the edges in iherterning EN 9 Weightwr Tritalre MST 8 Etpty, sewuted ander’ = step~2— : Z- Fer cach edye th #96 step ekep ae? EG addiny the eel ges desk firm a ys be thea jhelpde TE Ln MST, a step B2- Otheuuire dis canded , Be ! e © scanned with OKEN Scanner Step- $= Repecta Gott ath the vertices cree mulsded A)—*© OF ae Tike complexity : > KRuskal's Algorithm usihg. Hea We take, ol eee - Gi ki Net]: ; = Prins giows MST Foon one yertix,, picks sdzes cemnecded fo visited ede Cele ee eee eee eee => Kuakalis picks gfobally arate edges ky avoiding cydes He Tntewat chedy Ung Ady ostithm * Prolesim stafemenk— (4) Conde only one ockinily af « time (2) Want te do rmximym achilly possible thoee thak maximise the conus arte seltctes ba (a) Whe dus adiwily tak maximise the amount x achuitin, —? <—D 2 The Constnoin het@ is he wo interwals event mph time =? ae they wu compatible . a? ee Notes Mb all inkemmls ore dypored tobe ackeduted onby = =? a © scanned with OKEN Scanner Ex» A Drawing : Reary oti sports, Ly optimal Abswen > Cte), m2), c,h BD Mony solutions ae possible which we feadihte but ue @ have te select one otk gf these “Saltbion ov fe, @ that contaias ax ho. of InFewall. € © ae * Gud strategy :~ : © t- Ptecess the [hteval IK the ortder of thei atoll g time Be the — elitnk skanking time . WidK nek MBjve | the ophiinal’ salubion, \ © 2- Biers fhe inbewals ih te oul eat Ot Fouest ConFilick, Tt dees nol always Dye the se optimal answer \ e Bo Process the Thfsswals jn the ootdet of thou Fibishing@t Hime’ je the interval For which ibis hing Rime ig™ od frak Of possible. Tavs atebe so, ally gives thes optimal steautk. cece “ae eH \ 7 ee s — tas) Cea (Ly ew @ en —S So e . a a 2 + s 6 a ry 4 * ——— i e optimal Answet ~ wor ) (4 sph ° ® Pessibl Answer- (C92) (%4)) & {CL3) Ch ayy = © scanned with OKEN Scanner te Complexity + ‘ Meee eee eee deeded Vs The complexity of the mrelhed clepend son the cwthing Alpin chessen fer sorting the Tnkerwalk 15 Hye onder of Finishing time, 4 Divide and Goh per = Big problem =p canbe divided ihto subpxeblim Sha, SF, SPy > each Aub prchlim id Independent => Divide 7 Solve Thdivi dually > Combine FTE Ie oe pstchtom seluing shrulgy bWhette prablim i's btaken ints smal sub pcblime Solve the Aubpreb tum Crcursival, ard merge then solutions’ get the Final Hoult , Exenple Binary, Search, Merye sue, Quid< sont amd stv absen's mabtix multiplication. , ‘ > opkinalily of Divi det. conquer: sigsiery i THis stickyy gyes an optimal roulk Th poroblim cannot be byolceh cows into smllye indepen dent problem Each of which can be solved jaarerively and than solution en be tomtined EF ficlently. a~ Revsabiliby ran 2 Bowr Finding oe Binoy Seach i— We This Will got n/m in the ee) wanst care, bh Mi © scanned with OKEN Scanner | Neawertence + e ae R R e ecwerence elation is a meffematial Expression that dchnng: sech Certm oP ox sewence ob a function Pf JS prUWlovr teu le insted PL any a firma fer the ph form e cbuctly | JE gives pulatinship b/d the bY tertm and © one or mene oP jh carlin Lerms, 7 e 3 A seawerence jutatisn for a Beware. “ap fsan ¢€ cut Arm e a 2a Seo, Snag, - - Bauch) e : a PoE en is Hee! nitht’* pol iw FIs some Junckion i e Kis ander f reurrtence, e = : " Eas Fibehacci Senin C etteese oy) & Cee a 7 « FE Masten Thea: a mL gi & j e dot azt and b>1 be consbonts dbive Retry —eprdKinype @ ctfired AF Fir be a -Fundion and, Joe Ten) he dedined o, & the neh hegalive Integers by ithe pacurnrence. Ty =O TCh/b) + Fay Whee we intesprt h/b bo mean ebthert Gilet. .. aye Q Ch dey ty h) . Then Tony har the Following atyngiee He beunds e A) LE Fey = OCn ge ®) For seme eee ese - then Tin, = OChdoy *) | “ew 2) Te Fay =O Cht) then Ten) = es 2 © scanned with OKEN Scanner (3) EF Foye SL Crtoy i! 6) ter gma cormzane E30 and if a Flo/b) & C Fin, for come canshant acy and all sot Fic den thy clage o , ther Th OCFH »). shext Tricic > 24 ao » > Fon, aS Or +o 5) Se 3 > Fe 2 hr Jey & RS ms ms => ay & ty Rm ty = mh s @ Te, = ST chs) th a= J bes ZY deck » htog,s a ahigd = Jag = he hteg ay Fun, nz > bh compbeni YA HS > aCh?) o ohh) 147 Shee) 4-1 o- & i, ached 3 hile Fim= 1 as) fh doy Sw Fins ae comdsxi ty > “Tony = Oktahape, ec4 by h) © scanned with OKEN Scanner He Rearnce Be & Te, = STCh/y) + htsgh Ges => check =, te b=4 ne Fay = hog hn I Hemegerewa Noh-Homeyeneoua Subabtuhen - Induction Reuntsive True Lternotive veebse chang ing > Moaken Methed ey es => Reunsive The :— Cn) — ut s hee n Loy & Finy am — = mig 2 om fim) = bboy mem @e -ID - T= & Crdey Bo bey b) = 6 Crit toyn) = = - - - a \ © scanned with OKEN Scanner a oe Th this melhed the stems wu speadied ther obinely vhEL the cost is 4. and the pathuth 1a) beady & Find the anwen, : TO) = 8T CR+ we 2) = BrCh)+ a Sy Ti = 9 Car Ce st) ene ~ 69TH) psa ne TOR =a ere eae as he 8) +35 Tiny = 6+ eee eee 0e0eeee @ 5, & 512 (4h : ey) RAR ane he TO) 7 -_e. 2° ne © scanned with OKEN Scanner TE Substitution Method < TH consist YP Too steps — Bei t- Guess the Form of solufien vd SV 2- Use mbhematiat Trdection & Gind the constant COandaw condition) ond shew that the coomedé, SEE Solve the Wiwivtence SO Tr) = 27 3)en : Tat a Gude ¢ tse step-1-Tit) =o av = 2 (2) 2T C2) pa = 2TCt +2 = lke te =2 TH = 2G.) = 20C2) sige ( ‘ sess u uke elle eee Se a =& ‘ey es ZT GS Joh a 2TC4) +e = 64 ¢2 oo THs) = ar (is | I6 a 42 PCR Ae SWEET + oe eg. h 4 ee Guess ic Ta) = Miley h - © scanned with OKEN Scanner Tih) bh Log 2) 0 (hJogh) =) Ton) & C Chdtog h) Step-2- °° Tdchive Tt =? ¢ CL hog L) Ti) = © ca) “EE fs astume that it in bwe for a VCS) oh Sep 7 New we have to prove thal TH) = Ghrfesh = ss i= abe ceteect Br hf Tw) = z7Cb) oe Ti) E22 Ly ey) 4 T (hy a GA Loy A Scns To) 5 oO Cte eer aaaaaeereeeees eee e e ee eo peeeees 2 l © scanned with OKEN Scanner Dynamic programming > Tels «a techmique of programming for Beluing preblms by breaking them ‘dow jmte overt Jappins Sob- prsblems 7 ebuing each sub~ problem Ohce ahd we using these ponutte | > Tt IS useful where the pretim have pptinat sob shucbwe ( whenel a talion ‘tan Kuudietecm! call sabuticn, > When sub— problems overtap. = > »S> SS S tS ; © scanned with OKEN Scanner re eoooOrX aE Beliman Ferd Algenisthm |= compli Vz Stee-t - als] dle] wv) ther aCv] dO + wey) then Repeat thas ve cys IS Ment Source _ ee lil a a vi ieee FE Bboy —Warshath Abgesittin = STE ie dypemic Programming Approach te Find the sh HLS Om path bly LL pain 9? Yerticns WN a Welybted piebh OF f TE eennot Wet iy the prsence of we ody ©. abeays po 7 EE ewes Adjeconay mabtix by the “pproach ; Prvogsiarming, Zl Dypame PrrePPPP? © scanned with OKEN Scanner Exes L-2 << S Adjaceh 4 mabwix Me => disack ealje- pathlength =f oa Mt iF © pthsoyih M*> > iF @ patter fh mo [t= 2 1 3 5 Ss 2 2 6 6 3 8 3 a = ° As + Lo ° © scanned with OKEN Scanner Fortmola : — ALi j1= min iia ALi tKd+ ALasy) Gomptexitty— oC h*) CL, V Knap sads co ies — Gu Fnadtonek ( Greedy o-t Approach ) C Papamic approach) grin, a — S e Zi Cat cs le © scanned with OKEN Scanner a baa a ae Fractional [upsadk Peabsom,— LS Grudty Qa —__ Profit > Cast Lo Height | Se Pedi Wet grt copay - 150 // Le C to) Te Ces) —>2e Te Coe) > 20 [50 fae Comp duity > © Chlegn) Guardy > 3 4a ea! caer objec} Maplin) s« the Page —>28 oh) + © Chtegh) + oh) YD Maximuny, O= Lb CPynarmey Ne ee meas Bo. —_—— Care © scanned with OKEN Scanner » Notes '— ort keh ap sacks Adge = O-L ken prac oljenithm bases bbe rhe tbh Without ew, TH abe caleusates” prop weigh weatio and dties bo Jill bay. batealsing ik shte pe = Any item sheulfdirt be Proien ah, even Aye in the bay, (# seme Spuces eine somplinily of this problim withué ctynemic approach ts ortlen gf 2% or Gh), - Bek with using ypomic Poe Rermin ing compli. of m,n) Whete m= copecity YP Krupsack ho= totek no. of item. + Hashing is DRondemised Alyerithm:— Randomise ahyerithm yee Nonlem choices dusting the eprecufion these abgeytihms deni give the sume output | Input . 4 Hashing e Harhing isthe methed te Skene and nuveie deke Fately Yang specieh Jymcton “celled ar” Hash anchion, 2 2 Which prowde oC1) ewerige Hine complaiky fe Poh, debition | Updation envatis a ik “Hash Table? Cav), and Secotching © Heshins Mtoe bmalt ther of an UK ceatle oe Hash Table: Tt is an wutay wherte cea is artarud ot poet position cle Gulect by Hanh Function © scanned with OKEN Scanner > Hash Ev neti on :- Hash Function map a key te an intex. eA geod Hosh Function must be fast to compwhe and mintmise the callision, Example: Diwsion me thed , Mo dbipl cation method Univerca. OST CT suduces the collisions) key / Zn a ie ioe key tn Colo ee fades Ot 2 Ss C2te24, 22,23 24,25) Hash Feachion > hb Cis) = IS mod sb seh- hC 20) = +8imed S a h@L = 2Lmds ; aL | how) = 22 mod S : _ : HC) = 23md5 as nKC24) = UW md S 3 © cahtision) Gis). = ae 1S The Feys 20and 28 ao TZ Wash ty the seme Key Cettision 7 When two Keys Hash to the same inde x, tH co ision Husatubion Techhique !- , 4- _opch hashing Chaining ) : Talees time, Fach Hash table 5 rE conleatns a UnKed isk af molt le Keays, map to bhe cxume index then add them in the Usk, © scanned with OKEN Scanner disadoan tage: 2. qurcmene fr were cess fy linked USE hb = fetes K med S ss 40 Ex> Keys 26 eee Endex ae ] fz TTT Copenh aad ussing ) « 4F csesed Hashing Find arether empty LF an index is occupied then slot in the Hah table — Thee art 2 types - T- Une Probing | 2- Qyatdretic Pro bing a- Devble Yachih pe = Liheat “Bitobing Tn this method When @ cllision we hext empby ihdex. reel et eae ched< ev the Ex> zy ye ACi<) = CZR+S5) med to Sok he (2.03) +3) mod to = FD mod te = 3 © scanned with OKEN Scanner pO?) = C2AZ) +3) Pred be tomed Le Bb Fie = cee = 2b med le -* =) a = a 1 i CeELLLELEL Ts] | et = 6 eS 3 chain 4 O-uadnalic Patobitn 5 = SEUS mad 10 "473i 3 Gta =2 © scanned with OKEN Scanner Peal equartoes SwWher callision we probe SCALA CID) ned im By using — this fo > now he 7 ‘ At BES ee Ht at Double Hashing :- Dowkle Hashing Melvees the Ne 2 cLlision by ony fe caltided then the Hash Fordichs When a key is Next — _Lection WI be Aird USing Fesmuter, [ur of hLr = Wick) modm whe, = viz hy CH) mote FE Univewsek Hashing :~ CRandsrise Hashing ) © scanned with OKEN Scanner

You might also like