Algorithms Illuminated (Part 1) The Basics (Tim Roughgarden) (z-library.sk, 1lib.sk, z-lib.sk)

Algorithms Illuminated Part 1: The Basics Tim Roughgarden

c 2017 by Tim Roughgarden All rights reserved. No portion of this book may be reproduced in any form without permission from the publisher, except as permitted by U. S. copyright law. Printed in the United States of America First Edition Cover image: Stanza, by Andrea Belag ISBN: 978-0-9992829-0-8 (Paperback) ISBN: 978-0-9992829-1-5 (ebook) Library of Congress Control Number: 2017914282 Soundlikeyourself Publishing, LLC San Francisco, CA tim.roughgarden@gmail.com www.algorithmsilluminated.org

To Emma

Contents Preface vii 1 Introduction 1 1.1 Why Study Algorithms? 1 1.2 Integer Multiplication 3 1.3 Karatsuba Multiplication 6 1.4 MergeSort: The Algorithm 12 1.5 MergeSort: The Analysis 18 1.6 Guiding Principles for the Analysis of Algorithms 26 Problems 33 2 Asymptotic Notation 36 2.1 The Gist 36 2.2 Big-O Notation 45 2.3 Two Basic Examples 47 2.4 Big-Omega and Big-Theta Notation 50 2.5 Additional Examples 54 Problems 57 3 Divide-and-Conquer Algorithms 60 3.1 The Divide-and-Conquer Paradigm 60 3.2 Counting Inversions in O(n log n) Time 61 3.3 Strassen’s Matrix Multiplication Algorithm 71 *3.4 An O(n log n)-Time Algorithm for the Closest Pair 77 Problems 90 4 The Master Method 92 4.1 Integer Multiplication Revisited 92 4.2 Formal Statement 95 4.3 Six Examples 97 v

vi Contents *4.4 Proof of the Master Method 103 Problems 114 5 QuickSort 117 5.1 Overview 117 5.2 Partitioning Around a Pivot Element 121 5.3 The Importance of Good Pivots 128 5.4 Randomized QuickSort 132 *5.5 Analysis of Randomized QuickSort 135 *5.6 Sorting Requires ⌦(n log n) Comparisons 145 Problems 151 6 Linear-Time Selection 155 6.1 The RSelect Algorithm 155 *6.2 Analysis of RSelect 163 *6.3 The DSelect Algorithm 167 *6.4 Analysis of DSelect 172 Problems 180 A Quick Review of Proofs By Induction 183 A.1 A Template for Proofs by Induction 183 A.2 Example: A Closed-Form Formula 184 A.3 Example: The Size of a Complete Binary Tree 185 B Quick Review of Discrete Probability 186 B.1 Sample Spaces 186 B.2 Events 187 B.3 Random Variables 189 B.4 Expectation 190 B.5 Linearity of Expectation 192 B.6 Example: Load Balancing 195 Index 199

Preface This book is the first of a four-part series based on my online algorithms courses that have been running regularly since 2012, which in turn are based on an undergraduate course that I’ve taught many times at Stanford University. What We’ll Cover Algorithms Illuminated, Part 1 provides an introduction to and basic literacy in the following four topics. Asymptotic analysis and big-O notation. Asymptotic notation provides the basic vocabulary for discussing the design and analysis of algorithms. The key concept here is “big-O” notation, which is a modeling choice about the granularity with which we measure the running time of an algorithm. We’ll see that the sweet spot for clear high-level thinking about algorithm design is to ignore constant factors and lower-order terms, and to concentrate on how an algorithm’s performance scales with the size of the input. Divide-and-conquer algorithms and the master method. There’s no silver bullet in algorithm design, no single problem-solving method that cracks all computational problems. However, there are a few general algorithm design techniques that find successful ap- plication across a range of different domains. In this part of the series, we’ll cover the “divide-and-conquer” technique. The idea is to break a problem into smaller subproblems, solve the subproblems recursively, and then quickly combine their solutions into one for the original problem. We’ll see fast divide-and-conquer algorithms for sorting, integer and matrix multiplication, and a basic problem in computational geometry. We’ll also cover the master method, which is vii

