Algorithms Illuminated Part 2: Graph Algorithms and Data Structures Tim Roughgarden c 2018 by Tim Roughgarden � ISBN: 978-0-9992829-2-2 (Paperback) ISBN: 978-0-9992829-3-9 (ebook) Library of Congress Control Number: 2017914282 Soundlikeyourself Publishing, LLC San Francisco, CA [email protected] www.algorithmsilluminated.org Contents Preface vii 7 Graphs: The Basics 1 7.1 Some Vocabulary 1 7.2 A Few Applications 2 7.3 Measuring the Size of a Graph 3 7.4 Representing a Graph 7 Problems 13 8 Graph Search and Its Applications 15 8.1 Overview 15 8.2 Breadth-First Search and Shortest Paths 25 8.3 Computing Connected Components 34 8.4 Depth-First Search 40 8.5 Topological Sort 45 *8.6 Computing Strongly Connected Components 54 8.7 The Structure of the Web 66 Problems 71 9 Dijkstra’s Shortest-Path Algorithm 76 9.1 The Single-Source Shortest Path Problem 76 9.2 Dijkstra’s Algorithm 80 *9.3 Why Is Dijkstra’s Algorithm Correct? 83 9.4 Implementation and Running Time 89 Problems 91 10 The Heap Data Structure 95 10.1 Data Structures: An Overview 95 10.2 Supported Operations 98 10.3 Applications 101 10.4 Speeding Up Dijkstra’s Algorithm 106 *10.5 Implementation Details 112 Problems 123 11 Search Trees 126 11.1 Sorted Arrays 126 11.2 Search Trees: Supported Operations 129 *11.3 Implementation Details 131 *11.4 Balanced Search Trees 145 Problems 149 12 Hash Tables and Bloom Filters 151 12.1 Supported Operations 151 12.2 Applications 154 *12.3 Implementation: High-Level Ideas 159 *12.4 Further Implementation Details 173 12.5 Bloom Filters: The Basics 178 *12.6 Bloom Filters: Heuristic Analysis 184 Problems 190 C Quick Review of Asymptotic Notation 193 C.1 The Gist 193 C.2 Big-O Notation 194 C.3 Examples 195 C.4 Big-Omega and Big-Theta Notation 197 Solutions to Selected Problems 200 Index 203 Preface This book is the second 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. The first part of the series is not a prerequisite for this one, and this book should be accessible to any reader who has the background described in the “Who Are You?” section below and is familiar with asymptotic notation (which is reviewed in Appendix C). What We’ll Cover Algorithms Illuminated, Part 2 provides an introduction to and basic literacy in the following three topics. Graph search and applications. Graphs model many different types of networks, including road networks, communication networks, social networks, and networks of dependencies between tasks. Graphs can get complex, but there are several blazingly fast primitives for reasoningaboutgraphstructure. Webeginwithlinear-timealgorithms for searching a graph, with applications ranging from network analysis to task sequencing. Shortest paths. In the shortest-path problem, the goal is to com- putethebestrouteinanetworkfrompointAtopointB.Theproblem has obvious applications, like computing driving directions, and also shows up in disguise in many more general planning problems. We’ll generalize one of our graph search algorithms and arrive at Dijkstra’s famous shortest-path algorithm. Data structures. This book will make you an educated client of several different data structures for maintaining an evolving set of objects with keys. The primary goal is to develop your intuition about which data structure is the right one for your application. The optional advanced sections provide guidance in how to implement these data structures from scratch. We first discuss heaps, which can quickly identify the stored object with the smallest key and are useful for sorting, implementing a priority queue, and implementing Dijkstra’s algorithm in near-linear time. Searchtreesmaintainatotalorderingoverthekeysofthestored objects and support an even richer array of operations. Hash tables are optimized for super-fast lookups and are ubiquitous in modern programs. We’ll also cover the bloom filter, a close cousin of the hash table that uses less space at the expense of occasional errors. 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. The starred sections of the book are the most advanced ones. The time-constrained reader can skip these on a first reading without loss of continuity. Topics covered in the other three parts. Algorithms Illumi- nated, Part 1 covers asymptotic notation (big-O notation and its close cousins), divide-and-conquer algorithms and the master method, randomized QuickSort and its analysis, and linear-time selection algo- rithms. Part 3 focuses on greedy algorithms (scheduling, minimum spanning trees, clustering, 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, including 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 as well as several useful data structuresfororganizingdatathatyoucandeploydirectlyinyourown 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 different 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’llgetlotsofpracticedescrib- 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 you learn about algorithms, it’s hard to not see them everywhere, whether you’re riding an elevator, watching 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 Thisseriesofbookshasonlyonegoal: 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. There are a number of excellent more traditional and encyclopedic 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, unlikethesebooks, catertoprogrammerslookingforready-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 upon which they are based 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 8.2—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 book Mathe- matics for Computer Science, by Eric Lehman, F. Thomson Leighton, and Albert R. Meyer is an excellent and entertaining refresher on mathematical notation (like and ), the basics of proofs (induction, 8 contradiction, etc.), discrete probability, and much more. P Additional Resources These books are based on online courses that are currently running on the Coursera and Stanford Lagunita platforms. I’ve made several 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, as well as additional advanced topics. 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 for testing your under- standing, followed by harder and more open-ended challenge problems. Solutions to problems that are marked with an “(S)” appear at the end of the book. Readers can interact with me and each other about the remaining end-of-chapter problems through the book’s discussion forum (see below). Programming problems. Most of the chapters conclude with a suggested programming project, whose goal is to help you 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 at www.algorithmsilluminated.org. Acknowledgments These books would not exist without the passion and hunger supplied by the hundreds of thousands of participants in my algorithms courses over the years, both on campus at Stanford and on online platforms. I am particularly grateful to those who supplied detailed feedback on an earlier draft of this book: Tonya Blust, Yuan Cao, Jim Humelsine, VladimirKokshenev, BayramKuliyev, PatrickMonkelban, andDaniel Zingaro. I always appreciate suggestions and corrections from readers. These are best communicated through the discussion forums men- tioned above. Tim Roughgarden London, United Kingdom July 2018 Chapter 7 Graphs: The Basics This short chapter explains what graphs are, what they are good for, and the most common ways to represent them in a computer program. The next two chapters cover a number of famous and useful algorithms for reasoning about graphs. 7.1 Some Vocabulary When you hear the word “graph,” you probably think about an x-axis, a y-axis, and so on (Figure 7.1(a)). To an algorithms person, a graph can also mean a representation of the relationships between pairs of objects (Figure 7.1(b)). 40 f(n)=n f(n)=log n 35 30 25 f(n)20 15 10 5 0 0 5 10 15 20 25 30 35 40 n (a) A graph (to most of the world) (b) A graph (in algorithms) Figure 7.1: In algorithms, a graph is a representation of a set of objects (such as people) and the pairwise relationships between them (such as friendships). The second type of graph has two ingredients—the objects being represented, and their pairwise relationships. The former are called