New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Miss Emery VonRueden


Miss Emery VonRueden
GPA 3.55

R. Shah

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

R. Shah
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 111 page Class Notes was uploaded by Miss Emery VonRueden on Tuesday October 13, 2015. The Class Notes belongs to CSC 3102 at Louisiana State University taught by R. Shah in Fall. Since its upload, it has received 21 views. For similar materials see /class/222862/csc-3102-louisiana-state-university in ComputerScienence at Louisiana State University.

Similar to CSC 3102 at LSU

Popular in ComputerScienence




Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/13/15
656 3102 Adv Dam STrucTures and AlgoriThms Analysis General Info Scope Tex rbook Assessment General InformaTion 39 Web page h r rpwwwcscsuedur39ahu3102 Ins rr39uc ror39 Rahul Shah r39ahucsclsuedu TAGrader Sudip Biswas sbiswa7lsuedu Office Hours Coa res 291 Mon 130 230 Thursday 1100 1200 Algori rhms amp DaTa STrucTures When we solve a problem we usually need To handle a problems every day Transform an inpu r info a desired ou rpuf Algorithm A me rhod of solving a problem using a sequence of welldefined s reps Data Structures Some ways To organize The da ra smar rly so Tha r an algori rhm can run fas rer and so Tha r real rime queries can be performed AlgoriThms amp DoTo STrucTures Ex Given a lisT of 100 numbers DeTermine if The number 54quot is in The IisT AlgoriThm 1 Linear Scan Look oT every number in The IisT Is This The besT we can do 7 LeT say we have few more queries How much Time do we spend for each query Can we do someThing smorTer SorTed array Say The lisT is sorTed and can be randomly accessed AlgoriThm 2 Binary Search If The lisT has 1 elemenT answer direchy Else compare The middle number M in The lisT Case 1 If equals answer YES Case 2 If M is bigger search lefT half Case 3 If M is smaller search righT half Is This necessarily beTTer Than AlgoriThm 1 AlgoriThms amp DaTa STrucTures BoTh algoriThms can be exTended To solve a more general problem for any sorTed isT of any lengTh and for any TargeT number QuesTion 1 When The lengTh of The isT is VERY long which algoriThm do you prefer Why QuesTion 2 WhaT if we need To updaTe The isT of numbers 6 Wha r will we sfudy Sfudy fundamen ral da ra s rruc rures and s rudy Their efficiency in Terms fo space usage query Times and upda re Times How To design an efficienc r algori rhm wi rh proper da ra s rrucfures To solve a problem How To show fha r an algori rhm is correc r How To analyze The performance of an algori rhm or a da ra s rrucfure Prac rice on implementing algori rhms and da ra s rruc rures and compare pracfical efficiencies Teaching Plan Par r I Basics Sor ringSearching Grow rh of FuncTion Solving Recurrence Par r II Fundamen ral Da ra S rruc rures Linked Lis r Queue S rack Tree Graph Hash Tables Par r III Graph Algori rhms BFS DFS Connec red Componen rs Shor resT Pa rh Spanning Tree Algorithms wi rh Priori ry Queues 8 Teaching Plan Par r IV Dynamic Programming and Greedy Algori rhms Par r V Tex r Processing S rring Searching Tex r Compression Search Engines Par r VI Advanced Topics Compressed da ra s rruc rures for Se r da ra Compressed da ra s rruc rure for Tex r searching Skills Building Abs rr39oc r Thinking in algorithms and efficiency Google DE Show Yahoo MS inferview ques rions IOI ACM ICPC Programming Con res r Questions Research in Do ro S rr39uc r ur39es Search engines Tex rbook lt3 References Tex rbook Do ro S rr39uc rur39es and Algor39i39Thms in C by Goodrich Tomossio and Moun r Some book in Java References In rr39oduc rion To Algor39i39Thms by Cormen e r ol Algor39i rhms in C by Sedgewick MIT Opencour39se Assessmen rs Mid rer39m 25 Homeworks4 paper2 programming30 o Project group 10 Par ricipa on 10 Final Exam 25 STudy Tips Have a fresh mind in lec rur39es amp ru ror39iols Don39T be shy osk ques rions Try your39 bes r To do every ossignmen r Sugges rion Work in groups To exchange highlevel ideas bu r Then do if sepor39o rely in The end S rudy Tex rbook and Try The exercises Mos r impor ron rly Have fun 656 3102 Adv Dam S rruc rures amp AlgoriThm Analysis Lecture 2 Sor ring Previously We saw Tha r if an array is sorTed we can search fas rer39 using a binary searCh Binary Search A i j x k midpoinT of range Aij If Ak gt x search in Alk Else search in Ak1j Bu r This needs us To sor39T The array Binary Search Running Time Tn c TnZ T1 d Solving Tnclognd AbouT This lecTur39e STudy a few simple algor39iThms for39 sor39Ting Inser39Tion Sor39T SelecTion Sor39T Merge Sor39T Show why These algor39iThms ar39e cor39r39ecT Try To analyze The efficiency of These algoriThms how fasT They run The SorTing Problem Inpu r A sf of n numbers Ou rpu r Arrange The numbers in increasing order Remark Sor ring has many applications Eg if The lis r is already sor red we can search a number in The lis r fas rer InserTion Sor r Operates in n rounds Q Swap Towards lef r snde 39 AT The klh round S rop unfil seeing an i rem wi rh a smaller value Sign QED kl h i39lem Inser rion Sor r i r 1 89436 gt 8 9 4 3 6 i r 2 84 93 6 gt 489 36 i r 3 gt 48396 gt 43896 gt34896 i r 4 3 4 86 9 gt 346 8 9 CorrecTness If ar39r39ay lengTh is 1 This is True Now assume ThaT befor39e kTh r39ound A1k is sor39Ted Then we can say ThaT afTer39 kTh r39ound A1k1 will be sor39Ted This is known as InducTion sTep The above is True because we Take Ak1Th iTem and inser39T iT in iTs r39ighT place All The iTems previously in A1k remain in The same order39 So aT The end of n1 sTeps we geT cor39r39echy sor39Ted ar39r39ay SelecTion Sor39T Operates in n rounds AT The kTh r39ound Find minimum i rem affer k lTh posiTion Le r39s call This minimum i rem X Inser r X of kTh posi rion in The Iis r Ques rion Why is This algori rhm cor39r39ec r39 Hin r You need To assume some rhing s rr39onger39 Than The fac r Tha r A1k is sor39Ted a r kTh round 9 Divide and Conquer Divide a big problem in ro smaller problems solve smaller problems separa rely combine The resul rs To solve original one This idea is called DivideandConquer Smar r idea To solve complex problems why Can we apply This idea for sor ring Divide and Conquer for Sor ring Wha r is a smaller problem 9 9 Eg sor ring fewer39 numbers 9 Le r39s divide The lis r ro rwo shor rer39 lis rs Nex r solve smaller problems how 39 Finally combine The r39esul rs 9 quotmergingquot Two sor39Ted lis rs info a single sor39Ted lis r how Merge SorT The previous algoriThm using divideand conquer approach is called Merge Sor r The key s reps are summarized as follows S rep 1 Divide lis r ro Two halves A and B S rep 2 Sor r A using Merge Sor r S rep 3 Sor r B using Merge Sor r S rep 4 Merge sor red lis rs of A and B Ques rion Why is This algori rhm correc r 12 Merge SorT Tree An execuTion of mergesorT is depicTed by a binary Tree each node represenTs a recursive call of mergesorT and sTores unsorTed sequence before The execuTion and iTs parTiTion sorTed sequence aT The end of The execuTion The rooT is The iniTial ca The leaves are calls on subsequences of size 0 or 391 Merge Sort ExecuTion Example Par39Ti rion 74 v lgtlt HL muL cwr h 39 E r I U 11 E Merge Sort 14 14 ExecuTion Example cont Recursive call par ri rion I inm v7ulm 34 muL I L I i x 1 339 Merge Sort 15 15 ExecuTion Example cont Recursive call par ri rion I inm v7ulm 34 muL I L I i x 1 339 Merge Sort 16 16 ExecuTion Example cont Recursive call base case I 1 r w w 1 1 s 3 1 H I l N 1 y x c Merge Sort 17 17 ExecuTion Example cont Recursive call base case ExecuTion Example cont Merge I K a I u 39I 11 a lt 5 Merge Sort 19 19 ExecuTion Example cont Recursive call base case mer39ge quot quotv x c lt Merge Sort 20 20 ExecuTion Example cont Merge t Merge Sort 21 21 ExecuTion Example cont Recursive call merge merge Merge Sort 22 22 ExecuTion Example cont Merge HMHZ 99 44 33 EH8 66 H1 Merge Sort 23 23 Analyzing The Running Times Which of previous algor39iThms is The besT Compare Their running Time on a compuTer39 BuT There are many kinds of compuTer39s ll STandar39d assumpTion Our39 compuTer39 is a RAM Random Access Machine so ThaT each ar39iThmeTic such as x memory access and conTr39ol such as condiTional jump subr39ouTine call r39eTur39n Takes consTanT amounT of Time 24 Analyzing The Running Times Suppose ThaT our algoriThms are now described in Terms of RAM operaTions we can counT of each operaTion used we can measure The running Time Running Time is usually measured as a funcTion of The inpuT size Eg n in our sorTing problem 25 Insertion Sort Running Time Below is a pseudo code for39 Insertion Sort Insar rion Sor A 1 forj 2 To lengthA 11 Compare Aj with Aj1 Aj 2 un ril getting Ax smaller Than Aj 12 Insert Aj after Ax Note Steps 11 and 12 can be described in terms of RAM operations Can you do that 26 InserTion Sor r Running Time Le r Tn deno re The running Time of inser rion sor39T on on inpu r of size n Suppose rJ deno res The number of comparisons in round j By combining rer39ms we have Tn c1n 1 c2 ZTJ The values of TJ are dependen r on The inpuT no r The inpu r size 27 Inser rion Sor r Running Time Bes r Case The inpu r is r is sor39Ted so Tha r a TJ 1 Then Tn c1n 1 c2n1 Kn c linear39 func rion of n Worst Case The inpu r lis r is sor red in decreasing order so rha r a rJ jl Then Klnz K2 K3 quadr39a ric func rion of n 28 WorsT Case Running Time In our course and in mosT CS research we concenTraTe on worsTcase Time Some reasons for This 1 Gives an upper bound of running Time 2 WorsT case occurs fairly ofTen Remark Some people also sTudy averagecase running Time They assume inpuT is drawn according To some disTribuTion 29 Merge Sor39T Running Time The following is a Cs ryle pseudocode for Mer39ge Sor r MERGESORTA p r 1 ifp lt r 2 then q lt Lp r2J 3 MERGESORTA p q 4 MERGE SORTA q 11 5 MERGEA 1 611 The subr39ou rine MERGEApqr39 is missing This can be done by cr39ea ring 0 Temp arrays for39 merging 31 Merge n1 qp1 n2 r q Le r L11n11 and L21n21 Copy L11n1 Apq and L21n2 Aq1r39 L1n11 00 and L2n21 00 i3J1 For kp ro r39 If L1i lt LZLj Then AkL1i i Else AkL2j j 32 Merge Sor39T Running Time LeT Tn denoTe The running Time of mer39ge sor39T on on inpuT of size n Suppose we know ThoT Merge of Two lisTs of ToToI size n runs in cln Time Then we can wr39iTe Tn as T0quot 2Tn2 cln c2 when n gt 1 Tn c3 when n 1 Solving The recurrence we have Tn Klnlogn Kzn K3 34 Which AlgoriThm is FosTer UnforTunoTely we sTill connoT Tell since consTonTs in running Times are unknown BuT we do know ThoT if n is VERY large worsTcose Time of Merge SorT musT be smaller Than ThoT of InserTion SorT Merge SorT is osympToTically fosTer Than InserTion SorT 35 656 3102 Adv Dam STrucTures and AlgoriThm Analysis Lecture 3 This lec rure Analysis of algorithms Gr39ow rh func rions Quicksor r Running Time MosT algoriThms Transform i npuT objecTs i nTo oquuT objecTs The running Time of an algoriThm Typically grows wiTh The inpuT size Average case Time is ofTen difficulT To deTermine We focus on The worsT case running Time Easier To analyze Crucial To applicaTions such as games finance and roboTics Running Time 120 100 80 60 4o 20quot I best case I average case El worst case 04 1000 2000 3000 Input Size 4000 PloT The resulTs ExperimenTal STudies WriTe a program 9000 i mplemenTi ng The 8000 algoriThm 7ooo Run The program wiTh A 6000 3 inpuTs of varying size and 5000 composmon E 4000 Iquot Use a funcTion like The i 3000 g buiITi n clock funcTion To 2000 geT an accuraTe measure of The acTuaI running 1 39 I 1 Time 0 O 50 100 Input Size LimiTaTions of ExperimenTs IT is necessary To implemenT The algoriThm which may be difficulT ResulTs may noT be indicaTive of The running Time on oTher inpuTs noT included in The experimenT In order To compare Two algoriThms The same hardware and sofTware environmenTs musT be used Theo retl cal A nalys i Uses a highlevel description of the algorithm instead of an implementation Char39acter39izes running time as a function of the input size n Takes into account all possible inputs Allows us to evaluate the speed of an algorithm independent of the hardware software environment GrowTh RaTes GrowTh r39aTes of funcTions Linear z n Quameic z n2 Cubic z n3 T n In a loglog char39T The slope of The line corresponds To The gr39owTh r39aTe of The funcTion lEl Cubic Quadratic Linear 1E1 1E3 1E5 1E7 1E9 I l DominaTing Term Recall ThaT for inpuT size n InserTion SorT 395 running Time is AN2 Bn C ABC are consTanTs Merge SorT 395 running Time is D log n Eh F DEF are consTcst To compare Their running Times for large n we can jusT focus on The dominaTing Term The Term ThaT grows fasTesT when n increases An2 vs Dn log n DominaTing Term If we look more closely The leading consTanTs in The dominaTing Ter39m does noT affecT much in This comparison We may as well compar39e n2 vs n log n insTead of An2 vs Dn log n As a r39esulT we conclude ThaT Merge Sor39T is beTTer39 Than Inser39Tion Sor39T when n is sufficienle lar39ge ConsTanT Fac rors The growth r39a re is E 3332 no r affec red by quotWear co nsTanT facTor39s or IE ear lowerorder Ter39ms g 1E IE 1 Examples 1E IE 7 102n 105 IS a linear 1B 5 funcTion 1E IE 1 105n2108nisa quadra c funCHon 1E1 1E1 1E3 1E5 1E7 1E9 n Big O noTaTion Defini rion Given a func rion gn we deno re Ogn To be The Set of func rions fn I There exis rs posi rive cons ran rs c and no such Tha r O S fn S c gn for all n 2 no Rough Meaning Ogn includes all func rions Tha r are upper bounded by gn 12 Big Oh No ra rion 10 000 Given functionsn and 3n gn we say Tha r n is1 000 if 2n10 0gn if There are posi rive cons ran rs c and n0 such Tha r 100 n S Cgn for n 2 n0 10 39 Example 2n 10 IS 0n 2n 10 3 en gt c 2 n 10 1 10 100 13000 n2 10c 2 n Pick 6 3 and no 10 1 Big Oh Example 1000000 nquot2 Example The 2 100 000 W quot100 fUhC I39IOh n IS no r 10n 001 10000 W x n2 S cn xx xxquot n g 0 1000 x 39 quot The above inequaliTy 100 xquot x39 cannoT be saTisfied xquot since c mus r be a 10 xquot consTanT 1 1 10 100 1000 More BigOh Examples 7 n2 7n2 is On need 0 gt 0 and n0 2 1 such that 7n2 S on for n 2 n0 this is true for c 7 and n0 1 l 3n3 20H2 5 3n3 20n2 5 is On3 need 0 gt 0 and n0 2 1 such that 3n3 20n2 5 S on3 for n 2 n0 this is true for c 4 and n0 21 I3 10gn10glogn 3 logn 10g10gnis Olog n need 0 gt 0 and n0 2 1 such that 3 log n 10g10g n S colog n for n 2 n0 this is true for c 4 and n0 2 Some more examplesBig Oh 4n e O5n pr39oofi c 1 n 21 4n 6 On proof c 4 n 21 4n3 On proofc5n23 n e OO001n2 proof c 1 n 2 100 loge n e Olog n proof c 1 n 2 1 log n e Ologe n proof c log 6 n 21 Remark Usually we will sligh rly abuse The noTaTion and wife fn Ogn To mean fn e Ogn 16 Big Oh and GrowTh RoTe The bigOh no ro rion gives an upper bound on The growth r39o re of o func rion The s ro remen r fn is 0gnquot means Tha r The growth r39o re of n is no more Than The growth rate of gn We can use The bigOh no ra rion ro r39cmk func rions according To Their growth rate n is 0gn gm is 0fn gn grows more Yes No n grows more No Yes Same growth Yes Yes 17 Big Oh ConvenTions If is n a polynomial of degree d Thenn is 0nquot ie 1 Drop lowerorder Terms 2Drop cons ran r fac ror39s Use The smalles r possible class of func rions Say 211 is 0nquot ins read of Zn is 0n2quot Use The simples r expression of The class Say 3n 5 is 0nquot ins read of 311 5 is 03nquot 18 Relatives of BigOh bigOmega I fn is Qgn if there is a constant c gt 0 and an integer constant n0 2 1 such that fn Z c gn for n 2 n0 bigTheta I fn is gn if there are constants c1 gt 0 and c2 gt 0 and an integer constant n0 2 1 such that c1gn S fn S cZgn for n 2 n0 little0h I fn is ogn if for any constant c gt 0 there is an integer constant n0 2 0 such that fn S c gn for n 2 n0 littleomega I fn is oagn if for any constant c gt 0 there is an integer constant n0 2 0 such that fn Z c gn for n 2 n0 r Intuition for Asymptotic Notation BigOh I fn is Ogn if fn is asymptotically less than or equal to gn bigOmega I fn is Qgn if fn is asymptotically greater than or equal to gn bigTheta I fn is gn if fn is asymptotically equal to gn little0h I fn is ogn if fn is asymptotically strictly less than gn littleomega I fn is oagn if is asymptotically strictly greater than gn 20 Example Uses of the Relatives of BigOh I 5n2 is Qn2 fn is Qgn if there is a constant c gt 0 and an integer constant n0 2 1 such that fn Z c gn for n 2 n0 letc5 andn01 I 5n2 is 2n fn is Qgn if there is a constant c gt 0 and an integer constant n0 2 1 such that fn Z c gn for n 2 n0 letc1andn01 I 5n2 is 0n fn is oagn if for any constant c gt 0 there is an integer constant n0 2 0 such that fn 2 c gn for n 2 n0 need 5n02 Z con0 gt given c the n0 that satis es this is n0 2 c5 Z 0 21 Big O and BigOmega Similar To Big O we will sligh rly abuse The no ra rion and write fn Qgn To mean 1 01 E Q901 Relationship be rween Big O and Big Q n Q9n 9n 0fn 24 Big O Big Q and CH Similarly we wr39i re fn gn To mean fn 9n Relationship be rween Big O BigQ and G n 9n ltgt n Q901 and fn 0901 27 G noTaTion example 4n n c11c24n21 4n3 n c11c25n23 logen log n c11ogec21n21 Running Time of Inser39Tion Sor39T nz If noT specified running Time r39efer39s To The worsTcase running Time Running Time of Merge Sor39T n log n 28 LiTTle o equivalenT defini rion Definition Given a func rion gn ogn is The se r of func rions mo I limpinf amgm 0 Examples 4n 0n2 n log n 0011000001 n log n 0n log2 n 29 Cinderella39s Problem You have To find The largest bol r and The largest nu r 30 Cinderella39s New Problem You have To sor r The bol rs and SM The nu rs 31 Fairy GodmoTher39s Proposal 1 Pick one of The nuT 2 Compare This nuT wiTh all oTher39 bolTs Find Those which are larger and find Those which are smaller 32 Fairy Godmo rher39s Proposal 0 z 39r 39r T 39r 5 139 TT Bo ITs BolTs I smaller larger Than LIT BoIT equal Than nuT 0 W o o o O 33 Fairy GodmoTher39s Proposal 3 Pick The bolT ThaT is equal To The selecTed nuT 4 Compare This bolT wiTh all oTher39 nuTs Find Those which are larger and find Those which are smaller A T39 Bows BolTs smaller39 larger Than nuT BolT equal Than nuT 0 quotUT 0 o o o O 34 Fairy Godmo rher39s Proposal NUTS smaller Nuts larger Than bolT Than bolT 35 Fairy GodmoTher39s Proposal 5 Sor r lef r par r recursively 6 Sor r righ r par r recursively M This is all of my proposal M 39 ll I A l39 O o o Coo NUTS smaller Nuts larger Than bolT Than bolT 36 Fairy GodmoTher39s Proposal Can you see why Fairy GodmoTher39s proposal is a correcT algoriThm WhaT is The running Time 9 WorsTcase nz comparisons No beTTer Than The bruTe force approach I Though worsTcase runs badly The average case is good n log n comparisons 37 Quick 0M 38 OuTline and Reading Quicksort 103 Algor i rhm Par ri rion s rep Quicksort Tr39ee Execu rion example Analysis of quick sor r y 1031 In place q uick sor r 1031 Summary of sor ring algorithms 39 QuuckSor r 39 Quicksor r is a I randomized sor ring I algori rhm based on The I I H I divide andconquer III E II and par ri rion S in ro H J l Y l H J L elemenTs less Than x L E G paradigm Divide pick a random elemenT x called pivoT E elemenTs equal x G elemen rs grea rer Than x 77 Recur sorTL and G I I I Conquer Join L E and G QuickSort 40 40 ParTiTion We parTiTion an inpuT sequence as follows We remove in NM each elemenTy from S and We inser39Ty inTo L E or39 G depending on The r39esulT of The comparison wiTh The pivoT x Each inserTion and removal is aT The beginning or aT The end of a sequence and hence Takes 01 Time Thus The parTiTion sTep of quicksorT Takes 0n Time QuickSort D Algorithm partiti0nS p Input sequence S position p of pivot Output subsequences L E G of the elements of S less than equal to or greater than the pivot resp L E G lt empty sequences x lt Srem0vep while SisEmpljy y lt S removeS rst if y lt x L insertLastOz else if y x E insertLasth else y gt x G insertLasty return L E G 41 41 Quick SorT Tree An execuTion of quicksorT is depicTed by a binary Tree Each node represenTs a recursive call of quicksorT and sTores UnsorTed sequence before The execuTion and iTs pivoT SorTed sequence aT The end of The execu Tion The ro 39 39 39 39 The Ie Oor1 42 42 ExecuTion Example Pivo r selec rion 1 7 V rJllt 34 mhL I U u a 4 Quick Sort 43 3943 ExecuTion Example cont Par39Ti rion recursive call pivo r selec 39 a j g quoti 115 Quick Sort 44 3944 ExecuTion Example cont Par39Ti rion recursive call base case Quick Sort 45 45 ExecuTion Example cont Recursive call base case join Quick Sort 46 46 ExecuTion Example cont Recursive call pivo r selec rion Quick Sort 47 47 ExecuTion Example cont Par39Ti rion recursive call base case Quick Sort 48 48 ExecuTion Example cont Join join QuickSort 49 49 WorsT case Running Time The wor39sT case for39 quicksor39T occurs when The inOT is The unique minimum or39 maximum elemenT One of L and G has size n 1 and The oTher has size 0 The running Time is pr39opor39Tional To The sum nn 1 21 Thus The worsTcase running Time of quicksorT is 0n2 depth time 11 1 1 QuickSort 50 50 ExpecTed Running Time Consider a recursive call of quicksorT on a sequence of size s Good call The sizes of L and G are each less Than 3s4 Bad call one of L and G has size greaTer Than 3s4 2 Good call Bad call A call is good wiTh probabiliTy 12 12 of The possible pivoTs cause good calls Bad pivots Good pivots Bad pivots QuickSort 5 1 51 ExpecTed Running Time PorT 2 Probabilistic Fed The expec red number of coin Tosses required in order To geT k heads is 2k For a node of depTh i we expecT i2 oncesTors are good calls The size of The inpuT sequence for The currenT call is of mos r Thei393ef4digW6 have expected height I For a node of depth 210g43n the expected input size is one I The expected height of the quick 0n sort tree is 0log n time per level On 01 The amount or work done at the 0g quot quot0n nodes of the same depth is 0n Thus the expected running time of quick sort is 0n log n total expected time 0n log n QuickSort 52 52 Ideas for In Ploce PorTiTion Idea 1 Use Ar39 The IosT elemenT as pivoT Idea 2 Process Apr39 from lefT To r39ighT 39 The prefix The beginning parT Of A sTor39es O elemenTs less Than pivoT seen so for39 Use Two counTer39s One for39 The lengTh of The prefix One for39 The elemenT we are looking 53 In Place Par39TiTion in AcTion before running Leng rh of prefix O 13782645 nex r elemen r PiVo39r Because nex r elemen r is less Than pivo r we shall ex rend The prefix by 1 54 In Place Parfifion in Acfion affer 1 s rep Leng rh of prefix 1 13782645 nex r elemen r PiVo39r Because nex r elemen r is smaller rhan pivo r and is adjacen r To The prefix we ex rend The prefix 55 In Place Par39TiTion in AcTion af rer39 2 s reps Leng rh of prefix 2 13782645 nex r elemen r PiVo39r Because nex r elemen r is larger Than pivo r no change To prefix 56 In Place Par39TiTion in AcTion offer 3 s reps Leng rh of prefix 2 13782645 nex r elemen r p39VOT Again nex r elemen r is larger Than pivo r no change To prefix 57 In Place Par39TiTion in AcTion offer 4 s reps Leng rh of prefix 2 13782645 pivo r nex r elemen r Because nex r elemen r is less Than pivo r we shall ex rend The prefix by swapping 58 In Place Par39TiTion in AcTion after 5 s reps Leng rh of prefix 3 13287645 I nex r elemen r pivo r Because nex r elemen r is larger Than pivo r no change To prefix 59 In Place Par39TiTion in AcTion offer 6 s reps Leng rh of prefix 3 13287645 pivo r nex r elemen r Because nex r elemen r is less Than pivo r we shall ex rend The prefix by swapping 60 In Place Par39TiTion in AcTion afTer39 7 sTeps LengTh of prefix 4 13247685 39pivoT nexT elemenT When nexT elemenT is The pivoT we puT iT afTer39 The end of The prefix by swapping 61 In Place Par39TiTion in AcTion offer 8 s reps Leng rh of prefix 4 13245687 pivo r Par ri rion is done and return leng rh of prefix 62 QuicksorT in C sTyle pseudocode The Quicksor r algorithm works as follows Quicksor rApr39 To sor39T or39r39oy Apr39 1 if p 2 r39 r39e rur39n 2 q Por39Ti rionApr3939 3 Quicksor39TA p pq1 4 QuicksorTA pq1 r39 To sor r A1n we jus r coll Quicksor rA1n 63 656 3102 Adv Dam STrucTures and AlgoriThm Analysis Classwor39k Session 1 Exercise on G noTaTion Show The following bound 1 2mm k 123n n2 2 Elm To n k2 149n2 n3 Exercise on G noTaTion Show The following bound 3 2km n 1k 1121n Iog n Big O exercise If dn is Ofn and e n is Ogn show Tha r dn 6n is 01 n 900 dn n i5 0fn9n Is This True 9 2d n is O2fn Searching Ar39r39ay A was supposed To be like Ai i However due To an error one value wen r missing so Ai 2i for iltk and Ai i1 for The r39esT We have To find This missing value k Example The missing value is 5 i1 2 3 4 5 6 7 8 9 10 Ai quotBEEEmma Searching in a maTrix LeT Am be a mono ronically sor red ma rrix ie Aij lt Ai1j and Aij lt Aij1 for any ij Given a number x how fas r can we find if This number x appears in A or no r MonoTone Ma rrix m 10 39 50 59 80 89 28 101 112 119 28 36 49 60 74 93 96 113 121 133 33 46 61 71 80 95 109 125 134 147 45 55 67 85 90 104 119 134 140 150 51 62 75 88 99 121 128 139 150 166 60 80 89 96 108 133 134 154 165 174 78 86 100 108 117 140 147 159 171 184 80 98 106 117 129 148 160 174 181 190 97 107 114 130 141 160 165 183 194 205


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Jennifer McGill UCSF Med School

"Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.