viii Preface a powerful tool for analyzing the running time of divide-and-conquer algorithms. Randomized algorithms. A randomized algorithm “flips coins” as it runs, and its behavior can depend on the outcomes of these coin flips. Surprisingly often, randomization leads to simple, elegant, and practical algorithms. The canonical example is randomized QuickSort, and we’ll explain this algorithm and its running time analysis in detail. We’ll see further applications of randomization in Part 2. Sorting and selection. As a byproduct of studying the first three topics, we’ll learn several famous algorithms for sorting and selection, including MergeSort, QuickSort, and linear-time selection (both ran- domized and deterministic). These computational primitives are so blazingly fast that they do not take much more time than that needed just to read the input. It’s important to cultivate a collection of such “for-free primitives,” both to apply directly to data and to use as the building blocks for solutions to more difficult problems. For a more detailed look into the book’s contents, check out the “Upshot” sections that conclude each chapter and highlight the most important points. Topics covered in the other three parts. Algorithms Illumi- nated, Part 2 covers data structures (heaps, balanced search trees, hash tables, bloom filters), graph primitives (breadth- and depth-first search, connectivity, shortest paths), and their applications (rang- ing from deduplication to social network analysis). Part 3 focuses on greedy algorithms (scheduling, minimum spanning trees, cluster- ing, Huffman codes) and dynamic programming (knapsack, sequence alignment, shortest paths, optimal search trees). Part 4 is all about NP -completeness, what it means for the algorithm designer, and strategies for coping with computationally intractable problems, in- cluding the analysis of heuristics and local search. Skills You’ll Learn Mastering algorithms takes time and effort. Why bother? Become a better programmer. You’ll learn several blazingly fast subroutines for processing data and several useful data structures for

Preface ix organizing data that can be deployed directly in your own programs. Implementing and using these algorithms will stretch and improve your programming skills. You’ll also learn general algorithm design paradigms that are relevant for many different problems across differ- ent domains, as well as tools for predicting the performance of such algorithms. These “algorithmic design patterns” can help you come up with new algorithms for problems that arise in your own work. Sharpen your analytical skills. You’ll get lots of practice describ- ing and reasoning about algorithms. Through mathematical analysis, you’ll gain a deep understanding of the specific algorithms and data structures covered in these books. You’ll acquire facility with sev- eral mathematical techniques that are broadly useful for analyzing algorithms. Think algorithmically. After learning about algorithms it’s hard not to see them everywhere, whether you’re riding an elevator, watch- ing a flock of birds, managing your investment portfolio, or even watching an infant learn. Algorithmic thinking is increasingly useful and prevalent in disciplines outside of computer science, including biology, statistics, and economics. Literacy with computer science’s greatest hits. Studying al- gorithms can feel like watching a highlight reel of many of the greatest hits from the last sixty years of computer science. No longer will you feel excluded at that computer science cocktail party when someone cracks a joke about Dijkstra’s algorithm. After reading these books, you’ll know exactly what they mean. Ace your technical interviews. Over the years, countless stu- dents have regaled me with stories about how mastering the concepts in these books enabled them to ace every technical interview question they were ever asked. How These Books Are Different This series of books has only one goal: to teach the basics of algorithms in the most accessible way possible. Think of them as a transcript of what an expert algorithms tutor would say to you over a series of one-on-one lessons.

