Fw DAA ~ Design oud Avalysts o Of Algprittons | yf Exeduction: . oy Ngotthen | He (6 0 Sequence of unawbigens fasbructiow gor soving a problem te; for clinintag a xequived ¢/p for ony legttimrerte tp tm @ finite, awourt af time- p> Teopectamct potas: i » se wowltguous coquirement for each step of an alate Commot be sed. vthe wrge of Taputs for hich an abprtihe ‘orbs has to be specified carefully. +The same algovttten Com be represented fr several differerct voays. + Thexe may exist several algorttrons px sdving He problem. + Reprithns for the same problem can be bowed on very clffevent ideas ard can sve we poblen EU doommartically different speeds > Malton af ebjers Probes bp _—v caput aL Compete | > atau > Rind amentals of Agorttentc Rroklenr Goluing + of steps to 9p Horough & desig & omalysiug on allgertttonn - Understanding the problem “Reeectakrteg Qe capabilities of computedional devie ‘cheadng blo exact & Approxtwete problem, sduiug T Algortton design techut g ye 1 Desiguing an Algortth. k Data sbruchee .,)), Scanned with CamScanner pphayarenevanaainicy-tlowckat, A tevstand We problem Detde on: Computabional macans , 7 exact vs. oxtmate sdvivg: algertthn dlestgn technique L Design on algortenn L Prove cowrentness v Aalyze the algorthn v Geode the algortthn ~ Noort. + DotoStuchue « R a oe + Methads of specifua on dwn — Euclid’ ime Mer" — Pseudo cade . Rotvg an ortteds Crcrectress : Arraluyes on Atgori tbe . = Be efficiency | 7 Spoce effictency — sSrpleci eae | 1 Codtvg of om Mop illo Yh Teportact problem type: ~ Sorting § Reacrasngtng he thers th ven-decressty oxdex- “Roo properties of sorting ave stable, t-plost Gy bubble «ort, mege sot quick sort ete. > Search TE deals rotth, fird&aq a atven voll catled ~ a seacch keu. # 3 ™ Scanned with CamScannerfoo searde algo nas + exes search , ivaxy seaich! up ShReg_processing 1 Shing wakehiug | ( Geaph problems: Graph travesal olaprithnas (BES, ESD, Shortest path algoritons (Dijesteas algortles) i Gombtuatortal. problems: Graph calovrteg prokless) covellivg Salesman prdcler ore examples Lp Geometic prololems: closeb— pak problem , convex welcottcs * , | _o Numextcal_ pollens: Totegrabion 4 dtffererctioction | | | w | Findanentals af re Analysts of Mjorither afleteticy: The tralists frametoork : EL means dp, calculate the |) afftcfercy of algortthens in tems ‘of -time comp lexty kil — ae A I abottlods > Mensusteg an Sypuld steo: Myost all a wens | Units of Measuring Ruwiig tue: eT eK EW) | vlee; | Td = ~remnivg, Hine of progroun Kc exceulion time of avr algevtln's baste operation | Cln)= ve of Limes Ube operalion executes Es algorttln A Prcers of Gorath + Gmpawes te. values pw, at, wd,2% | logue , wlog~ , + hbo -cose, Best-—case and Average -ase efficfercies: Phe worst-case efftcteucy of om algartitinn’ Bs ficiency or the word—case Bput of seem, udtelr fs Bo Baput of size n for voltel. the. oplger Elan, Cs Be lougest among abl posible ey uh of Leak size. Pte besb-case effictercy of awalgortthen 1 ts officion for the best-case Ropu of Sen, wheh & an Rapat “11 fre wn for which the. abgetthes suns the fastest ono all passtle Rapids of that sive - 1 Scanned with CamScannerop & & veiller Ue voorst—caso omallysts Loe Les case dren Me vecesory Befcmaction aloud an abpritig bebavior & a typical teo vor on padioulas Teput. TR & overage - cose efficteney. . Rocaptluliation of toa frolycts Framework: Roth | deme & Space efficiencies are mmeasuced aapnctons | the allgpritaw’s faput Sze. : Nie ieee Baste Eipiclency Chere | TS. compare Rvonk He orckxs af growls op a adertids use Levee violations OC b oh), bl omega) Choi deta) . ob, ° aw seolbleia Sze => Ouctéx oll nes NE ee ee of geobe | . | fois | > Th wosh cases average cose fs eqpah co von , | ease The: Ueoreeak Lepenctip. fe: frrerage. cose = ALL passthle coreHime / No. of cares: > Bry oh vototion fs fer woash cosa, Bi © is for best ase, Big rete = flor eweaage- cose. > tn) ecg = By Lok(O)(esorst cose) eke) Reg Begn ome Pest coe) = aggre Eee gey -~ Bg ~theto (vege) Gr Wan tl = ov) wa nel 2 SO) stay < cg) - Salle oh = btn) = o(ger)) > Hn) > Cg" = Seal l omega > tlm) = (9) > Bey of Tobahion ®% lpper bound “of algeitton' > BY - WSF nrcbakiow fs Upper bowel of allgprition > swoll-oh ts the tert - bound. > swall- omega & the Hight r Sepipe bound. Scanned with CamScanner© Peoblems? (Assignment 4) 2 La ulogn thw = = __ (wd) 1 v4 tek n= 10 = No log! + els ae Cosy), => 10(3-3) + loo+! =) Ls (tog0) > PP 33rlootl = __ (1000) 134 < c(looo) an wlogn + wey = OCW) | | ® vlog enn =O (vemest value vot largest leh. waio * : value) oD Wleg® +10 +H! > 10(3-3) + loot! a 33 + loot! > 134 & wo te; to So, the neorest value ts w. in vlogn tel = OR) ® vloge + We I = —_ ¢r leé w= lo ? => lo log + weal > 10(3-3) + oor! to34 > c (1000) t nlogn + wey = SLC) => & vlog < — Mnleg~ lee us to => vo xegi) = uoaee. (10 log) => 10 (3-3) = —— tow 3-3) => 10(to.89) = —— 23 > 108-4 > ¢ (33) Scanned with CamScannerae wileg’n = SL(rlogw) s wewlogn +) = (L — lee n= lo = or te? log 4\ => loco t (od0(3-3)+) > (woot 3300+ 1 => 430) SC Coco) wee Wlegn +l = M(n?) Cowect solt- As +o find nearest one: First consider the marcterm t fi so that, FW = Wr wlogn HL and: maxtem one fm > 3th) 3 fm) = o-9h&) LY, loo dousterts coustdexation we verPlegn tt = 0 (logy) *€ bthen weasest solulfovs one asked greecest lower beunt® $5"amega. votetfows , for @tg-ch volatios we shoull choose. looest &pper Louvel- : + Now = Yecussfve & Recurst rethwus t “5h prckion which calls self te called ‘vecusston Such algorthms cre called wecurstve algortiims —> Now -recusstve algorithms achide condthional sb fonctions etc. : non- -recunstve Regottans + : 1 belle on a puameter Selfeating on Rapats ste as Tdewttfy the algprtamns baste operation: a. Check whether {he vo: of Roves basic epescko® executed depends only om the See of taput TH cso cleperds on soe additional property, the oi Scanned with CamScannerez... averoge —case ,amd if nesessomy, , best —calye rclbueey he to te eesttgated db atecy” ae i Sek Upra sum expressing the. ho: of Hanes algae Tat opel tee . 5. Usig stonclas) formulas & sles of, sum wardpulation, either find a Closed ~forne for vrata fr Be ah & ot te vey least estaleh | as ordes of gol, + Malremalicat | Aralysts of Recursive Algptthenst/(s | Ta Backwoond sulstitelion vlelhal ‘Heaton weltal =) BReaustor tee meted wi General pla» fox faaly ding 04s S efftetenrcy Of Reouistve. __Aggrtitens: 1. Decide om a povanerter Luisa, or Brputk a Rhedify the algoctins baste speration. ] 63: Check whether! the: vel. of tines the boat operat Gs exeadted com vory ov cliffrerect Caps so than the poorest case average -cale } dand ae case efficienoes musk be tuvestiqahed spately.. war Set up a wecurvence velan’on ve aus opPropriate tathial cowlehion, for the mumber! of Fiies ee bos opexotion {s executed F-dlve the recctwence (dat leash, ascerbaln: the’! oder of growth of ifs sdudion. sy Asstquemert t a ‘ ; 1) Malhemolteal faduction ',2.4 = enti) se iz z ~SBoste step? ble need t Prive Hat tk ts true for nei. $0, substitute nit We dhe given equatin Wer Bt eI Tec RRS nh) = HUE eet “a > z ~ LHS =RHS , the ey 1s tuedor n= 1: WEavabeon step! Let us, consicler, rot, the Loken eqiction fs tue for “=k, then Scanned with CamScannerBye ete ae fet 2 iy Grenexalization step! we fs. tue ve tue fr, ne kel all other voles: ‘60, for eke! ‘cousider Liss > oe tos Zt +t kl . Y > 5 re 1 Pe finn tvcucion, KORE Use) | step] = + (kel s +. sj (ee C&+2) = (key (cred +) Q ' & RISK For we kel! > (rat) (ern 0) 2 vreed to prove that the yee wotlk be true}o, iw in “LYS = RUS \ Hence proved | “DThue, complextly of Fibowacet sumber usteg ome ve cusstve algorttha / solr declarodion . of: bapub (tes vw) ueo wn, OL for fea to n do * “3s <— ny Ny yelun Ks nN, ere nes : Te vo. of operations th the algodti con coleulated as: Covsider each for loop to be a stgle operat” tren, 1 le Scanned with CamScannerCW) = BAI Pay ‘| tea = cinyehn-t fo, Hime Complextty Tl) = KiCCH) Tn). = K-(r-1) Now , we apper’ bound af Tn) fs) > Ws OM) 18. Tame. complextly of (Fiboacci uumber using vecuvsive algovi-tn. bls Maori tow : 4 Joomputes the wth Fibouacct uumbex tbevatively by using th deftuehion U Loput : hk vonnegative integer 1/ Owlput: The uth Fbouacet number Flej co, FftjJet for fo aton do i A(t] efi-t}+ efi-al : velumn F(nJ . ) “The basic operation & fln) = f(n—1) + fla-a-G) ble nents ft-Ne f(n-2 +fln-3) Substitute e9O fim) = afta) + fOrd) S, the Ceffictents owe conbinuously Neaying- So, consider TH 8 a hemegencous second order (Creor recurrence Yelation fe, | FW) - fF MAY'- fF h-2) = 0 Te chosactentstte eq, fs C-Lsk BO Bs sob ove ty y= ‘ei . tens y mie solutton for the recuwence relations Scanned with CamScannerfede e(B)'+ BCE) To caloulate «, B! : let neo > fede <(Or BLD 5 OF + B @ | tee net @ pole e(eB)rP('SE) | > .-+ «(ub®)+p('=8) > lez LOt@)! «('=®) (se j D Pre Kr ~ hr Bd DS Ls Bd - > “x-l es eck “= 2? & n nw : = wf VAN A/G FO £28) + EUS) = b “A “ww lt Pa HE =» fird= L(p- 8%) WP enperteal Mealpte of Napithe 1 Unelexstond “the expertnnencts purpose | Decide on efftetency metic! M tp be measured & Une) measurenren unit (an operation count vs. atts, 3: Decide on chovactertshits af faput some (ths a gy Prepare a program tuplemening the allgpvittsm or He experimentation s. Generate a comple, of taputs- o- Run the algorttaam on the senple’s fopuls & red Lhe data observed. + Avolyze dhe data obtained - + Hapstlbrerte Vicwalteationt There ae by. petrcfpal vartekions of algoritaen vtsualteaction — : Scanned with CamScannerip gtate lgorttlnr vesualteation Heck . e Dyworate algorittnn Visualizabion , also called algortttann animotion: / Ly Tn Static , pletures ore taken tudo conidartion aT Dynawic, abgosttherte morrents are considered x The. case com be vealoulated: & empertcal analy SBgoathente hoay lenear way», Conver ‘ous. «There ase seve general scules fe detewnining Ue. runing time of algoniben : & Leops wr ily Nested loeps , ee eo | Wb Guseciclive statement - - Wy Tf -then- elses ¥ 9) Legoatthertc comple sty igumnenct ! (s) a votd Function (int » { int 1, count = 0; fox (fe1; Rican; HY j count ++ 5, fl Tf we observe cavefully , the valie Of t ts multiplied by teelf th the condition - Thtktadly 1, th dhe next step I=, and’ & subsequent steps f23,4 and £0 on- Let us assume Hiot the loop & erecultag “K times. AE fh step , P2k omd the condition ts Kew SB Kath “Total time = o(ve)- 3 vos \ R void function (Ot wn) { : wt t,5,k, comb = 0; for (few, y Peeny i++) Porljeas jt myetny Salo | Scanned with CamScannerfox (w= Ly RSENS Ke k*aQ) j count ++ 7 Bs for (t= Yo} teens 4) J} Weis loop & executed YY, Hees: fox Jes je Mae=en) Jape [Wks loop % also executed “Yo times. for(kety) Reenz k= K*R) J I Wks loop % executed log w +fmes. w. Total we = Cx etx logn < O(log») 3 wid function (ext 4) it U5 Kk, count 207 for (aM, y leans tet) for (jets j Tir) = NTO oe > Tin)= ae shi _. aah => TM = oo foto Tin) =3 TC) +) [is The -for loop thovedes for & tives =e ott ts dor the th condtttow]: Backword sulastthution! . ane | Thh)= 3-T(Ys) +) Ti)= 3 [3-7(09%)-* J +) Tl) = (2) +3 +4 Tin) = Sf -T(aye | +341 C2 ot tne} Te) esters) + S484 | Cet amey vat pote Cely ofes aay i vant & times J Th) = SE Teh) EEL se) TWh) = aN TORS T sey : . [es for 2. =a =) “e a Mat : w (RE) OGD]. Hs Tene complexity = oa), Scanned with CamScanner vxe Ontb = 2% 3 a Beste owe: De & a cstrouig let. forsee approach, at sobing on problem, usually. dtrectly baed om Ny problem statemenk & ao es of concepts Pvolvredt * _ ! Selection Sort! : oe oP 8 os aS be ent mitre Tt; ee ;4+*) if : afil < amt] mines x Best cose! sue ; ® Avexage case? a j Ey Hors cose: OF Scanned with CamScanner* Bubble socket j swap(alt] , almed); saa LA * TE fam Soploce valgorttows. So OC) Fs j cit: Teo to mr?® do mtn i foo CCn) = t= ee sv [ke nit) S a 1 Fo a, iy Fe t0 etary = Ol) for So tet to ot oe = ols tH ACES < Afewte] wide PT swap ALi] and A Cmin J / 1 Corals Teh] ia > ie 1315] EE Bh 4p t{s)> © SZ Oia 8 [sTa|s fate] £ YZ Space complextity et) — 22GE) we VG ') ae n(a-) va \ oye file Scanned with CamScannerS4teg Te sort uv elements be vequive ei) parses, Beudo cde: "for (207 46m1 9 S4 coe he mtay > alse) 0 temp = ALES? ALS} = ALE Afg+u) = temp ye 3 5 on wl c(i = Z\ = ne wz) “wu izojso ; (so a ce ot) * we Best case: SLO). be space complentty :O0) mm Avexoge case: O(n) xT fs alse a * ie case: OC) ; Paplace algorithm Assignment * (4) 0. Given numbes ove’ 13,", +, 8,9,2- — Selection sort! posiit=o 5 mine on, ge 4 ~~ atyt a>u & awe jo wat 542 afile afmiuy > afa}< aft] sawin ep Sow =ay yes | af3}-< afetl 3 afat 8 afay afst # 13<4 (PF) | mins a ; oa) > soap lat, afmins) vrs mint =f ° 212 AS => l\altjuls ale | Sorted pot | passa i faa 5 mie, j=3 atjt afah win jf} 2 wine 3, 324 ats} < atm} > alat win ej Demush , jes afj} < abe} = als} < af[4],2 13<9 ce) me 4 min [ot = swop (ats , afmins) Ce see > Celelela{ nfs) | sorted port 1 | passiS: (24; mine 4,5 = alsd< alert} safs}< ala] > B<' (F) mma 4 a> mm = 2 ‘ Ke 3 4 s > isteffulel | w Teas ts the sorted oreroy - Te fs obtothed oftes Therocting rhe le ea)” — Bubble sort: One| 2 3 4 S Bb\ul+ys aya Pass-t: T=0 % 520 aj] raters eafosz aL ssl (ry swap (ait, als+}) a => [welselil2] = 5-2 w a(st satsed > a{tt rafal BD swoop (aC33 ,af3 +4) 234s > [wilsle[sla) 25-2 afi} >afstl] > ofay >afays Boe (1) Scanned with CamScanneret soap ( af33 ali tN)” > 2 alii sa GiHry sofa} soley 182% een al5+13) ~ > 5h afsi Sofie > afar salsh 3 Ba ™ swoop ( ali} ,af3+'3) i Cees oftes i poss) | pass-a! fats jaa asi >afi+s) aalss >alad Suse swop (alis , afjett)’ a - elves Te = yet : aft} sagjey > ald safays wes (D 3, afs+0) : a > sa afi safse wafad Safay Sourav swap Caf} ,afie!) : > zeta [tebe] => ps8 afilsapiwu 2 alas>atay > 1 >a lt) swap (alit,af5+t)) > aarti S34. a{ij palit} > afet sats} o U7 CF) o 1.2 Bb Ss 7 > fa[slefal ls] CAvoy after a pass) pass-S i fzay Jeo afsjras+t} Sales >altl +,4>8 (FP) => yet afyysafsi saltd also 89 ce) prea ~ as >ald 4} aafpjsafal >a >a(D Scanned with CamScannerswop (als, of +) | Ba fa : > Glaslyn 3 iss a(stratit) Safst>alat sae! ce) > j2h ; afi} pafs+t) Safhl> als} 2 u>i3(F oy 2.3 4 ks. > ey ap ala] ula] Carey after =™ pass) Pass-4: t=3 5 40 5 afsd Safety Sales aly 2 F> 8 (0 = jest afi} > alse > aft vafay > 8 > 2 OT) sroop (af 33, afj+ty> => S138 ali => jr als salt Sas > ats} > 82a (© => 323 afs3 > alist > ofa} >afhy PIU cP) => 524 ais} >afit3 > af} pats} on >B CO ° tz 3,4 Ss > [sfalslaln el (Away after a pass) Ress: t= & 5 je afss Safint > afedsaltd > t>2(D Swap (afi , ofits) oes) = 3+ asd yalset}> afrdratays 78 CO = 522 afiz>afstd > ala} sala > 8>9 Ce) 2373 afs3 yatsrid> afapoalss St? Ul ce = yeh af4t>absety > afhd safs}> >a (F) Se ks © [pela i1e] (heey © sorted) Scanned with CamScanner —NS Me fal Seach? Th lis ve “ose ppheg to’ fed the dlemenk by seachiig each ener | by acts ttnear search- To search \B iielolnl ls Vow ‘ Bement ts found ok ‘oalion < 3 TS search 4S - Not fet Peeudo code: ox Cleo) tems tei { if Cali) cordate) 9 U pettp(telement fared fai); ; break; - , pues r “bo. | end mee eine *TL & the wodifred code Fe; jused, for vistque| clewends: Gf some clowients, are pnd on simple code & used: | ox (i=0; len; int) : i (ofits =dated, ret etanend ford 7d” i, ge * Tone complext-ty " torvst cose = O(n) 5 Best case = LC) hay cose - Zall cases = 2 ot wo: of eases me G = a fog Case ce Ov). © dyed Scanned with CamScannerBd a BSbieg mratdaing + @usider an example T= AB ARC ABD A P= AB => ABABCABDA AB AB AB aS x B ce AB AB Aigortlbon Bruteforce SbfigMatch (TL, wt Plo. mt [input thn array Of on dhrargcters & arether 038044 | A wm choractas: | Youkput: The brdex of x Chosracter Pr the text | matching gulasttug ov -1 ff Search %& unsucrersil fox To to nm do : Tk m(nome dE = Bw -3+0) = 3016) 2 48 [ompatsous 4 | : | Scanned with CamScannerlig Apply Sequertial search on 19,23 45, 36 38) a4 assay Of elewents and find the 60. of oe needed to find clemreiit 2\ and 4, Sols Sece alt te clemexts the army oe. ' urique’, we con i ode tex: pseudo caf ce [sf] <] sf at | 34'} & dota = teo , aft safod= 19 afi t=data 3 t+ tod Macks 2 ef Ve as afty| = data sit tea, aft} s afasq4s aft3\ sdata » i++ t=3, oft = aS} = 36 afisl edota = Ter a afk =a8 ais, data = i++ ‘yes , olf} s afssia aftj==data = break: | » Blebent -fodud ot? 5 postion :! th data = 44 Teo, alt= afov=9 afidpc data a tt ta ats aft} sar afisls data > tht fea, colt] = ofa -as afis| sdata > i++ Scanned with CamScanneroie3 afd safsy=36 von en Re SA) afi3!=date & +t ish ,alitd = afky = 38 2 oft =datai = TH+ ° | tes afij= a[s}= al f S| data S ++ ie 6 aft] safes 34 | alt3| data Tarelling salesman problem: Teidévg” short a) Scobie ; a, est pets by Viking’ all cib’es One abd agat apdig book to the f&st tty. oe s 7 i a Problem: Gikem ia’ set! of Fem ttl, wets | 2 cach: Déteimfue the no. Of tems to felude. be) S collection co thal tte total serait & lass tan d | pod, Ho gion lEwit & the cake i. optimal. Scanned with CamScannerkDivide & Covguer: Fireh ditde the given problem a set of sub lems. Solve every, problem Fda vecuasvely. trd pat together Le solublows of the subpolloms to get the solutton to the hole role, Merge sort + De keeps on .aplititig ox ancy Belo y elves unltL a condition fe met’ whee ce try t perform meigesor: ow a subosmay Of size, t fey Pox And thom 8 combbares thre mdividuol sorted sebosiay Wto berger arrays util fhe whole array © merged, Frokem | y . Sdution to orgvalL problem RF 2 nh 13 fF , B\ eg 694 cosh Ay tt HIB cosh 2 9 +44 849-30 cost 29 + 3 * B44 = 24 pe] casts Vt S+ S46 = 26 cost = 9 + T+ BT I= Brox cost = 9 FEE 1G Had cost = aLE+I +4 s cost = RE G+R*V=RS : ceb'c VESTS AH=AMG cogt 2 VE T+ABAT =20 Scanned with CamScanner—Feva fa qost eo ge t+ SAA = QBs Oe ZR, 4,d,'7 cost = Vere eS UF £3, 2,47 costs, F648 +4 = 3,1,4,a> cost = F4+6 4846 23,41, > costs tH yas tH = 2 £3,2,4, 19 cosh = ee BHT HAE, . <3,4, 1, 2> cost= ++ west 6 = as 2354) a> cost =) t+ t+ 8+ : LH, VR,B> cose SECTS TA = 3h <4 3B, R? cost= @ 4 ot [+6 =als 44, RU 3> cose = Btht orgs Xo} <4, 2, 3,\7 cosh = B+ At tt = F-Le) <4, Bt PR> cost'= @ + 34 54+6 = QR ee pcos = 4 4 BH BHT = 26 ® The Dhl solutions cre either wEnkenuer Bs wakmum cosk Bey <2, 3,4> & <1 4,28,3>- 2 Exomples of génvex seb ond now —comvek. seb shapes . 1 (@ Convex sets + Atl requis ce Bk Gs b Non- Convex sets: ' Keke) RYE we concider avy tc pots P4 eadtde the a the lune seqraentt Jotbg them shouldy't ony Of the edges uvdess tt te the edge eye Such slapes ore Convex setselapes: Scanned with CamScannerBs. Mexoe sock of a3), (2) 4S 533,36, 81 18,24. fds Deide avd Conquer: 1g, §8, 23,2, 33 Ry AS , 81- : 2. all tre Howree Cases 16! * Teme complexity - 4 O( ten) ef Cutogu) , Blvtoqn- Scanned with CamScannerBtBLO6% WOOF Fee) 4 Y des t c Rsesack: 00S ahcu tn ayn portition CALE, UBT + Buick sort (kU) ub) Pivot = a LAGS ; Le eeub) me “loc = postition (Abs) 4 Buicksort (A, Ab, bee’ i)y while eee pak) | Bude sort « (Rylec tt uy tay ho 5 4 ; set ata op + { Soa * (tag)? per fabrsa53)4 5 Soap (alist, als De yp vehe a * Tere Complentty > Best ond ao i 9(Nlog N)- * Woesk: O(n): : * Berry; Search: Arvay should. be. sovted. Reudo cade: feck Bevory Seach: Ca jn, data), » t L287 aAznli; fest whvle Chev) * Teme omples' t tte hex . ; OClegn) * t at sl a wehan (el; J else th dada < afmtdy) we mid -1; else ; Cemidy i; Lovehan -)t } ; I Scanned with CamScanner« Bray fee troversals: -> Rrecrcer (Root , hep subbee Righh S-®) > Tr onder (L:8:T, Rook RST) > Bt dder’ (Ls T), Rat, Rook). Assiqument +(2) ‘ UE te ger ciample stow each teyetion 7 qpiick soxt by taking pice as ie ond last cleaments ‘6 w\or w |- sols GW Prot as widdle eleimen Rstr fs0,5=t gy es AS GE ae B1qaeaad atti afa}=7 > 9 (&) | g--3 soop( pet, af33)2~ i . 6 3 {4 e@2 i q , wc = Bss-at t-0, $26 pivot = + SE ea See oe alti al63= 4 >4 (x) (84) soap (alt3, al}3): Scanned with CamScanner™Ee — 3 Se S 2 VF Ho war! at : ’ ie}, Bot =t a eT o 4 4 Us i afisce pret e ee . Cees s Ss.) al33 spot s | J--5 O° s fass-3 T= 0 aft3<= pivot alsd Spivey» Ht; * gett BY Gb 120, $22 | Swoop Fa : Nid (ep i tet: a{ii P fot dss; Scanned with CamScannerPass-s= tel jas | prot = 4 afts pivot erent i a J. ce 3 4 Q 2 t24) $e 3 B-4 sucap (pivet, AL83)7 Cte 5) as. Loin i 2 By a 4c «lee =3 afi3 <=pivet af i3 > pivet tat is, a 3 i. i S--3 Wess (855) & stoop (pivot , a[33) x3 ve Fl PEcen | Oxreoy fe me [Ol ge et Aes ee Pfe[s[4|s lee ‘9 | 2 Rad post “oxdex tf 'pre ovdex tee, 44, 1B 9, RE, BO ,lO8, 360 7 Sd Reorder : (Root , Lett cub tree , Rare sub tree) The. iwosy tree fs: The post-order is: (left sulobee , , Regt subbrce, Root) te; , 2E,1B, 108, 360,180 599 Scanned with CamScanner; Re » Me ultltetlon of (aaa Rrlagexs: For ony pate of bvo- dit numbers a=ac, end bbb, chek& | product “c" com be computed by re formule : eS sawb «610 “ et6 tc; where, C, = a,#b, | (1 Whe preduct of 1. thae ford dis : (& he product of their seconel lgits) C = fara, Ce,+) deste) Coe" * PD tettonyly, *H Con qi, extended tp n-digit 7 aac 2 amie ''( 0 16 Mea) 4 (bch eb) arb) 4) Carley to * b 10 2 O10 Se ctor cy * Sheassews Moki wuttipltcation: we constder 8 wmulliptiadions 8. general matric muttipttcrtion - But that com be veduced to a ual strasens wotrtx multiplieabion- # closest alte! Nan TW) = © (mleg'n) — vorwally TM) = O(log) — teak Noox's Reovex ull problem: : i e Cort thy) = otwh) - geverolly T(n). = wth) < worst cose Asslqvewentt : (8) Tne complertty of wullliplication of lage | integers by beacktoord sulastibitton. ) Spe ithe recurrence for numer of mulbiplteations mtn) be R- I Scanned with CamScannerRo & gven as Min) = SMC pT Pox, net o> Md = 4° [2 multiplication of w- digtt wunloers “requires 3 multiplications of Mh - digit numbers J Backward Substitution: My) = 3- (V2) = 3{am (oy,) | 2 Smlyp) [oath abstehaion] = Swbyo3 ait =o8 i om (2) J as 22 JE (ye): [es 4 subsstiheion] Elly after k eves) mtn) = a8.m('Y,5) Por solving tt, _. ne ak. 2 ma) = 3 m(ty 1 Ce mtd 2th => m(n) = 3 - an JiThe wor of mutliplicabins Ml) = x = Min) = 32 loge payer ae Lf hsea ele Se: [mend a3 wi : Crest = 18H a. Teme complextty of strassen’s waltx bey backnoasd substthition: & Leb the thre Complextty ey Th). Tk bwolves F wultipliactions of wy, watvices; —_ Scanned with CamScanner~Hand addition ‘Of worices. So,me teanctonce.' welation can be horttten asi 1 Th) = T) + Ww, ne! fr ned 3 THE ‘ Bockwsaxd » substitetion : rn) = ene ow aT = after, F ee +e ya =i by Tod ease G te Se) i ; : i [ tal afte bee Eat) «Sp i ale) a = Foe solving | t, consider ne af 2b) = 2 aT) 4 [eas er y- <1 > Tw) = FW! + [ee ol 3 Jar ce’ i Stim) -% + Gu k A winreS aT A, log tt DTH) 343 2g TH elk le5 Cilegt= ase > TH) = oo 3 Tine complextty of closeset pote toy bock- ‘ad substitution: Ar Let the time complexity ue Th). — Scanned with CamScannerNowwoally ° the vecurrence relation = given as Thy) 2 ati) +n+ nlogu 7a! Fx “=4 0 TCE Bock wooad Gees TH) = alate T (Oy) + "% aw te3%,] wt wegen = TOs eee wlogyy ant vlog. BO Aker 4 ‘| ' \ ‘ te sulostituton) a Cy) nok - -1) elles egies ~+ log Celgene za STK) + nk enrnf leq 4 a \ fe : 25 . : =a2Q° +nk — ei = Ke 2 TUM). Sone nee Dlegn be Dleg?| . at TC hee) + nk ant nk leq = nlogat wood Fev sclvig , consider ana hy; Bt) en-T(Hy) + nk- —namblegr—nlognr SS tog? Tn) e Wt nk—K4vblogue onlogn + ele )goo D> Tn) = wk + niklogr--nlega + lis) lege PTO) = vlog? loge + legs Cag Ntegal “Re log) au P Te = wilegnys mageCled- Magy ITA S O(nlos))| Scanned with CamScannerEe we constder -rtth wespect ite Y-axis fs" | Tla) = RT(Ya) FW, WEE [ee med Ted) Backoard substttbion: ov Th) aprirey,) + | +n Soh ae Oe toys) at th > Coates Cay = QT (Ve)+ n(2) y . oe x [ace + yl + 2a) wae es 2-1-3) + Pye an eae) (Chaban i | Cally after k tenes) Th) = ar(Y,«) - kn by: Fox selving Consider akin > Th) = ak TW) © kn Tin) = a TO) + kn - Tey= ay + kw ota = ake ku Tin) =n + nleg i “ae [ TH) 2 Olnlege)| go : Decrease and. wer: ble Consider the Pastas. Sed fied the solutions to-thal frstances,lober Be sclidin tothe orbjtval problem | te solved. | Scanned with CamScanner* Sometimes, ‘catled Jas: Puoremental opproath. ir { There ote 3 wejor vostaclions of clecrense —omd_ \ Mex > ' a 5 — decrease ly a constant (decreasing. by out (Ameaay) > deerese by a constant factor (dareastng by ? Saag wre yerteble size decrease -Cstze xeductton vonfes from Fey sees) a i supe Gey) ate ie ) ecighhal prot: % Decvense (by ene) & conquer Facholque Pebey, f D ‘ PY” YW evend ive ae at ee j oO a [ers & wis odd \ i mao. Zoudtiow Salo “4g Decwase (By bel) & congue ‘elton ” Padku2que ental potter] oe eel & Lx dor vosfable ste decrease fs fading a of, a wmbes: qed ws = gcd Cy wlegn’ « x Thsertton sort: Cousider the ov of elements: L oO t Gq Scanned with CamScanner ~@ [at] brs el Te) “190 i a [nls ! . - ¢ lu] ts) ay tf lo j wel 1 Unsorted ‘Lompe € ( Sttbs ae fle, onps 6 ( een Os ofa fu lsat jasper fob i sorted | unsorted temps W ) | \ 6 [a \nj a} ahs sorted a ned fempa ; [ea] 14) Bl alar rorberiio Hl sorted: Fumsorted tempat rie [e Ls) i | | | “hed ey Lytton: | Bardo cate; - for (C24 5 foams pf temps oli; braved jetels while (520 kk aL rtemp){ . ab+ealjss- j--) v o. ‘ - Vit * Best’ coe 000) | & [toweb a oa i coses: OW): | “Scanned with CamScannerofj+3 = temp; Assignment :(q) , boot ra ls Trseclion sort 1 Bl, FR, (9, 2%, 6, 18,45: nos 6 . Ss. oh. 2 3 6 oF ot, [2 [ade arf |iafas || Bus-t: sovted | rere ; tei, tempzaltd salsa. oy, jei-t = 0 (>=0> ae ali} > temp = afod=8l sta(D |. ofs+ ae aie 2 ols : $2.2 3251 ee > albJ= Led Le 7 ieee aie FR ‘ rd 81) 19 ras Be onortad | Poss-at eS isa, temp = a Lit = sirsgle get-t-t (>= alitstemp » alt eal > talt afset}calis S ofateafy-8! Ci--7) 420 l>=0) ry? ofss > temp =aaloj=taria (rh : cals ots} Salid=afoy=tR Ci--)) ge altemp, balay =81>at (1) afjet} safj} > afaj=afass 8! G--») =1(>=0) 53 satep > aft = wad at (0) ; ale = alii s aft = afit= mR GD J=e(>=-0) |. . als} >. te~p > afoj= l9 sar CF) alitt} = temp > ee at ° C2 3 i 4 steel (tH nN ‘Sovted i tnsorted fay, temps af idrofaj= 26. =i-t=3(>=0) ala Shemp > afay= BI> se (0 alitJ=alj} > afal=ofst-ai G-3) j= 2 C>=0) j 5 als} > temp => alas tar ze CH. : ] | | afetycaljl +S alfa} cafay= AR, Ci-s3) ¢. ben les o) af33 > temp => afd= 2% 536 (F) ae Aik > otas = BG Me ’ eles] ctt+) he 4 Te Ics, temp = apiieafsss 2 Sef-le4lve ©) all> temp Safkis i> sloielt) AH sal} > afstealaj=at G--7) 523 (220) yey ( 19 [a | a6 \tR a Sected in af | 2 Scanned with CamScanner33 > temp & af} =a2 >18(T) alget} = sali} 5 aay = ales = cy Cy--5) $= (s=0) ALi} >temp >afade 26 >18(T) 7 alg+ih=als} afas-afal=2 | G--) 3=' (> =0) alys > temp > aft} =at> g(t) : aie hafj3 S afaysaltteat (U--2) J=0l>=0) ; afis >temp > afdj.= 19> aD off saljd = aftt= afese (3--) je i (Xo) salg+t} =temp : ? ei Pope) | Ve SG ] 13] ta] ax] % |aaler [as] tie) socked. 1 uncoched Poss-6! : t=6 » temp zalttsafes=4s jet-l=s (>=0) oes >temp > alst=31>45( efsrij-alil > afeseats}-381 (f--3) &3=4(>=0) . afi >tenp = “olh}= Favas(T | alse salfs > afsd=alajeta, L3--) j=2 (> =o) afis > temp af) 36 2 AS (ED Sofjrt} step > aladaas w. The sorted anray aS 5 SEG oh 2 2 & : [e[is ie] , Scanned with CamScannerNOY DY Depth First Search: Ht a traversal. The graph: should be dérected & way Covcboie caples - Te te Ue fastest seach edhegjie: we wee Be aaa) Stock, Pe solving ths i Z @—XO—©) Back tracking tecbortyue fe used t& DES: We use | ® (e—_ ff) Pre-ordex fh DP Bree: | b+ obphaekent. Guilt s push x s ripush levdnemaale fom se + push C (no new ede com be a Hy i | | | YL Ss] cm) vistted from bb so pop) *pop © (ne node db visited) r push d (neo wde e & visited) * push © (wo Meo wode visited frome $0 Pop ee a b visited so, pop &) a * Pop S+ (no new vode aan be | * i <\ a CGoels tracking) + pop > _ oro : llc Teleff ‘pep f ws ytithed = fe, b,e,d,a,f} Tet Comple f HB iacoms OE C) — Lebel Neck OW) ~adtjpconey wedi Dice can represent the geoph ustag adjacency” let WW acljacency wobix. S : | fe pteral an PS | [b boar bh ae 1< |: ef Te | ld | : | e ‘Ly | It} ‘ Scanned with CamScannerOK Breadth Fast Seaach: Tr ts a grape mavenal itdetgue tot uses queuetriroy uses level onk SRA BES Bex: bree: i re ope < alpha Cetical arden ae dequeue oO % enguare cements visited: from a. oe | dequene b & enqueue hetb, 3 | depreue a (e\g|—_] > \ Hehe e . deqete $ | GL ea “Tene completes ode strilag to DFS ¥ Gpolegtcal ovderty + (Source removing algortur) % Tadegree - No: of cxlges tbe vestex: “t # Outtdlegree - Nov of “44 from the vextex. 20 a. IL) i 4 ‘Removiug Le clemerts tlh iuclegvee “ol kw | worth 4 Be der % callecl to eal | voting rem the ox 6 callecl potegte sorting: \* poetd 6 © ~ alee, S 6 Cage 0 20 ia 7 Q & Delete Co Gr Jae Delete G, 1* Delete Co The solutton ts [a So 03, %, Lesh: for topological sorted order , re qeaph clould be d&recked - Acyeltic : Scanned with CamScannerme conept of rials bo - back alo, we, ad de — we edges. ‘ ac - forwoad edge Cnet pee és fe - cross edge Coot ote he = tree) Assiqument + (10) DFS ond BES Shad aang gov: kb Aplabetical order &%. considered: “DES -, Depth Frest: Search ( Stack), bog PUSH a dt PUSH b doPUstLe ww pore wo yD BIT 7 7? a ae 4 {| co $ BI. - iB oo tee [al [o7} [eat a i wi PUSH Fin POP F. Willy FOR g ti) POP ‘ls WPOPé) elete[Hls} * a” Visthed . nodes =] 2, akcas}. WPUSH dK) POP d i ‘BES - Breadth First Seavch ( Queue) i Bqueve a. Sfef cea 1 Dequewe a & enqueue bic. & 7 | moree b & enqueue eg. OB eieqare Scanned with CamScanner = 7 ehwe Depeue © kemueve f NS TSTEL Dequeue = ora w Dequene S| T= p= 3 wy Dequene 4 Hf WW Enquene J. ‘a= wo Dequeue d cot Bi: Nphobetical ovde« ts concidexed - . pES- Die Fivst Seawel (stock) © oy alee ) CBI HE a o & ‘a Pustt b_ tiv, Pus ¢ dy PUSH d wpe -\ Ve ~ PRC pd wy POPC 3 ee ; lw pastt eww P wid rh de lew por bi) POP oO wily POSH f Gv PoP fF Uw Vistted wedes = f2,9,d,e, 6,0, \ |. ees - Breadth Fist Search ( Queue) a | | 6 a 16 Enqueue jy Dequene O Bemquene Aste iy Dequeve b & enquene C Woe 7 Scanned with CamScannerno Degpeue Co Bengrene ch: w Degen db enqueue 9° yy Dequeue 9 & emqueste & wil) Dequene- e wid) Baqueve: + (9 Deniiie f ate VSbed nodes =fo,b, 49, 2/F5 , | ee tteletal problems : (Peretishabions BcoMkstartions) + Solecon Bolte Agorttin Chey pots) 8y Didentity De tesgast Mobtle component t8; | (A mole 4 te the one leat tae | ~ eee crvalldy to. Aself-) yo | » Exchange we wilh the. eget oefpedat ty Re to 1 wohicdy te fs potstiig. : a bs, 3) Reverse the. eeealios of oxKo19 oh olrec» age Heb axe greater Low “k fs Giron. weber te 486): ; ode OB a Place the oxvows and fulloro abe stops: ee GEES (while ompes,6 3 ke 6), FSF C Echorge) hive HES (re dat & gueter ten k) ~ 465.03 ie SS Cwebtle comp. = 6 3 K6) ! “SHS (Exchange) ! THE (No deg ts’ greater “Hon 7 ~ ng iy. ETE (weblle compe 6 5 R= s) : SER (Exchange) 4 ) CEG (6 & greater Hon b) ~ 654: ©. PEL (wolile J 26)" k2e) sey CExchouge) ms OF TNeo dark bs! joel on ka Scanned with eeewir? eeu "SH. (Exchange) ' .ere Cosel t greatex Won &) ~ S46 © Rg orton ge tevetuoted as there is ho vebile co ment: ‘ The total pexm dios ane 6 ¢ [they Oe {456 ,465, cas, 654,564, seh, * Lexo. Lc ovder algoctten * outcome ot perendadion as 12/324 if wet, ge to: steps dai . for c= 2 to) total count(al). , gorerate” pom Or yrs he by following steps’ b,Sean. “he dgth from vignt to left kind fad comsectetie pats such that a nl) | step-3: Stop | Wi The pernutetius ave {ast nes, S46, sch, c45, 54 he pevmutations flat awe obtakred from the lekogeaplic onder algoviten awe abooys present fe as a ovdex (@ Mmevesst Order. ; ; “The total permutations sstll be ey wal! to total curt a re fey oI- Scanned with CamScanner| Ressquenent (01) 4 Lad alll the pesmaestedkoss formed fro ‘Phe die § of %29 wing a © Bhuson Toller Mgodles? | a) - aye (robile comp. = 77 (Echouge) (No digit fs greater thon F) - gat (enotile comp. = 97 k=) ‘ (Exchange) c Cte dgjtt & greater than k) - BET” STE (wobile comp 28/97 eee ape E 4 Ea 8 CExchay 2) _ 1g Ss Cho dij te gels ton #) a j ». Las (mottle comp: = 9 7 RED 6G FT CExcharge) st | ZS Che digit ts greater Hon epee 9 ST (mobile comp. 8 * k 28) : a SS (exchayge) | SE (a fe greater Hoon ky) - 18st | ef 24) 3S at ae re a7 <2 4 Sh cot ct cop cot a L-01 Dh-Ot dy ilo more wekile comporentts , so Hs dexmbiated! etal peswtctoctions ave 6. They ove ¥ { 4289, 498 (948, ABI, S14, BEY: | 4 | wy Lexographic_orlex algo ben: Here ne3 ,and , | otal count (nl) =6 ° Tathtally o=1, | Stopol cot sues 2 pt +39 (cts) step-a' "C238 ; i 4849 [ a - (8,9) 3 meal | w w=4 . f | ay 18 ¢ [ tutexchavge AX] oy 498 ( trevenstug over | ow Rat 498 Casts) Scanned with CamScanner”a *O@= 3 ot98 L Paty - (4a) p mest ty 38 tw 89F [icterchange ak xy tw 8F9 — Lhicreastag ovlec] w Pit BET Cc+ty) 6Ceh & 6 3ta [Re - (4,9 5 meal i 229 iy 89% Cirterchange a & xJ (VBtt — Lihevensing odexd w Ret 894 Cc+4;) "CeSs- b Bat CR&- (8,9 7, ™=13 th LF wast Cwdechage a kJ te N8 [irerensing order J w Ret 9B Coets) ‘caer wate (Pete -(4,8) 7 mal wees j Weagt — Lirtexchage a & xJ qs — [trcreasig over] © Ret 9 et Cott) *c=t (2) Sepa: stop “The pemnutalous are f x99, 498, BEF, BT VFB IB. we "Recrense by constant factor Mgovtthen: : Boo search : The consbort factor heve fs lg’, =u) { Q2sta_ abo (130) me m2; apt 6 S20 | Bompape od ¥ 3 ton | toe as sy) ROBO (HtOhO) | , ect Solution 20204 L040 +130 a ata; f sobs? 3as0 — nen; _ 1 Josephus problem: “he recurrence \elackions & even: S(2k) = ajW-1 w odds Tlaeet) = a+ Scanned with CamScannerrn”, am. Monpule a rnedian and whe selection probler: } caiculate he medtan & one he key clemed | y et wot equal devide % ‘tnto a ports Cleft & i faut. side of median) and then compose wth the | veroiintg elements : @ Cr isie) ° ny 3 uw Ss GT wedions O$8 2 |vs| sa Siofah=3 #4 | gred = otf 2 Losj= 0 » afoy=1#4 : i ejpwed= 4S 24 = afay=s 44 J be Lz ass =A = 4 Chey) found . Quick: select: TR ts the combiration of gquick t and. selection: ie aa dhe $e omallest wo: be the eel «flels sly Peck sort the axroy ustig, qpiels soxt : +) 4 [x0|-e| 3) 13 fella FAY swallest element position = S-1-= 4 e afad = 66: ey ‘Searching and tusertion , So. berosy bee "Interpolation seasch ¢ foray should be ee so Mey tems sorted array fod) a wetfoely soled Won untforly sorted) & fe) Cotttegage, & sobs kt! Be 4g ae Ps s334 Scanned with CamScannerAssfqumentt: ay * | Reset peasaxtt reultiplicadion ab sh My ‘NE | 34 6t | Ut (By (8-5) 8 268 (+ 134) a S36 Q Lor 1 2144 S BUECT = yw FURY = QAtB | & Josephus problem for. 6 n= (even) 2 Jes = awh! | / Geulate 3(8) > Kah | Sly) > k= yi i > Sle)=aj&) -) TC) = a jl~] > 38)2 ame, : TE) = afajoy-1] -| ATW =2ktet StH) = ald-t=1 | ® © ON Q. , S > @a os Re ee @_@ © dy w= 49 (odd) => D(akxi) = a(iOs) +1 Cateulate Sla)—> R24 = ajtH)4! = ace le3 see é x“ oe _- eet Scanned with CamScanner gwe SGdexpole lation search: Goustder the axoy (foray) Sorta) (le ]*|sTe $ pos oO FH SAS Leo he Sx 24” : coach eleowee apaset , alhd=6¢ , Ret te eee ) 7 Talks Vaile S204 [wets 23 posttton of we BB. alss=4. Qousider the omay (oom -ertfornal’y sovted): stellate rr a 4-6 Leo, has oor ae alhs= Ket “s' be pes: of = x93 Le Ch- SS NS [aig 8 Jp = e-']«c5) ot Se SL aS S= e+ [i > ral 2 se pash=r 5 aehtr Noo , tet &=3 , hes, %=6 aft} =6, othg=t > S23 +] igh > Bt gh sass , postion of a=6 fs 3 => aLsy=6- rp aealss , problem fs solved. Slt avpafes @> Lestl hb “Ip ac ee mon-unigorly sorted assay with 1 st alefters # Baeveased 3 t pp arten : |= [ist . As| Tal wa, io. “i gs afaser, afhd=2% = = 2 ive ss o4 [uh 2\(" #, = beds 4 afsjealth=4 5 x>apsy => hestrlsQ2 ,hes : aftten , afhs=at Seaet)7ueu Xo 2.2, Qat- Ser) \ of mal ts a. Mot 2 cose > ee oto eon= wndfdealy sorted) J * Te untfovenlsy surted! amowy fester poledton. seach & best & foe non- woos corte! ones bitrasy sent & wostly used. oe ; + TR btrory search, we well seardk vot postetou but . Ms fcberpolation, search we will go wuh de | FGenexating subst (last topic fa combteatortal probs fa . = Poser det coudoiis all the subs of ater seb > covtaius 2% clenot Teme, complexity — O(2%) - : Com code Mois deffer by a stigle be. #6 wed fo memory representation ke every pttvg wessoge 4 Scanned with CamScannera hopes ; Trans fe and Unique element ww vane CON > Mede frequen cy of elements fn weedbibe acon}. = Searching Problem C Binary Search) : Astorert : as) | 4 Compute wode of the amay i 4,3, 2,21, U1,4 using preatt oh Geen ancy TES a ale a] 4]4] Arrows after sorting 2 [4] EI [S147 > Ap. “3 Here n=8 ico, wode frequency = ° Rusd feet) 3 Oct EM) 2 runlengih =t ; vwwolue =A[rJ=Afo}= 1 ote srusnlenglh > orLe= (n-ct kk A[tt unlength]= At 4<=2(v) 45, seunvalue ~) > rwlergth = d41 =a ue or | "Tevuntength 5 oF ade Gr) kh Minwaloginfe re | RL EW L=wnalue () | Drurlength = art = 3 | E 1+ vunlength 3 043 <= (n-1) && ALT + rumlengthy= AL] | B<=tlv)> a= Yuwalue (x) Scanned with CamScanner Problems gaston ceBH lrumlength > wodefreguercy) > (S > 0) -tue wodefrequency = vunlength = 35 modevalue = vunvalue = 1 7 Te f+ wumlengthh S043 2 1-3 Rss-a: feom-0 3 3224) > sunlength = Ls runvolue =AfiS= ALBJ=R: + f+ vunlength > B41 <= 4 Ke Afttrulergthy = =WUnvaly 44624) AfaJsacal(vy > wunlengit = Sdti=a + te vunlength > B+ ace (rd Mh Afievuntergit] unl, Se=4(v) . AfsJe 3S = (x) 4 "Ylowlength wodfeuaney) = if (2>3) ~ follse Tale vunlemgth » 342 = les | Rss-3: fe=h-0) > ses¥ ly) | srmlength = 15 rwsolue = Altl=alsl ea | ett vunlength BD SET2)- false | fettrurlengh > st > {26 / Pass-4 1 tc = Ss 6<=t(vy | Srwunlengli = 15 5 vunvalue'= ATCT = Aled= 4" + t+ vunlevgth > 641 <=@-) LAC ATE urenghfenael #<=4(Y) kle> 4=4 (4) > vunleng th = L+i=a tte xunlength => 64a s= (1) B<=t(x) HFbewlength > wodefrequency ) a tf(a>d - - jee Ta ttwemlegh > 6+a 5 i=8 (on) vetun modevalue, = 4 5 [Hada eT], Mode tapamneyi= 3 ' | Scanned with CamScannerBe Gaausion alternation wicttod ! He wf! perfec | Pre opecdions and convert the matte Belo echelon form» LE is usecl for solving system of {ereos equations Neither + Foxword Llimiuation pe tet ton do afi mt] <—b[tI Jougments wabix Te A to nt do [on] for j IafpOotvors, UJ] ptvetrow LUx=eb py cure y Urey > She x Twesse of a wobdx: ACAD / iA] jy, Detemivont of wate: IAL, * Rallanced search Frees "AVL, Areas: The height at ony Atree should be ether 1,0, +1: Orebse the mice % unbalanced. I Scanned with CamScanner vode Cousideved fm |tod “dl Stegle R- fs . Stale L~ #| “< A) 2 qe i oy \ Doulle Lp -vobation |) \aftad ie-vobatton te becomes ew) Dude RE- A | then R-vollten te pegpooved 1 Node ott left child. ts given ve & seight cbt Ne. No. denotes the vumbker of cbildven: Tr tad | node-3 hove! 3 let altlhen 60, sa & inl & te | bee depth & consideved. Leer J | 1 Balaurci © Trsext A +» Move S + Move ¥ BRT Q: pe AY Scanned with CamScannerji) MM- Heap? Root ts thé wiinimune of all nodes. a Tnsexst 97, + Insect 8 OF eta . Swap eat @ a ® « SWOOP @® 63 @ w ates cent: Remove: Ure woot agin heapty until all wodes ove deleted. Replace root sotth ‘fast lecef « + Remove 3 & vepkce 36 Scanned with CamScannersoinateemen Ste -R ve 5 & replace 26 @® Keptiyig + Remove 6 & veplace aa Attex, heapifying + Remove F & veplace aa, — Hex, 2 @ 4 b2SW henpiyeg C86 ® + Remove 8 & replace 36 1+ @ Ate, g@ BS heapifying SEG. + Remove Q & seplace 45 heapifytg * Remove 18 Ae, AS QQ Mar P28 3) f « Remove 2 % replace 36 After | @ heapifytng @ & + Remove 26 f& Yeplace 4S Scanned with CamScanner- ie cae, oP | . Rewove 36 & Teplace 4S 3: @ ' . Remove AS : | qhe vemoving orckr of elements gives the sorted forme! 3,4 87 6,7, BU, 1B, BA, AE 36,45: ypattnalc divisions PO) = Oo: Fd + FD where , POY = polynomial /Uvidend | Ao = gqpottent : | fl» = divisox | <0). = Yemalider | | | | | | . 2 Ew yy ee abe £8 [REET HSK AS ay FICHE Cette oie F EL tS eT 1 Bway exponerati + G6 a POL of a a a +: dregs @) 3 ft ~Régnt Binary expowentication! (Agovitbun) Product Lircas Broyrormig problem : (Ust Stwpbex method * Reduction “Lo Grarh Cs Genk a paths to the given gang dehoce ; Exy state -space’ groph for peasant , roolf 1 9oet ke Calobage puzele- | Aessignarent (15) ° (Orbe the given LPP Ustug simplex webbed Moximize 010% + O0Fy +0032 f > vdhs ST x4 y4z = 100 {| ned £43 Zz oashty) where X20, YEO ,220° y het P= olox + C1044 + Or O32 + OS1 + OSA40S5 ST Re Yr Z+ OS, OS, + OS, =100 —Oo 3L-Y+O7Z+4 OS, +1854 OS, = © —® RA YrHZ +0814 084 15, = 0 —@® A Scanned with CamScannera. | ot top 1 ed o- ° 3 4% 0 2 00 90 0 SG-AA O10 OOF O05 0. O10 . \ T ctacomtng vartable)) & PR-3R Pa>e,-k, Table- as Rae Rok —— Sz oto OOF 0.03 O, O a Coff No yoe &° 8, Oto | 1 \ 01 67 0d OveR BP Aya OG? =Be0 : OO $30 QO HS.3 Obi lOO, ZO OF OF © OND aviboud4s ao 70:03 OOF 01) O. —aA( hme £0) “The vequived sduttons are ix 2100 > Sy=-B00S $,=-100. Substitute them ti! 4® © 3 weg eo The maximum volue P iis AO. 3 0-10(100) + 01540) 4 0% 'o3(o) fe lo. Dd State - ~ Space gor as ps, gj onde puedte.”” ob Scanned with CamScannerBE ye Space be Ute “Bndecoffn * Etthes the space complexity fs Breveased didder 4, tereased inmovder to veduce We space c. These ase Une boo vastetias | of spacel- for - are vowed 05: + fapuk evhancement — Pre: process he toaput (8 thy fo stove some Bfo) to be cued lalet Be sduteg tye Pretlen. (space complex ty tees): - Counkiug sods . — Sting searching algortttms, - : + Be sbauckustug 8 Boput to woke Be elements easter (Hove completly is lex) Nedlucé Weg Hime “complexity OI time complextly 2, omglext . tive ORL, | access | — tached Doe Radlexiug scheimes'( €q:" B-trees) S Gunkiig Hegr 9 : “Compaitson counktig soit: Ml the dled bide estoy oe Cuibtaltsed “woHO cowit Wo feker De allog ts Geremeuted based on accondiug Uf | The count of cach element af : ‘ | Bon eek Ye fae pee | dade i i 1 7 +s * / L | [eal a] 24] a6] bth... Dahtally 05.0, 40 OO = Coun | Pust® 3 © Lo 1, ogo : | pas at VER Roo | Frm eck, poss Peet fot ia Blo oY cusient ee pe S| oak 4-4] “mt & gas | fess Fo a. Be emp : facet Peal 3 SO a AK coum ober z es emer forcét =. = — wese oo 9 > tar] ealseta) | ts cnet | Wieitbukion counting sorts | Ger Consider Ihe onsen, — Scanned with CamScanner