Algorithms - Parallel and Sequential

Contents......Page 3
Parallelism......Page 15
Parallel Hardware......Page 16
Parallel Software......Page 17
Work and Span......Page 18
Work Efficiency......Page 20
Algorithm Specification......Page 22
Problem......Page 23
Implementation......Page 24
Background......Page 26
Sequencing Methods......Page 27
Genome Sequencing Problem......Page 29
Understanding the Structure of the Problem......Page 31
Brute Force......Page 32
Brute Force Reloaded......Page 33
Traveling Salesperson Problem......Page 35
Reducing Shortest Superstrings to TSP......Page 36
Greedy Algorithm......Page 38
Concluding Remarks......Page 41
Background......Page 43
Sets......Page 44
Relations......Page 46
Basic Definitions......Page 47
Weighted Graphs......Page 50
Subgraphs......Page 51
Connectivity......Page 52
Graph Partition......Page 53
Trees......Page 54
Language for specifying Algorithms......Page 56
Syntax and Semantics......Page 57
Parallelism and Reduction Order......Page 58
Syntax and Semantics of SPARC......Page 60
Derived Syntax for Loops......Page 68
Pure Functions......Page 70
Safe for Parallelism......Page 71
Benign Effects......Page 73
Functions as Values......Page 74
Functional Algorithms......Page 75
Analysis of Algorithms......Page 76
Basics......Page 77
Big-O, big-Omega, and big-Theta......Page 78
Some Conventions......Page 81
RAM Model......Page 83
PRAM: Parallel Random Access Machine......Page 84
Language Based Models......Page 85
The Work-Span Model......Page 86
Scheduling......Page 89
The Basics......Page 92
Some conventions......Page 93
The Tree Method......Page 95
The Brick Method......Page 96
Substitution Method......Page 101
Master Method......Page 103
Sequences......Page 104
Defining Sequences......Page 105
The Abstract Data Type......Page 108
Tabulate......Page 110
Map and Filter......Page 111
Subsequences......Page 112
Update and Inject......Page 113
Collect......Page 114
Aggregation by Iteration......Page 115
Aggregation by Reduction......Page 118
Aggregation with Scan......Page 119
A Parametric Implementation......Page 123
An Array-Based Implementation......Page 126
Cost Specifications......Page 128
Array Sequences......Page 129
Tree Sequences......Page 135
List Sequences......Page 136
Miscellaneous Examples......Page 138
Computing Primes......Page 142
Persistent and Emphemeral Implementations......Page 146
Single-Threaded Sequences......Page 147
Implementation......Page 149
Algorithm Design & Analysis......Page 150
Algorithmic Reduction......Page 151
Brute Force......Page 152
Divide and Conquer......Page 156
Merge Sort......Page 159
Sequence Scan......Page 160
Euclidean Traveling Salesperson Problem......Page 161
Divide and Conquer with Reduce......Page 164
Contraction Technique......Page 165
Reduce with Contraction......Page 166
Scan with Contraction......Page 168
The Problem......Page 171
Brute Force......Page 173
Applying Reduction......Page 175
Auxiliary Problems......Page 176
Reduction to MCSSS......Page 177
Reduction to MCSSE......Page 178
A First Solution......Page 181
Divide And Conquer with Strengthening......Page 185
Probability......Page 190
Probability Spaces......Page 191
The Union Bound......Page 193
Law of Total Probability......Page 194
Independence......Page 195
Random Variables......Page 197
Probability Mass Function......Page 198
Bernoulli, Binomial, and Geometric RVs......Page 199
Functions of Random Variables......Page 200
Conditioning......Page 201
Independence......Page 202
Definitions......Page 203
Markov's Inequality......Page 204
Composing Expectations......Page 205
Linearity of Expectations......Page 206
Conditional Expectation......Page 207
Randomization......Page 208
Randomized Algorithms......Page 209
Advantages of Randomization......Page 210
Analysis of Randomized Algorithms......Page 212
Randomized Algorithm for Order Statistics......Page 215
Intuitive Analysis......Page 217
Complete Analysis......Page 218
The Quick Sort Algorithm......Page 222
Analysis of Quick Sort......Page 224
Intuition......Page 225
The Analysis......Page 226
Alternative Analysis of Quick Sort......Page 231
Concluding Remarks......Page 232
Binary Search Trees......Page 233
Motivation......Page 234
Preliminaries......Page 235
The Interface......Page 236
Implementation via Balancing......Page 239
Parametric BSTs......Page 242
The Data Structure......Page 243
Cost Specification......Page 245
Cost of Union, Intersection, and Difference......Page 246
Treap Data Structure......Page 252
Height Analysis of Treaps......Page 256
Augmenting with Size......Page 258
Example: Rank and Select in BSTs......Page 259
Augmenting with Reduced Values......Page 261
Sets & Tables......Page 265
Motivation......Page 266
Sets ADT......Page 267
Cost of Sets......Page 270
Interface......Page 273
Cost Specification for Tables......Page 277
Ordered Sets Interface......Page 278
Interface: Augmented Ordered Tables......Page 280
Example - Indexing & Searching......Page 282
Graphs......Page 286
Graphs and Relations......Page 287
Applications of Graphs......Page 288
Graphs Representations......Page 290
Edge Sets......Page 291
Adjacency Tables......Page 292
Adjacency Sequences......Page 293
Adjacency Matrices......Page 295
Representing Weighted Graphs......Page 296
Generic Graph Search......Page 298
Reachability......Page 300
Priority-First Search (PFS)......Page 301
BFS and Distances......Page 303
Sequential BFS......Page 304
Cost of Sequential BFS......Page 305
Parallel BFS......Page 306
Cost of Parallel BFS......Page 308
Shortest Paths and Shortest-Path Trees......Page 310
Cost with Sequences......Page 313
DFS Reachability......Page 314
DFS Trees......Page 316
DFS Numbers......Page 318
Cost of DFS......Page 320
Parallel DFS......Page 321
Cycle Detection......Page 322
Topological Sort......Page 323
Strongly Connected Components (SCC)......Page 326
Path Weights......Page 332
The Sub-Paths Property......Page 334
Dijkstra's Property......Page 337
Dijkstra's Algorithm with Priority Queues......Page 340
Cost Analysis of Dijkstra's Algorithm......Page 344
Graphs with Negative Edge Weights......Page 346
Bellman-Ford's Algorithm......Page 348
Cost Analysis......Page 352
Johnson Algorithm......Page 355