x Preface There are a number of excellent more traditional and more encyclo- pedic textbooks on algorithms, any of which usefully complement this book series with additional details, problems, and topics. I encourage you to explore and find your own favorites. There are also several books that, unlike these books, cater to programmers looking for ready-made algorithm implementations in a specific programming language. Many such implementations are freely available on the Web as well. Who Are You? The whole point of these books and the online courses they are based on is to be as widely and easily accessible as possible. People of all ages, backgrounds, and walks of life are well represented in my online courses, and there are large numbers of students (high-school, college, etc.), software engineers (both current and aspiring), scientists, and professionals hailing from all corners of the world. This book is not an introduction to programming, and ideally you’ve acquired basic programming skills in a standard language (like Java, Python, C, Scala, Haskell, etc.). For a litmus test, check out Section 1.4—if it makes sense, you’ll be fine for the rest of the book. If you need to beef up your programming skills, there are several outstanding free online courses that teach basic programming. We also use mathematical analysis as needed to understand how and why algorithms really work. The freely available lecture notes Mathematics for Computer Science, by Eric Lehman and Tom Leighton, are an excellent and entertaining refresher on mathematical notation (like P and 8), the basics of proofs (induction, contradiction, etc.), discrete probability, and much more.1 Appendices A and B also provide quick reviews of proofs by induction and discrete probability, respectively. The starred sections are the most mathematically intense ones. The math-phobic or time-constrained reader can skip these on a first reading without loss of continuity. Additional Resources These books are based on online courses that are currently running on the Coursera and Stanford Lagunita platforms. There are several 1http://www.boazbarak.org/cs121/LehmanLeighton.pdf.

Preface xi resources available to help you replicate as much of the online course experience as you like. Videos. If you’re more in the mood to watch and listen than to read, check out the YouTube video playlists available from www.algorithmsilluminated.org. These videos cover all of the top- ics of this book series. I hope they exude a contagious enthusiasm for algorithms that, alas, is impossible to replicate fully on the printed page. Quizzes. How can you know if you’re truly absorbing the concepts in this book? Quizzes with solutions and explanations are scattered throughout the text; when you encounter one, I encourage you to pause and think about the answer before reading on. End-of-chapter problems. At the end of each chapter you’ll find several relatively straightforward questions to test your understanding, followed by harder and more open-ended challenge problems. Solutions to these end-of-chapter problems are not included here, but readers can interact with me and each other about them through the book’s discussion forum (see below). Programming problems. Many of the chapters conclude with a suggested programming project, where the goal is to develop a detailed understanding of an algorithm by creating your own working implementation of it. Data sets, along with test cases and their solutions, can be found at www.algorithmsilluminated.org. Discussion forums. A big reason for the success of online courses is the opportunities they provide for participants to help each other understand the course material and debug programs through discus- sion forums. Readers of these books have the same opportunity, via the forums available from www.algorithmsilluminated.org. Acknowledgments These books would not exist without the passion and hunger supplied by the thousands of participants in my algorithms courses over the years, both on-campus at Stanford and on online platforms. I am par- ticularly grateful to those who supplied detailed feedback on an earlier draft of this book: Tonya Blust, Yuan Cao, Jim Humelsine, Bayram

xii Preface Kuliyev, Patrick Monkelban, Kyle Schiller, Nissanka Wickremasinghe, and Daniel Zingaro. I always appreciate suggestions and corrections from readers, which are best communicated through the discussion forums mentioned above. Stanford University Tim Roughgarden Stanford, California September 2017

Chapter 1 Introduction The goal of this chapter is to get you excited about the study of algorithms. We begin by discussing algorithms in general and why they’re so important. Then we use the problem of multiplying two integers to illustrate how algorithmic ingenuity can improve on more straightforward or naive solutions. We then discuss the MergeSort algorithm in detail, for several reasons: it’s a practical and famous algorithm that you should know; it’s a good warm-up to get you ready for more intricate algorithms; and it’s the canonical introduction to the “divide-and-conquer” algorithm design paradigm. The chapter concludes by describing several guiding principles for how we’ll analyze algorithms throughout the rest of the book. 1.1 Why Study Algorithms? Let me begin by justifying this book’s existence and giving you some reasons why you should be highly motivated to learn about algorithms. So what is an algorithm, anyway? It’s a set of well-defined rules—a recipe, in effect—for solving some computational problem. Maybe you have a bunch of numbers and you want to rearrange them so that they’re in sorted order. Maybe you have a road map and you want to compute the shortest path from some origin to some destination. Maybe you need to complete several tasks before certain deadlines, and you want to know in what order you should finish the tasks so that you complete them all by their respective deadlines. So why study algorithms? Important for all other branches of computer science. First, understanding the basics of algorithms and the closely related field of data structures is essential for doing serious work in pretty much any branch of computer science. For example, at Stanford University, 1

