AlgorithmsIlluminatedPart1TheBasics无水印pdf

Algorithms Illuminated Part 1 The Basics 英文无水印pdf pdf所有页面使用FoxitReader和PDF-XChangeViewer测试都可以打开 本资源转载自网络，如有侵权，请联系上传者或csdn删除 本资源转载自网络，如有侵权，请联系上传者或csdn删除To EmmaContentsPreface1 Introductio11. 1 Why Study algorithn1.2 Integer Multiplicationaba multiplication1.4 MergeSort: The algorithm1.5 MergeSort: The analysis6 Guiding principles for the analysis of algorithms26Problems332 Asymptotic Notation362.1 The gist362.2 Big-O Notation452.3 Two Basic Examples2.4 Big-Omega and Big-Theta Notation2.5 Additional Examples54Problems3 Divide-and-Conquer Algorithms3.1 The Divide-and-Conquer paradigm3.2 Counting Inversions in O(n log n)Time613.3 Strasscn's Matrix Multiplication Algorithm73.4 An O(n log n)-Time Algorithm for the Closest PairProblems4 The master method924.1 Integer Multiplication Revisited4.2 Formal Statement4.3 Six ExamplesContentsof the master methodProblems114Quick Sor1175.1 Overview1175.2 Partitioning Around a Pivot Element1215.3 The Importance of Good Pivots125.4 Randomized QuickSort132*5.5 Analysis of Randomized QuickSort1355.6 Sorting Rcquires Q2(nlog n) Compari145Problems1516 Linear -Time Selection1556.1 The select algorithm1556.2 Analf eselect*6.3 The DSelect algorithm1674 Analysis of DSelect172Problems180a Quick Review of Proofs By InductionA. 1 A Template for Proofs by Induction183A 2 Example: A Closed-Form Formula184A3 Example: The Size of a complete binary Tree185b Quick review of Discrete Probability186B. 1 Sample sypaces186B 2 Events187B 3 Randoin variables189B. 1 Expectation190B5 Linearity of expectationB6 Example: Load balancingQIndex199PrefaceThis book is the first, of a four-part series based on my online algorithmscourses that have been running regularly since 2012, which in turnare based on an undergraduate course that i ve taught many times atStanford universilyWhat We'll Coveralgorithms illuminated, Part I provides an introduction to and basicliteracy in the following four topicsAsymptotic analysis and big-O notation. Asymptotic notationprovides the basic vocabulary for discussing the design and analysisof algorithms. The key concept here is"big-O notation, which is amodeling choice about the granularity with which we measure therunning time of an algorithm. We'll see that the sweet spot for clearhigh-level thinking about algorithm design is to ignore constant factorsand lower-order terms, and to concentrate on how an algorithm'sperformance scales with the size of the inputDivide-and-conquer algorithms and the master methodThere's no silver bullet in aIgorithm design, no single problem-solvingmethod that cracks all computational problems. However, there area few general algorithm design techniques that find successful application across a range of different domains. In this part of theseries, we'll cover the divide-and-conquer"technique. The idea isto break a problem into smaller subproblems, solve the subproblemsrecursively, and then quickly combine their solutions into one for theoriginal problem. We'll see fast divide-and-conquer algorithms forsorting, integer anld malrix multiplication, and a basic problein ilcomputational geometry. We'll also cover the master method, which isPrefacea powerful tool for analyzing the running time of divide-and-conquerRandomized algorithms. A randomized algorithm"flips coins"asit runs, and its behavior can depend on the outcomes of these coinHips. Surprisingly often, randomization leads to simple, elegant, andpractical algorithms. The canonical example is randomized QuickSort,and we'll explain this algorithm and its running time analysis in detailWc'll scc further applications of randomization in Part 2Sorting and selection. As a by product of studying the first threetopics, we'll learn several famous algorithms for sorting and selectionincluding MergeSort, Quick Sort, and linear-time selection(both randomized and deterministic). These computational primitives are soblazingly fast that they do not take much more time than that neededust lo read the input. It's imporlant to cultivate a collection of suchfor-frcc primitives, both to apply directly to data and to usc as thcDuilding blocks for solutions to more difficult problemsFor a more detailed look into the book's contents. check out theUpshot' sections that conclude each chapter and highlight the mostimportant pointsTopics covered in the other three parts. Algorithms Illumimated, Part 2 covers data structures(heaps, balanced search treeshash tables, bloom filters), graph primitives(breadth- and depth-firstsearch, connectivity, shortest paths), and their applications (rang-ng from deduplication to social network analysis). Part 3 focuseson greedy algorithms(scheduling minimum spanning trees, clustering, Huffman codes) and dynamic programming(knapsack, sequencealignment, shortest paths, optimal search trees). Part 4 is all aboutP-completeness, what it means for the algorithm designer, andstrategies for coping with computationally intractable problems, including the analysis of heuristics and local searchSkills you ll learnMastering algorithms takcs timc and cffort. Why botherBecome a better programmer. You'l learn several blazingly fastsubroutines for processing data and several useful data structures forPrefaceorganizing data that can be deployed directly in your own programsImplementing and using these algorithms will stretch and improveyour programming skills. You'l also learn general algorithm designparadigms that are relevant for many different problems across differ-ent domains, as well as tools for predicting the performance of suchalgorithms. These"algorithmic design patterns can help you comeup with new algorithms for problems that arise in your own workSharpen your analytical skills. You'll get lots of practice describ-ing and reasoning about algorithms. Through mathematical analysisyou'l gain a deep understanding of the specific algorithms and datastructures covered in these books. You'll acquire facility with sev-eral mathematical techniques that are broadly useful for analyzingalgorithmsThink algorithmically. After learning about algorithms it's hardnot to see them everywhere, whether you're riding an elevator, watching a flock of birds, managing your investment portfolio, or evenwatching an infant learn. Algorithmic thinking is increasingly usefuland prevalent in disciplines outside of computer science, includingbiology, statistics, and economicsLiteracy with computer science's greatest hits. Studying algorithms can fccl like watching a highlight rccl of many of the greatesthits from the last sixty years of computer science. No longer will youluded at that computer sciencktail party when someonecracks a joke about Dijkstra's algorithm. After reading these booksyoull know exactly what they meanAce your technical interviews. Over the ycars, countless students have regaled me with stories about how mastering the conceptsin these books enabled them to ace every technical interview questionthey were ever askedHow These books are differentThis series of books has only one goal: to teach the basics of algorithmsn the most accessible way possible. Think of them as a transcriptof whal all expert algorithns tutor would say to you over a series ofone-on-one lessonsPrefaceThere are a number of excellent more traditional and more encyclpedic textbooks on algorithms, any of which usefully complement thisbook series with additional details, problems, and topics. I encourageyou to explore and find your own favorites. There are also severalbooks that, unlike these books, cater to programmers looking forready-made algorithm implementations in a specific programminganguage. Many such implementations are freely available on the webwellWho are you?The wholc point of thesc books and the online courses thcy arc bascdon is to be as widely and easily accessible as possible. People of allges, backgrounds, and walks of life are well represented in my onlinecourses, and there are large numbers of students(high-school, college,etc. ) software engineers(both current and aspiring), scientists, andprofessionals hailing from all corners of the worldThis book is not an introduction to programming and ideallyyou've acquired basic programming skills in a standard language (likeJava, Python, C, Scala, Haskell, etc. ) For a litmus test, check outSection 1.4-if it makes sense, you'll be fine for the rest of the bookIf you need to beef up your programming skills, there are severaloutstanding free online courses that teach basic programmingWe also use nathenalical analysis as needed to understandow and why algorithms really work. The freely available lecturenotes Mathematics for Computer Science, by eric Lehman and Tomeighton. are an excellent and entertaining refresher on mathematicalnotation(like 2 and V), the basics of proofs(induction, contradictionelc. ) discrete probabilily, anld mluch more. Appendices A and B alsoprovide quick reviews of proofs by induction and discrete probability,respectively. The starred sections are the most ma.thematically intenseones. The math-phobic or time-constrained reader can skip these ona first reading without loss of continuityAdditional resourcesThese books are based on online courses that are currently runningon the Coursera and Stanford Lagunita platforms. There are severalhttp://www.boazbarak,org/cs121/lehmanleighton.pdf