Design and Analysis of Algorithm (IKCS-503) Bloom’s Knowledge Level (KL) | | Course Outcome (CO) | At the end of course , the student will be able to: i co 1 _ | Design new algorithms, prove them correct, and analyze their asymptotic and absolute runtime | Ke, Ke and memory demands. J Co? _ | Find an algorithm to solve the problem (create) and prove that the algorithm solves the problem | Ks, Ke | S05 _| correctly (validate). | co3 Understand the mathematical jon for deciding whether an algorithm is efficient, and know Ka, Ks. L ‘many practically important problems that do not admit any efficient algorithms. CO4 | Apply classical sorting, searching, optimization and graph algorithms. Ki, Ky | Cos _ | Understand basic techniques for designing algorithms, including the techniques of recursion, |" Ke, Ks __S2? __| divide-and-conquer, and greedy. DETAILED SYLLABUS 3-1-0 Unit | Topic Propos I _ oO Lecture Introduction: Algorithms, Analyzing Algorithms, Complexity of Algorithms, Growth of | 1 | Functions, Performance Measurements, Sorting and Order Statistics - Shell Sort, Quick Sort, Merge 08 i Sort, Heap Sort, Comparison of Sorting Algorithms, Sorting in Linear Time. "| Advanced Data Structures: Red-Black Trees, B — Trees, Binomial Heaps, Fibonacci Heaps, “| a eo Ge 08 Skip List) j Divide and Conquer with Examples Such as Sorting, Matrix Multiplication, Convex Hull and Searching. IL | Greedy Methods with Examples Such as Optimal Reliability Allocation, Knapsack, Minimum 08 Spanning Trees — Prim’s and Kruskal’s Algorithms, Single Source Shortest Paths - Dijkstra’s and Bellman Ford Algorithms. | Dynamic Programming with Examples Such as Knapsack. All Pair Shortest Paths — Warshal’s Vv and Floyd's Algorithms, Resource Allocation Problem. 08 Backtracking, Branch and Bound with Examples Such as Travelling Salesman Problem, Graph Coloring, n-Queen Problem, Hamiltonian Cycles and Sum of Subsets, 5 on Selected Topies: Algebraic Computation, Fast Fourier Transform, String Matching, Theory of NP- | Completeness, Approximation Algorithms and Randomized Algorithms os @ scanned with OKEN Scanner(Dict s. ia ee ae jets = FugoRttH = a =n ca Miros hn valk \a_d Lag autthm: sisi casts ell dip at of -stehs in Solt, naa i pautioulan. aera a hencréerstics oF A LGORTTHM = _ As An Al then aie asc finite: itu: hut op Incbuuctior 2 suchith ett fui ee —pttialt pattieulan. - a pid tite Te alnuig stuibeuth, mut eal = [1a Tai An Aljudtims ahnand douse woo ou NU but. Showld be fini. ho» 4 Jrputs ras tn lp AnAlgouithmn must give atuaat i gi elt me fluent od input vate, FT = —— Dyan Each "step muck be cheat ; Digan nd pero —— @ scanned with OKEN Scannery 8 Phir + fitenus ie “2 citer eat Td ety Zt umber “54 —stps | : Liompuing Best Cate, wanst Y. wha’ ! ae and” aera core iz @ scanned with OKEN Scannerptthald mas. “Ww Shar to > Thr Shae -tompberity of a Progam ist, com ouunct__ tho janetc Junto LamUtiont ft watt aa cdtiion dn sve a inulin = h ut sii i lable, folentifen. 9 I | | Sp= Space dupind upon instance chanactewisties. ——_Thisa_vawiabls part ua share. tt de pind tpi patton — -————puoblum —tinstonaag, Tins Compact = i @ scanned with OKEN ScannerTe olgin) iy and caly oe itonsii Gand OS ft) :6-496n) NS he. 2 C30 1 ee | | [sl de sepetinents thd vuppusthn i ph 8 uot an—Algarit SN Cte: tpigy @ scanned with OKEN Scanner7 on thst omy Ai (rap) 3 assy Notation (aN Notation) = ne dad tn bao (Gt 4 wth =eulst Ja constant _¢_ Ji Such that = _ : Soho Leeann function that calle at Lt cole talon, ountinadton. wenditoa Calping pat) | oth uate, an our _folliued Lu cmsiue spac ngetcia may on finite. Loop - _ 3 an Recusuaion ene function tala Hitt» 0 - __ 8} pavidm ction nwt ch » Code we rt bry hep, thang: — > Recwiuin i basicaly Solving big Problem ae small ham. he _ | Recwenen Ta haus an alpen in ac | Reewusien tivo utd Ahn we Convent: aati Be a mn then this equation: yk Rn pwn y Pema Aad Recustneince spuadlan, @ scanned with OKEN Scanner08 piusA wan) “<— ctiont ta at 5 cpeeint (not diay aah ss PureOne 1) | Recwouner Rulatin [Tiny = Tina) t 2 L Ouray —_! : a Tiny = Tin-1) +e | dee = z ine sr = coe pe ea en aS ae rae son @ scanned with OKEN Scannerith Tabac anal 4 Method. fox Solving.» ania gdivt Recuniu nice L-Equotign — i 4 we Saket Substitution Method regi oe 7 = Er ee @ scanned with OKEN Scanner> dn this__puoblum is divide indo a’ Subprobliq tach of Aizen uchnt a. _y._b oH __ postu adie te : (The trop dlivtdtng. the i J juablems asad tomb fr f a os -¢tn) = Theos = win ¢ @ scanned with OKEN Scanner0) Ya 8, than Tom = 6 (nine) 9 iL a= bS then (if Pet, then Tenye 0-(r Pe tng’ nr) (b)_if P=-1, then Tthi= 6 (pe. Loglogn) (Of P Sal then: Tony 'p CnteH%) Bi ib acpk ~ oi) P20, then Ten) ='0 (n*dog fn } Ob) i Pb™ such ‘thak | 9 >3" Thue Time 6 (tet) 2 Ten = 6 (ny Tm nrc ge @ scanned with OKEN ScannerTony = 6 (Ney ana inlet id ‘2x1 yp eat 3 Carb) and (Pop t> | ae Tin = oth a Jay Mn) p= es = egn} ql : Moy = 8 (h Login oA sf jf rey : ———___" noe @ scanned with OKEN Scannereen hae, mre ——— At sakisfy iu Mactin lant 0 OBE Auch H23t C444) and pro then » ‘Tony = 6 (n¥bog"n) Tone 8 (Wilog?n) fontngens tt Saticpy tha Wailex Conditin, — I ack Auth 2t* “Such thaFe a> ra” | >i @ scanned with OKEN Scanner— Tem = ar (2 Be er ae a=3, b=38, k=i, se _dt Sakishy pth, Mast Condition = ! Q=bK such that 3=3' oe an Cure pirat aw feOo 0 >-1) Ten) iS 6( pe. Log? tn | ; y= b(ndogn) Am. | I Guest Recurence Equation ~ j , “Ten)-2—Ten=1)t nt | Q=1, b=0 + Ke fo Nadker Theos bot fe O>4 . do | wnditio « ay A Fala @ scanned with OKEN Scanner| Ton) = © Ch? togtn) hig ae} Huw Ws 3, b=3- kal 7 popiin ut check, a>pe : an . ha - a 3>3” Bt sd @ scanned with OKEN Scannerthin we apply Matis theorem Ttn)_= a(n i) L 2s Toe 6 (nF) eo — | Tin). s.0(n) . Ans.. | Softo-) _HMian as 2 wea) am pe To = 27 (2) + neg (Row as2, bea, ket, pent be the eb 7 ] : gen ZI win {p a2 A | 2 ——~thin__ehice _Ps=1 “£0, weiek ta apply Tends 6 (nS *Log.tog n) i Ten = 0i( nh? Log bogn) ; | Tin= 6 tbogdnghd Ans. selos|o3. i ! i 52 orf{ nr) n3 Sut Feet (ot a — @ scanned with OKEN ScannerKynobt sidd os ate cont S88 <9 4 Tas aT cd fsb BUUH f eh ere $s) LHe @216, b=4, K=9. = p=-2 : use ch a E | i a=b* i wi da eustt EF vats 5 Wa t* o. ompd f_- | {6= 16 > (en herb walee BE) p kt f | Qrdzdin | roy Tin = O(n Ry I Tind= 8 (pe) 3 sey Tin) = 6 (rn 2244) ‘a - a bh mel i | Tin)= 6 (rn?) Aas < ee | @ scanned with OKEN Scanner> {nts ttuthod. fiw Sees the fou _one__vasntable anol __Substttution —__ DVanen vy ‘he Vawwiebte inthe voan oth. en equation x | Substitution Mithood = Ht Se 5 Li I Forward ——Backworeat Substitution ~ Substitution aS (i [stonmnands* Subst = od Poanand _Substituctic: —£an__Are ps Pees > Soin Bora —_Substitutim Method we Dh A0UHIO 04 Stes tn ena tn and — ee — a aft a a @ scanned with OKEN Scanner—_Tteattion_ _Muthod Os. | 2 Aft aans Bespin sana Be co fess duwor, oy thy Aaurinling ML Ons i ety thy fn work - eal Tin rae > Ut n= ot | rhs Tene) +4 if nzo bet” Ten =Tth-19 t 4 Ton) = Ten-ayt £ Tne Ten-2) th tv pe Tenet) = Thn-ayt t ‘ €T(n-2) = Ten-3) t4 “Ttny = Tone2ot2 2 en Tin- 3)t 30 hue er a Tra TOR SS od i |, Tons. T(n~ Kot aK . hk D ~ Tem § = Thr tn Tin) = Th) + SS @ scanned with OKEN ScannerWu Typo f 2p Pat Teta { Tm tn, ip ne Teny= Ten-tyt ne put nance 7 — T(n-4) = T(n-2) tn-4 Ten=_Ten-2) += )-n iL A Put m= 1-2 sin GC . 7 Tm) = Tin-30t 22 Tim= T-3)+%2) + (n-4n T= Unk) + [n-k-D]+ HRD] ke m-K=0 ; ; —— iI Nek Tend = Ten-w0 + (aes 1] + [oii] gs = I(n)= To) + it2¢ ee OTD Tay = f4 foto REA n(nt) AP raps nny mys it is Tens 2. =n AE ter dock | Ta= 00) Hg @ scanned with OKEN ScannerTm = 1% + Ke Olek Ay | x : 2 | ak=n “Teny =F [ f] + —-Logn'c = | Hatke Log both side | LF tog.2S= Logh fo A= CF} wkag.a tog Tinj=_Tlt) + _togn:¢ _ Ke Aon —t _ ae Teoh Lind = Bog fins aol ta > RO StF a4 @ scanned with OKEN Scannerea renege Toe forte} Fe 98 a on ii. @ scanned with OKEN Scannergo(09 23 - oa © Bw =F ¢nj = RE) = = nt | oat (Lp Tent Fdn-) Ter-a)- 4 = al ; (nde nnd T(n-2) = _ Sea ra teat ncoNT (= NCn-t). Cn) /Ten3 eel. TE G¥ 2 #4 [> Tien (h-) (nay n-ne) Toms (n-L) (n=2) ah J “We know tho k= -_ n(n-1) (n-2)#-..-- 3% 2% 1 | ate | $0. F pipet ; — [| Ttm= O(n) Ans _ [= aS @ scanned with OKEN Scannerb (het =¢ Cr “ivy pod Fons = er(a)¥(B) ee® fone 8 rf }+ an> 4 ne a ee en ras ies — co n= eS Ant tant i po Tes eT Las Ln aan reps (be) Teste) T(t LD A Teno Tt nL —Tn)_=_ htt p3 = n> ny siege Tin) = O(n?) Ans @ scanned with OKEN Scannervo . T_T tT Ue n= l est kul fu Ttn)-= lst) + wogh: yy nat j \T 7 Tem) = _T(n~ 1) 4 tog Hp 2 Tin 1)= Tena) ie Loy en-tyy Taos Tina) Papin ty tdagn. = test a T(na= =a T Ttagls Ton3> + Log aor er eg) t Logn Tet a= ene 74) + log) Tenj= Ten aE i CS) é ogo gtr 4) tag Timd= The Kt gin (jeu) t Log [n= Gay] + eas (k=3) J chs. Logn {i het neko { tee Tin) = Linen [Rant i + Gog [w-w42] Lag pls Hts it Liog’n @ scanned with OKEN Scanneree Peso St gli is t 1093 +-Logn r Shy. 60), C L= sagt Ray = 8. Wagny Tine 1 tilog- (L423 ¥. en) Tim= 1 + Logon!) 7 = i " dog(n = ntog(r) 7 _ dmy= gi), t J ne = } | Tind= O[nlogin)] Ans. ae | = 2 dj pe2sn Co Rus. (n= aa pave J gi feo=2rfay +c zh >) POT (mT ee Tlie 4 6 | 8 oe Teas aTinyt te | 7 ob = — IPs T= RATA FCT FS, THIE A] TMM) # 20FC @ scanned with OKEN Scannerie | bea THM LaT witaite To tet aac 4 poe FY =creyT Fon)-< “935 cn 440 4 Tas PLD eR —Fers-s 8 (oe) A) =r | 7 1 7 Tins 27a) DE kk top tay Pee _Tim)y= bo naTeT Lign aN a | 4 i di Tin)= loge + Log ea lng.n Td = ban (a4 1) Tiny S dogn #3 C t Tass 2 yout Tin) = oF 2 ATF _| [Tons olen fat | Le | [a=tubnr, @ scanned with OKEN Scanner—Y. _Fouwaud Substitidion. padittlion tmetfed t- Sheps Dake. Yee warpage: eae and tnitrall ren dition a) Put $e uiiliadl condition in eg “ond. aah fo Repth 4 —usest She pill fe 4) Patoue SRA que path it_conmeit et ai sodden. js | Tm) = T+ 7 n= 1 Assume uailied tendilion) THs TOI +1_ oe : TO? Tlo)+l >TO= 1] —d) ee Ti2)2 72-142 9 TO+2 — td at soluee TC) neg” Li) {| T2142 = 8 : = I] PT @)23 i Tale Ta) t3= Ti +gslt2tas { T4)=T (ua) t+ = Ts)t te 1424344 i TO) (5-145 = TOPs = 14243 +4 +5= retro }o— — Easier alien sf nme) ny oe ue ee iT 1 bE - Finye—otn*) | ue Pall Palen — Ten)= (ni) /2- i a0 2 n(mijiz (ely TOs a Nt2 (69a at paar a i(2)]2 =! @ scanned with OKEN Scanner@D —Recwusten “Tues Mead t= cae | mer 2G) ye (Bent 2 (mes) T(n)=ar(2)4n>_ im “fade! 2° me Ce Jewel at (ye Cay Ce) Lo gall ns: 9 2 — mt TE ee Yor <8) 1 t aE pa 5 aa { 2 carey. fer9-2—m2f. —— \ on2)-shs— here) oft fan Cie 7] = @ scanned with OKEN Scanner