2 Introduction every degree the computer science department offers (B.S., M.S., and Ph.D.) requires an algorithms course. To name just a few examples: 1. Routing protocols in communication networks piggyback on classical shortest path algorithms. 2. Public-key cryptography relies on efficient number-theoretic algorithms. 3. Computer graphics requires the computational primitives sup- plied by geometric algorithms. 4. Database indices rely on balanced search tree data structures. 5. Computational biology uses dynamic programming algorithms to measure genome similarity. And the list goes on. Driver of technological innovation. Second, algorithms play a key role in modern technological innovation. To give just one obvious example, search engines use a tapestry of algorithms to efficiently compute the relevance of various Web pages to a given search query. The most famous such algorithm is the PageRank algorithm currently in use by Google. Indeed, in a December 2010 report to the United States White House, the President’s council of advisers on science and technology wrote the following: “Everyone knows Moore’s Law –– a prediction made in 1965 by Intel co-founder Gordon Moore that the density of transistors in integrated circuits would continue to double every 1 to 2 years. . . in many areas, performance gains due to improvements in algorithms have vastly exceeded even the dramatic performance gains due to increased processor speed.”1 1Excerpt from Report to the President and Congress: Designing a Digital Future, December 2010 (page 71).

1.2 Integer Multiplication 3 Lens on other sciences. Third, although this is beyond the scope of this book, algorithms are increasingly used to provide a novel “lens” on processes outside of computer science and technology. For example, the study of quantum computation has provided a new computational viewpoint on quantum mechanics. Price fluctuations in economic markets can be fruitfully viewed as an algorithmic process. Even evolution can be thought of as a surprisingly effective search algorithm. Good for the brain. Back when I was a student, my favorite classes were always the challenging ones that, after I struggled through them, left me feeling a few IQ points smarter than when I started. I hope this material provides a similar experience for you. Fun! Finally, I hope that by the end of the book you can see why the design and analysis of algorithms is simply fun. It’s an endeavor that requires a rare blend of precision and creativity. It can certainly be frustrating at times, but it’s also highly addictive. And let’s not forget that you’ve been learning about algorithms since you were a little kid. 1.2 Integer Multiplication 1.2.1 Problems and Solutions When you were in third grade or so, you probably learned an algorithm for multiplying two numbers—a well-defined set of rules for trans- forming an input (two numbers) into an output (their product). It’s important to distinguish between two different things: the description of the problem being solved, and that of the method of solution (that is, the algorithm for the problem). In this book, we’ll repeatedly follow the pattern of first introducing a computational problem (the inputs and desired output), and then describing one or more algorithms that solve the problem. 1.2.2 The Integer Multiplication Problem In the integer multiplication problem, the input is two n-digit numbers, which we’ll call x and y. The length n of x and y could be any positive integer, but I encourage you to think of n as large, in the thousands or

4 Introduction even more.2 (Perhaps you’re implementing a cryptographic application that must manipulate very large numbers.) The desired output in the integer multiplication problem is just the product x · y. Problem: Integer Multiplication Input: Two n-digit nonnegative integers, x and y. Output: The product x · y. 1.2.3 The Grade-School Algorithm Having defined the computational problem precisely, we describe an algorithm that solves it—the same algorithm you learned in third grade. We will assess the performance of this algorithm through the number of “primitive operations” it performs, as a function of the number of digits n in each input number. For now, let’s think of a primitive operation as any of the following: (i) adding two single-digit numbers; (ii) multiplying two single-digit numbers; or (iii) adding a zero to the beginning or end of a number. To jog your memory, consider the concrete example of multiplying x = 5678 and y = 1234 (so n = 4). See also Figure 1.1. The algorithm first computes the “partial product” of the first number and the last digit of the second number 5678 · 4 = 22712. Computing this partial product boils down to multiplying each of the digits of the first number by 4, and adding in “carries” as necessary.3 When computing the next partial product (5678 · 3 = 17034), we do the same thing, shifting the result one digit to the left, effectively adding a “0” at the end. And so on for the final two partial products. The final step is to add up all the partial products. Back in third grade, you probably accepted that this algorithm is correct, meaning that no matter what numbers x and y you start with, provided that all intermediate computations are done properly, it eventually terminates with the product x · y of the two input numbers. 2If you want to multiply numbers with different lengths (like 1234 and 56), a simple hack is to just add some zeros to the beginning of the smaller number (for example, treat 56 as 0056). Alternatively, the algorithms we’ll discuss can be modified to accommodate numbers with different lengths. 3 8 · 4 = 32, carry the 3, 7 · 4 = 28, plus 3 is 31, carry the 3, . . .

