Algorithms Illuminated (Part 2): Graph Algorithms and Data Structures

by Tim Roughgarden

Overview

Algorithms are the heart and soul of computer science. Their applications range from network routing and computational genomics to public-key cryptography and machine learning. Studying algorithms can make you a better programmer, a clearer thinker, and a master of technical interviews. Algorithms Illuminated is an accessible introduction to the subject for anyone with at least a little programming experience. The exposition emphasizes the big picture and conceptual understanding over low-level implementation and mathematical details---like a transcript of what an expert algorithms tutor would say over a series of one-on-one lessons. Part 2 covers graph search and applications, shortest paths, and the usage and implementation of several data structures (heaps, search trees, hash tables, and bloom filters).

Product Details

ISBN-13:	9780999282922
Publisher:	Soundlikeyourself Publishing, LLC
Publication date:	08/08/2018
Series:	Algorithms Illuminated , #2
Pages:	222
Product dimensions:	6.00(w) x 9.00(h) x 0.47(d)

Table of 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 41

8.5 Topological Sort 45

*8.6 Computing Strongly Connected Components 55

8.7 The Structure of the Web 67

Problems 72

9 Dijkstra’s Shortest-Path Algorithm 77

9.1 The Single-Source Shortest Path Problem 77

9.2 Dijkstra’s Algorithm 81

*9.3 Why Is Dijkstra’s Algorithm Correct? 84

9.4 Implementation and Running Time 90

Problems 93

10 The Heap Data Structure 96

10.1 Data Structures: An Overview 96

10.2 Supported Operations

10.3 Applications

10.4 Speeding Up Dijkstra’s Algorithm 107

*10.5 Implementation Details 113

Problems 123

11 Search Trees 127

11.1 Sorted Arrays 127

11.2 Search Trees: Supported Operations 130

*11.3 Implementation Details 132

*11.4 Balanced Search Trees 146

Problems 150

12 Hash Tables and Bloom Filters 152

12.1 Supported Operations 152

12.2 Applications 156

*12.3 Implementation: High-Level Ideas 160

*12.4 Further Implementation Details 174

12.5 Bloom Filters: The Basics 179

*12.6 Bloom Filters: Heuristic Analysis 185

Problems 192

C Quick Review of Asymptotic Notation 194

C.1 The Gist 194

C.2 Big-O Notation 195

C.3 Examples 196 C.4 Big-Omega and Big-Theta Notation 198

Solutions to Selected Problems 201

Index 204