Algorithms illuminated Part 2 Graph Algorithms and Data Structures

Preface......Page 7
 Some Vocabulary......Page 13
 A Few Applications......Page 14
 Measuring the Size of a Graph......Page 15
 Representing a Graph......Page 19
 Problems......Page 25
 Overview......Page 27
 Breadth-First Search and Shortest Paths......Page 37
 Computing Connected Components......Page 46
 Depth-First Search......Page 52
 Topological Sort......Page 57
 Computing Strongly Connected Components......Page 66
 The Structure of the Web......Page 78
 Problems......Page 83
 The Single-Source Shortest Path Problem......Page 88
 Dijkstra's Algorithm......Page 92
 Why Is Dijkstra's Algorithm Correct?......Page 95
 Implementation and Running Time......Page 101
 Problems......Page 103
 Data Structures: An Overview......Page 107
 Supported Operations......Page 110
 Applications......Page 113
 Speeding Up Dijkstra's Algorithm......Page 118
 Implementation Details......Page 124
 Problems......Page 135
 Sorted Arrays......Page 138
 Search Trees: Supported Operations......Page 141
 Implementation Details......Page 143
 Balanced Search Trees......Page 157
 Problems......Page 161
 Supported Operations......Page 163
 Applications......Page 166
 Implementation: High-Level Ideas......Page 171
 Further Implementation Details......Page 185
 Bloom Filters: The Basics......Page 190
 Bloom Filters: Heuristic Analysis......Page 196
 Problems......Page 202
 The Gist......Page 205
 Big-O Notation......Page 206
 Examples......Page 207
 Big-Omega and Big-Theta Notation......Page 209
Solutions to Selected Problems......Page 212
Index......Page 215