Notes on Randomized Algorithms

《Notes on Randomized Algorithms》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、NotesonRandomizedAlgorithmsCS469/569:Spring2011JamesAspnes2011-07-1514:47ContentsPrefacexSyllabusxiLectureschedulexiv1Randomizedalgorithms11.1Atrivialexample.........................21.2Alesstrivialexample:randomizedQuickSort.........21.2.1Bruteforcemethod:solvetherecurrence..

2、.....31.2.2Clevermethod:uselinearityofexpectation......41.3Karger'smin-cutalgorithm...................51.4Classifyingrandomizedalgorithmsbytheirgoals.......71.4.1LasVegasvsMonteCarlo................71.4.2Randomizedcomplexityclasses.............81.5Classifyingrandomizedalgorith

3、msbytheirmethods.....92Probabilisticrecurrences112.1Recurrenceswithconstantcostfunctions............112.2Examples.............................112.3TheKarp-Upfal-Wigdersonbound...............122.3.1Waitingforheads.....................142.3.2Quickselect........................14

4、2.3.3Tossingcoins.......................142.3.4Couponcollector.....................152.3.5Chutesandladders....................152.4High-probabilitybounds.....................162.4.1High-probabilityboundsfromexpectationbounds..172.4.2Detailedanalysisoftherecurrence...........17

5、2.5Moregeneralrecurrences.....................18iCONTENTSii3Probabilisticinequalities193.1Basics...............................193.1.1Lawoftotalprobability.................193.1.2Unionbound(Boole'sinequality)............203.1.2.1Examples....................203.1.3Linearityofex

6、pectation.................203.1.4Markov'sinequality...................213.1.4.1Examples....................213.1.5Jensen'sinequality....................223.1.5.1Examples....................223.2Concentrationbounds......................233.2.1Chebyshev'sinequality..............

7、....233.2.1.1Examples....................24Flippingcoins...................24Flippingnon-independentcoins.........24Ballsinbins....................24Lazyselect....................243.2.2Chernobounds.....................263.2.2.1TheclassicChernobound..........263.2.2.2Cherno

8、boundvariants............283.2.2.3LowerboundversionofChernob