Algorithms Illuminated (Part 2) Graph Algorithms and Data Structures (Tim Roughgarden) (z-library.sk, 1lib.sk, z-lib.sk)

📄 File Format: PDF

💾 File Size: 7.9 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

Algorithms Illuminated Part 2: Graph Algorithms and Data Structures Tim Roughgarden

📄 Page 2

c 2018 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. First Edition Cover image: Untitled, by Nick Terry 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 soundlikeyourselfpublishing@gmail.com www.algorithmsilluminated.org

📄 Page 3

In memory of James Wesley Shean (1921–2010)

📄 Page 4

(This page has no text content)

📄 Page 5

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 v

📄 Page 6

vi Contents 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

📄 Page 7

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 reasoning about graph structure. We begin with linear-time algorithms 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- pute the best route in a network from point A to point B. The problem 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 vii

📄 Page 8

viii Preface 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. Search trees maintain a total ordering over the keys of the stored 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 structures for organizing data that you can deploy 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 different domains, as well as tools for predicting the performance of

📄 Page 9

Preface ix 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 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 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. 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, unlike these books, cater to programmers looking for ready-made

📄 Page 10

x Preface 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 P and 8), the basics of proofs (induction, contradiction, etc.), discrete probability, and much more. 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

📄 Page 11

Preface xi 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, Vladimir Kokshenev, Bayram Kuliyev, Patrick Monkelban, and Daniel 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

📄 Page 12

(This page has no text content)

📄 Page 13

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)). n 0 5 10 15 20 25 30 35 40 f(n ) 0 5 10 15 20 25 30 35 40 f(n)=n f(n)=log 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 1

📄 Page 14

2 Graphs: The Basics the vertices (singular: vertex) or the nodes of the graph.1 The pairwise relationships translate to the edges of the graph. We usually denote the vertex and edge sets of a graph by V and E, respectively, and sometimes write G = (V,E) to mean the graph G with vertices V and edges E. There are two flavors of graphs, directed and undirected. Both types are important and ubiquitous in applications, so you should know about both of them. In an undirected graph, each edge corresponds to an unordered pair {v, w} of vertices, which are called the endpoints of the edge (Figure 7.2(a)). In an undirected graph, there is no difference between an edge (v, w) and an edge (w, v). In a directed graph, each edge (v, w) is an ordered pair, with the edge traveling from the first vertex v (called the tail) to the second w (the head); see Figure 7.2(b).2 s v w t (a) An undirected graph s v w t (b) A directed graph Figure 7.2: Graphs with four vertices and five edges. The edges of undirected and directed graphs are unordered and ordered vertex pairs, respectively. 7.2 A Few Applications Graphs are a fundamental concept, and they show up all the time in computer science, biology, sociology, economics, and so on. Here are a few of the countless examples. 1Having two names for the same thing can be annoying, but both terms are in widespread use and you should be familiar with them. For the most part, we’ll stick with “vertices” throughout this book series. 2Directed edges are sometimes called arcs, but we won’t use this terminology in this book series.

📄 Page 15

7.3 Measuring the Size of a Graph 3 Road networks. When your smartphone’s software computes driv- ing directions, it searches through a graph that represents the road network, with vertices corresponding to intersections and edges corre- sponding to individual road segments. The World Wide Web. The Web can be modeled as a directed graph, with the vertices corresponding to individual Web pages, and the edges corresponding to hyperlinks, directed from the page con- taining the hyperlink to the destination page. Social networks. A social network can be represented as a graph whose vertices correspond to individuals and edges to some type of relationship. For example, an edge could indicate a friendship between its endpoints, or that one of its endpoints is a follower of the other. Among the currently popular social networks, which ones are most naturally modeled as an undirected graph, and which ones as a directed graph? (There are interesting examples of both.) Precedence constraints. Graphs are also useful in problems that lack an obvious network structure. For example, imagine that you have to complete a bunch of tasks, subject to precedence constraints— perhaps you’re a first-year university student, planning which courses to take and in which order. One way to tackle this problem is to apply the topological sorting algorithm described in Section 8.5 to the following directed graph: there is one vertex for each course that your major requires, with an edge directed from course A to course B whenever A is a prerequisite for B. 7.3 Measuring the Size of a Graph In this book, like in Part 1, we’ll analyze the running time of different algorithms as a function of the input size. When the input is a single array, as for a sorting algorithm, there is an obvious way to define the “input size,” as the array’s length. When the input involves a graph, we must specify exactly how the graph is represented and what we mean by its “size.” 7.3.1 The Number of Edges in a Graph Two parameters control a graph’s size—the number of vertices and the number of edges. Here is the most common notation for these

📄 Page 16

4 Graphs: The Basics quantities. Notation for Graphs For a graph G = (V,E) with vertex set V and edge set E: • n = |V | denotes the number of vertices. • m = |E| denotes the number of edges.3 The next quiz asks you to think about how the number m of edges in an undirected graph can depend on the number n of vertices. For this question, we’ll assume that there’s at most one undirected edge between each pair of vertices—no “parallel edges” are allowed. We’ll also assume that the graph is “connected.” We’ll define this concept formally in Section 8.3; intuitively, it means that the graph is “in one piece,” with no way to break it into two parts without any edges crossing between the parts. The graphs in Figures 7.1(b) and 7.2(a) are connected, while the graph in Figure 7.3 is not. Figure 7.3: An undirected graph that is not connected. Quiz 7.1 Consider an undirected graph with n vertices and no parallel edges. Assume that the graph is connected, meaning “in one piece.” What are the minimum and maximum numbers of edges, respectively, that the graph could have? 3For a finite set S, |S| denotes the number of elements in S.

