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