1.2 Integer Multiplication 5 5678 × 1234 22712 17034 11356 5678 7006652
2n operations (per row) n rows Figure 1.1: The grade-school integer multiplication algorithm. That is, you’re never going to get a wrong answer, and the algorithm can’t loop forever. 1.2.4 Analysis of the Number of Operations Your third-grade teacher might not have discussed the number of primitive operations needed to carry out this procedure to its con- clusion. To compute the first partial product, we multiplied 4 times each of the digits 5, 6, 7, 8 of the first number. This is 4 primitive operations. We also performed a few additions because of the carries. In general, computing a partial product involves n multiplications (one per digit) and at most n additions (at most one per digit), for a total of at most 2n primitive operations. There’s nothing special about the first partial product: every partial product requires at most 2n operations. Since there are n partial products—one per digit of the second number—computing all of them requires at most n · 2n = 2n2 primitive operations. We still have to add them all up to compute the final answer, but this takes a comparable number of operations (at most another 2n2). Summarizing: total number of operations  constant| {z } =4 ·n2. Thinking about how the amount of work the algorithm performs scales as the input numbers grow bigger and bigger, we see that the work required grows quadratically with the number of digits. If you double the length of the input numbers, the work required jumps by

6 Introduction a factor of 4. Quadruple their length and it jumps by a factor of 16, and so on. 1.2.5 Can We Do Better? Depending on what type of third-grader you were, you might well have accepted this procedure as the unique or at least optimal way to multiply two numbers. If you want to be a serious algorithm designer, you’ll need to grow out of that kind of obedient timidity. The classic algorithms book by Aho, Hopcroft, and Ullman, after iterating through a number of algorithm design paradigms, has this to say: “Perhaps the most important principle for the good algorithm designer is to refuse to be content.”4 Or as I like to put it, every algorithm designer should adopt the mantra: Can we do better? This question is particularly apropos when you’re faced with a naive or straightforward solution to a computational problem. In the third grade, you might not have asked if one could do better than the straightforward integer multiplication algorithm. Now is the time to ask, and answer, this question. 1.3 Karatsuba Multiplication The algorithm design space is surprisingly rich, and there are certainly other interesting methods of multiplying two integers beyond what you learned in the third grade. This section describes a method called Karatsuba multiplication.5 4Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974, page 70. 5Discovered in 1960 by Anatoly Karatsuba, who at the time was a 23-year-old student.

1.3 Karatsuba Multiplication 7 1.3.1 A Concrete Example To get a feel for Karatsuba multiplication, let’s re-use our previous example with x = 5678 and y = 1234. We’re going to execute a sequence of steps, quite different from the grade-school algorithm, culminating in the product x · y. The sequence of steps should strike you as very mysterious, like pulling a rabbit out of a hat; later in the section we’ll explain exactly what Karatsuba multiplication is and why it works. The key point to appreciate now is that there’s a dazzling array of options for solving computational problems like integer multiplication. First, to regard the first and second halves of x as numbers in their own right, we give them the names a and b (so a = 56 and b = 78). Similarly, c and d denote 12 and 34, respectively (Figure 1.2). 5678 × 1234 a b c d Figure 1.2: Thinking of 4-digit numbers as pairs of double-digit numbers. Next we’ll perform a sequence of operations that involve only the double-digit numbers a, b, c, and d, and finally collect all the terms together in a magical way that results in the product of x and y. Step 1: Compute a · c = 56 · 12, which is 672 (as you’re welcome to check). Step 2: Compute b · d = 78 · 34 = 2652. The next two steps are still more inscrutable. Step 3: Compute (a+ b) · (c+ d) = 134 · 46 = 6164. Step 4: Subtract the results of the first two steps from the result of the third step: 6164 672 2652 = 2840.