📄 Page 17

7.3 Measuring the Size of a Graph 5 a) n 1 and n(n1) 2 b) n 1 and n2 c) n and 2n d) n and nn (See Section 7.3.3 for the solution and discussion.) 7.3.2 Sparse vs. Dense Graphs Now that Quiz 7.1 has you thinking about how the number of edges of a graph can vary with the number of vertices, we can discuss the distinction between sparse and dense graphs. The difference is important because some data structures and algorithms are better suited for sparse graphs, and others for dense graphs. Let’s translate the solution to Quiz 7.1 into asymptotic notation.4 First, if an undirected graph with n vertices is connected, the number of edges m is at least linear in n (that is, m = ⌦(n)).5 Second, if the graph has no parallel edges, then m = O(n2).6 We conclude that the number of edges in a connected undirected graph with no parallel edges is somewhere between linear and quadratic in the number of vertices. Informally, a graph is sparse if the number of edges is relatively close to linear in the number of vertices, and dense if this number is closer to quadratic in the number of vertices. For example, graphs with n vertices and O(n log n) edges are usually considered sparse, while those with ⌦(n2/ log n) edges are considered dense. “Partially dense” graphs, like those with ⇡ n3/2 edges, may be considered either sparse or dense, depending on the specific application. 7.3.3 Solution to Quiz 7.1 Correct answer: (a). In a connected undirected graph with n vertices and no parallel edges, the number m of edges is at least n 1 4See Appendix C for a review of big-O, big-Omega, and big-Theta notation. 5If the graph need not be connected, there could be as few as zero edges. 6If parallel edges are allowed, a graph with at least two vertices can have an arbitrarily large number of edges.

📄 Page 18

6 Graphs: The Basics and at most n(n 1)/2. To see why the lower bound is correct, consider a graph G = (V,E). As a thought experiment, imagine building up G one edge at a time, starting from the graph with vertices V and no edges. Initially, before any edges are added, each of the n vertices is completely isolated, so the graph trivially has n distinct “pieces.” Adding an edge (v, w) has the effect of fusing the piece containing v with the piece containing w (Figure 7.4). Thus, each edge addition decreases the number of pieces by at most 1.7 To get down to a single piece from n pieces, you need to add at least n1 edges. There are plenty of connected graphs that have n vertices and only n 1 edges—these are called trees (Figure 7.5). newly added edge Figure 7.4: Adding a new edge fuses the pieces containing its endpoints into a single piece. In this example, the number of different pieces drops from three to two. (a) A path on four vertices (b) A star on four vertices Figure 7.5: Two connected undirected graphs with four vertices and three edges. The maximum number of edges in a graph with no parallel edges is achieved by the complete graph, with every possible edge present. 7If both endpoints of the edge are already in the same piece, the number of pieces doesn’t decrease at all.

📄 Page 19

7.4 Representing a Graph 7 Because there are n 2 = n(n1) 2 pairs of vertices in an n-vertex graph, this is also the maximum number of edges. For example, when n = 4, the maximum number of edges is 4 2 = 6 (Figure 7.6).8 Figure 7.6: The complete graph on four vertices has 4 2 = 6 edges. 7.4 Representing a Graph There is more than one way to encode a graph for use in an algorithm. In this book series, we’ll work primarily with the “adjacency list” representation of a graph (Section 7.4.1), but you should also be aware of the “adjacency matrix” representation (Section 7.4.2). 7.4.1 Adjacency Lists The adjacency list representation of graphs is the dominant one that we’ll use in this book series. Ingredients for Adjacency Lists 1. An array containing the graph’s vertices. 2. An array containing the graph’s edges. 3. For each edge, a pointer to each of its two endpoints. 4. For each vertex, a pointer to each of the incident edges. 8n 2 is pronounced “n choose 2,” and is also sometimes referred to as a “binomial coefficient.” To see why the number of ways to choose an unordered pair of distinct objects from a set of n objects is n(n1) 2 , think about choosing the first object (from the n options) and then a second, distinct object (from the n 1 remaining options). The n(n 1) resulting outcomes produce each pair (x, y) of objects twice (once with x first and y second, once with y first and x second), so there must be n(n1) 2 pairs in all.

📄 Page 20

8 Graphs: The Basics The adjacency list representation boils down to two arrays (or linked lists, if you prefer): one for keeping track of the vertices, and one for the edges. These two arrays cross-reference each other in the natural way, with each edge associated with pointers to its endpoints and each vertex with pointers to the edges for which it is an endpoint. For a directed graph, each edge keeps track of which endpoint is the tail and which endpoint is the head. Each vertex v maintains two arrays of pointers, one for the outgoing edges (for which v is the tail) and one for the incoming edges (for which v is the head). What are the memory requirements of the adjacency list represen- tation? Quiz 7.2 How much space does the adjacency list representation of a graph require, as a function of the number n of vertices and the number m of edges? a) ⇥(n) b) ⇥(m) c) ⇥(m + n) d) ⇥(n2) (See Section 7.4.4 for the solution and discussion.) 7.4.2 The Adjacency Matrix Consider an undirected graph G = (V,E) with n vertices and no parallel edges, and label its vertices 1, 2, 3, . . . , n. The adjacency matrix representation of G is a square n⇥ n matrix A—equivalently, a two-dimensional array—with only zeroes and ones as entries. Each entry Aij is defined as Aij = ⇢ 1 if edge (i, j) belongs to E 0 otherwise. Thus, an adjacency matrix maintains one bit for each pair of vertices, which keeps track of whether or not the edge is present (Figure 7.7).