Contents......Page 3
Preface......Page 5
Some Vocabulary......Page 10
Few Applications......Page 11
Measuring the Size of Graph......Page 12
Representing a Graph......Page 16
Problems......Page 22
Overview......Page 24
Breadth-first Search & Shortest Paths......Page 34
Computing Connected Components......Page 43
Depth-first Search......Page 49
Topological Sort......Page 54
Computing Strongly Connected Components......Page 63
Structure of the Web......Page 75
Problems......Page 80
Single-Source Shortest Path Problem......Page 85
Dijkstra Algorithm......Page 89
Why is Dijkstra Algorithm correct......Page 92
Implementation & Running Time......Page 98
Problems......Page 100
Data Structures Overview......Page 104
Supported Operations......Page 107
Applications......Page 110
Speeding up Dijkstra Algorithm......Page 115
Implementation Details......Page 121
Problems......Page 132
Sorted Arrays......Page 135
Search Trees Supported Operations......Page 138
Implementation Details......Page 140
Balanced Search Trees......Page 154
Problems......Page 158
Supported Operations......Page 160
Applications......Page 163
Implementation - High-Level Ideas......Page 168
Further Implementation Details......Page 182
Bloom Filters Basics......Page 187
Bloom Filters Heuristic Analysis......Page 193
Problems......Page 199
The Gist......Page 202
Big-O Notation......Page 203
Examples......Page 204
Big-Omega & Big-Theta Notation......Page 206
Solutions......Page 209
Index......Page 212