=t Introduction to_ to Agorithn + Algorithm, # At An allgoiithn fs a finile set of instructions followed ty complete o pertfeulor task . Al Aigorithms frag some choractertsttes /criterfa « 1» Input 2 Output 3+ Defintteness 4+ Fniteness 5+ Effectiveness %Outpuls Atleast one 61) more outputs are produced . aiiginal output. 4-Eintteness + steps fn algorithm chould te countoble and should terminate at a pont. 5- Effectiveness : 4 produces the ‘est time complexity . = Specificattons_of an Algorithm + An algorithm con be described in many ways. we can use natural tonguage ‘ike english , Graphfc representattons called flowcharts , tout they work well only # the clgoritam %& small and simple . a Comments begin with // and continue util the end of tine. 2+ Blocks are indicated scith matching braces: Sand} A collection of Simple statements can represent as a tock . statements are delimited ty s. a-The data types of varisbles are not clearly declared. The varfable qibal or tocal 40 a procedure will algo be cleay from context. Simple data types such as ‘nteger , float . chas, ‘boolean and 60 0n- t-Tnpuk ¢ Zero @n move quantities ‘Uinputs) ‘tas to ‘oe given rar 3: Ocfiniteness Jn every algorithm Expected output should te equal wo |1 ap VGmpound dala types con ve formed with records «4s Example | node = vecord | § datatype-+ data -4; | | : \ datatype -n data-n; i node, * tink 5 } | 4 Assignment of values 40 variables { done using the assfgnment | Statement . (vorfable) + = (expression) 3 In order to. produce © There axe two poolean values tue and false - these values, the togical operabors “and ,or ,e not” operators 2,2,=,4,2 and > are provided . nsfonal arrays are accessed using [ond]. For and the relational 6+ Elements of multidéme example, it * is, a two dimensional array, the (i,j) element of the army #% denoted as AL?,j], --Away indfees start at ger0 3 General form of a While toop + while (condition ) do (statement 1) ( statement n) b As long as (condition) f& true, the statements get executed + when (condiHfon) becomes false, the loop fs ecited . \ a: Gieneral form of fox loop + for varfable := yalue1 to value2 step step do t Statement 4 statement n Pee ete geQA vepeat until salement i cConshucled 09 flves : repeat (statement 1) statement 9 until {condition ) The statements ove executed as long as (Condition) it false . The value of (conditfon) f Computed after executing the gatements, 10 A Condition statement has the following foums + if Gondition) then (statement) if (condition) then (statement 1) else (statement 2) tis Tapuk and oulpuk are Aone using the instruchfons vead and write nlo| format is used to qecify the sye of fnpak ov outpu quontities | = Time Complexity + she time T(p) token ‘by o program P fs the sum. of the compile time ond execution time fe aalled ime complencity . Bxamples > for (Teo i ten 5 14+) ane stmt J +o 4 ame Complexity : T(n)= nti +0 = antl + o(n) + order of 9 2> for (feo 3 fen 5 i++) aera fos jeos fen sit¥) ncn’) stmt; aka 4ttn)= ati ¢nintt) +> — = o(n*) “Tine Com pleactty = Space Gomplexly + The cpace compleccity of an olgostthm fs tt needs to run to complétfon . Grample + foxcieg fen 7 H+) the amount of memory forfeos jen 3 144) stmt 5 i b Space Complexity S(a) > variables used ane 0, {+0 they ove constant = (4) Bramples for Algorithms ih Agatti fos Sum of avray Elements fos Ct 0 ton-a , TH+) san text A(t] mu print (x) cu Time Complexity T(n) = ony *o(n) Space Gmpkity s(n) = 2+ = 0(n)2) -Algortthm for addon of two matrices Number of array elements afa-a} a{n?) for (i-0 ; ten , 144) 7 8 . or tan forjeos jens it) . | § : cfajl-aliglaainj) = + + | | | Tine Gomplxtty = Tea) = Oe?) \ Space compertty + s(n) = o{ o>) | | 3 Algaittien 4o find sum of natural numbers | T=0 3 cum-0 while icn) Sum = sam +1 Ve fey write (sum) Stop Tine Gomplextty + tU0)- 0(n) Space Complexity + Sl0)= (1) = -Recrasive Agaithm + An dlgotithm call ‘oy felt 5 called as recursive algorithm. | we The veaurston reduces the number of fnstyuctfons fh wu ‘Aigoritrm wo progam there ‘oy veduefng the complextty - | & Recursive algorithms are of ‘wo types 2 «» Direct recwssive | a” 7 2b tndifeck veeuvsve | resi whch call oy itself fs called Direc reenssive « AN aigort m which call another algorithin han & called. fadtied dlgurithm .a -—~ _ © 3 Asymptotfe Notati ‘These are the Short hand way to represent 4fme Gomplecfty . In Asymptotte notations we have several notations ike ik Big oh(O) >* Omega (2) ay Theta(©) ur Small oh(o) 5} Small Omega (t8) " SQ oh (0) ; Gig oh notatfon denoted by “0” fsa method tox Teprecenting the upper bound of an algorithm tanning ime. 4t 0), 39) axe non-negative functions , (0) = c®gtn) » x nd only FF exfets postive constants Cyn then upper bound fin) £ cK gin) . | © Upper bound Should always be greater than funckfon . a Bi - Omega. 2) : Omega notatfon Bs denoted by “2” Ps a wnethod for Yepresenting he lower bound of on algoritarn running time . © tet €la) > 9(n) ore 40 non-negakive funcking, -£(n) = c¥gtn) oe and only TP ex?sts positive constants C0. then tower bound | #0) >C® gen). | & Fetate): Tela woiton Te ded by “8: te 0 mad for vepreenbiag, dhe Tunaing time between upper found and tower bound . w Let #(n), gln) are too non-negative functfons thety exists tun positive constants ci and cr euch dat ae 9(n) 4 Fn) Tolal tine wequfred wo divide we problem Ph 10 sub prin 4 combining the solutfons into a single solutfon . (8) = The computing time required 49 solve small inputs - | problem of sige 'n’ toto sige of | € AP we want $0 ABide a “nyy’ taking (n) computing Hime to diide and combine the | sub problems and solutfor then the veourvense. relatfon for | | | Obtafnfng the computing Hime of shen fs (a) = a-T(4)+FO") ce relatfon fs an equation that ~The general form of Yecuurrence = ‘Recurrence relakfon * he reautren defines a sequence ve curstvely relation fs (n}20 +O a(n) = t(n-t) +¥ —t © Eqn® ts called taitfal Conditfon eqn® fs qiled vecurrance Condthfon . + Binary Seoxch At & an efftdent searching method while Searching the elements using avis meted the cements fm the array should be in sorted order. | An element which f 40 be searched from ‘the ‘Pot of elements gloved, fn array and searched element fs called key, element. An Anis technique fret find out the yniddle clement 4 [in] then thee conditions need to te tested with the ey element. te 4t key Key) deo, hen-a , mids (0th) ; while (02h) if (key=* AlmidT) velurn mid 5 if (key < Amid] ) hemfd-1; | se id | ' de mid +45 | return -1 ; | inary Storch fa_Reaurafve | RBin—Search (th key) i if(1==h) i iF (key == AL LI) return L; else velurn -4 3 t else t mid = [i] ¥ Chey = = AL med ]) telusn mid 3 4 (key 2 [mid]) | R Binoy Seatch (Ls mit, key ) dse R Bfhary Search (mid+1 jh, key )Tene completly for Btoary Sasch : T(n)> + (2) 41 Tin)= +(4)i+! eat ee r(n) = 7 (Se) +8 rr en ke ( log,” £7 (9) - o( 69") = Finding Moxtmum_and Minimum (4-=h) mox = min = a[ a]; E(¥eeha) i€(afe] 2ah}) max = afhl; min =afal; | dse max - aft]; min = afw] 5 Find mace —min (Ay h pmax, ein’) ete) sxeturn mox= min = alt]; else ff (4-=h-1) ‘ it la(slzathl) min =a 04; max= afh};relerrn mmo , enn ¢ else min = ah]; mat = a(t veturn max ,min ; else g Nid = / Qth mi ( eh ) Find max-min (4, mid , max, min’) Find maze niia¢ mid +1, h, max, min) if (aCmax a] kE(S)]aan x om ap. act) . k [r(&)}4 2G) 7 PET} eo OH) = agr-1) F gn+o a-\ > Logn-t +t ay =I > 4 n> at TH 0(0) w= logn = Merge Sovt : The Merge Sort algorithm orks by diitding the thput anay fnto two halves, sovting each fal recursively ,and then merging them ‘back tegether. The merging process favolves comparing the fist element of each fylf ond selecting the smaller one to te ploced fn output array. ‘This prowess fs repeated util all elements ‘have ‘een placed in the array | Aigorithum « Merge Sort (bh) if(ich) Ya ie Merge Sort (4, mid) s 4 (4) Mergesort (mid +1} ,h) + (4) TwowayMergeort (2,mid yh) + ae b j Tine complstty for _mergesort T(n) - at(-4)+n T(L) = 27( =) +o r(2)- et Ca)+$ a ra)-ar (+2T(R)= ar (B+ @ t(n) - ar (3) +k = nr(t) + logo +9 = ner +nlogo 2 nt nlogn = wn n TWoo-Way Merge Sort Algorithm « merge (#[ 1,811) 120, j20 ker while (== f 4€ do ==j) Ye Uati2 0G) yesulk [ett] = ALi; te fet else s vesulk TK4#1 = BL fli jejtts at (ice f) for(: sted, sT++) yeoulk (E44 = ATF 5 els if 2 tor: speds speH) yesult (er + 1 2B1j1F=: Tine cempestty for Too 1044 Merge Sort * Qute sont Qutdcsort te a senting technique that fas the ability 49 beak a Massive data anay into smaller ones th order to save Hme- dere th the case of quick sort algovithm , an extensfon orrvany fs divided into ton arrays one of whfch has values tess than we specified value Say Pivot» the pivot value Ys ‘tofqger than the other. rove all elements Smalley than the pivol 40 the tft partitfon and ermaller than pivot to The left paritfon. 65 30 45 80 e5 «60 55 50 us ® @ o 6s RS as ed eS 60 65 sD 40 ® Ww Ww Sus go 8 fe ep es ae 5 tO w G) @) SS ei Cy an iGee ies ani OnieD tiie. 70 wo WG) co ous 6 Ss GO eS BO HH 7 oO - 60 us 50 oF 6S 85 80 +" then + Quiclesort (A) § foe fer ,f=ar-'> pr OG utile (FeJ) § acd € ale) } i445 ; | ce (aly) > aCe) f feos 5if (ie 4) § tenp = ails atid = «UY aly temps else $ temp = Ale di atel> a Ufli atl = temps } 3 =ye( ) 4 : yealol, tl, jaos while (721) repeat tay until it (afilzv) “repeal ger ze (alley) 1eCfe 7) gwop ( att, atj1) : gwoap Calf) y sehr js Quvcksort () — ttn) T otecgenyy a p( Joh) —n 4 guide Sort (15-0) 9 4at(t Giksov t (Ft) h) j (2) 5 2. Reumance Relakion + t(n) = arg) + tla)= 0 (nlogn)y Ti win orst case Hine complexity occurs when pivot Clement fe um (er) maxtinum elements of all the clements - ‘his’ con be pHs represented as clement =I Ss n-2 3 [o-3 = (Y= ne ta) ete) ee +1 We Ienow that Tin) = 14 24----40 Tin) = a(n) 2 yn z Gomes os “We worst case Hine compleatty Tn) 7 O(n) 1 Time Complesthy of Stkcbton sost = o(9*)eS SS Sees 3 Strasen's Matsia Mult plication : mens Tmabite Mulifpfealion to ate Aide and Conquers approach ae ‘the matstic multiplfeation problems - The usual tabi ‘plkatfon method mult*pies each rows with each column 40 achieve malate . The Mine Compartly taker by thts approtch fs OANA) since TH takes tio (nope to mmulkfply - Stassert's method was Introduced to reduce the fe Compertty form o(nd) +0 O(le9*). Agorithen Mutiiptication (41 8 19) $ iF(n==) , sets On ® but 5 else 1 (n==249 Cu 2A & Bu + Ars * Bat Cae Aut Bat An * Bo Gu = An® Bn + Aa2 * Ba Cor = tor® Bo + far * Ber dse ¢ vtptenton (4), , &% 1%) Muplnaon ("% » rn) (or) rAulliplleaifon (qu Gi Va) ¥ Maldipheedion (fe, Ba %) ulAfpicabfon (Ann, 81 Ya) + Multjptitabion (Aa> Baro Jn) matipttcatfon Cn Ba, Yo) + Muldtprtcation ( tha, Bra %n) Molbiplécalton ( B21, 8, %) + Mullipticatton ( Ar.) 82> 2)Reaamance Relatfon : eT (2) +n* (8 = o(n2)) Tine completity + o(n?) Cu = pas-T+V Cu = Q4T Car = RES Ciz= par-Q4+V Formulas : P= (An +Ar) ( Ou + B22) @ = Gu Aas + Aas) R=Aln (Gn - Bra) S$ = Aar( Gn - Bu) T = G22 (fn + An) U = (Aa - An) ( 6 + Bir) V = (An - Ax) Ba + B22) » Matite mulAtplicabion T(n) = o(n?) Strasen's multiplicatfon Tin) = 1 (2) + con® Tn) = of a*')Reccurence ‘Relation ne Complextty s(n) -1() +1 olloge) (0) - 8T (2) +2 o(r) tia) - aT (4) +0 (log 6) a(n) o(nlogn) rte) at ($)+0 fiverge case Tla)= T(n-l) +0 o(a®) worst case Sb Seleckfon Sort ttn) = r(a-t)4n ct Strassen’s mabix tta)> 4 ( 2 ) ie rnulkfp\fcatfon % mab odditfon a makotx multiplication