Real-World Algorithms. A Beginner’s Guide

Description

Contents......Page 3 Preface......Page 7 Stock Spans......Page 15 Algorithms......Page 17 Running Times & Complexity......Page 21 Stock Span using a Stack......Page 29 Notes......Page 35 Exploring the Labyrinth......Page 38 Graphs......Page 40 Graph Representation......Page 46 Depth-First Graph Traversal......Page 53 Breadth-First Search......Page 63 Notes......Page 68 Compressing......Page 72 Compression......Page 75 Trees & Priority Queues......Page 78 Huffman Coding......Page 82 Lempel-Ziv-Welch Compression......Page 90 Notes......Page 103 Secrets......Page 105 Decryption Challenge......Page 106 One-Time Pad......Page 111 AES Cipher......Page 116 Diffie-Hellman Key Exchange......Page 124 Fast & Modular Exponentiation......Page 129 Notes......Page 134 Split Secrets......Page 137 Public Key Cryptography......Page 138 RSA Cryptosystem......Page 141 Message Hashing......Page 151 Internet Traffic Anonymization......Page 153 Notes......Page 159 Tasks in Order......Page 161 Topological Sort......Page 162 Weighted Graphs......Page 168 Critical Paths......Page 170 Notes......Page 180 Lines, Paragraphs, Paths......Page 181 Shortest Paths......Page 184 Dijkstra Algorithm......Page 187 Notes......Page 195 Routing, Arbitrage......Page 197 Internet Routing......Page 201 Bellman-Ford(-Moore) Algorithm......Page 206 Negative Weights & Cycles......Page 213 Arbitrage......Page 217 Notes......Page 222 What’s Most Important......Page 223 PageRank Idea......Page 224 Hyperlink Matrix......Page 226 Power Method......Page 228 Google Matrix......Page 232 Notes......Page 237 Voting Strengths......Page 238 Voting Systems......Page 239 Shulze Method......Page 242 Floyd-Warshall Algorithm......Page 254 Notes......Page 256 Brute Forces, Secretaries & Dichotomies......Page 257 Sequential Search......Page 258 Matching, Comparing, Records, Keys......Page 260 Matthew Effect & Power Laws......Page 262 Self-organizing Search......Page 269 Secretary Problem......Page 273 Binary Search......Page 276 Representing Integers......Page 281 Binary Search revisited......Page 286 Comparison Trees......Page 288 Notes......Page 293 Menagerie of Sorts......Page 295 Selection Sort......Page 296 Insertion Sort......Page 300 Heapsort......Page 305 Merge Sort......Page 312 Quicksort......Page 326 Spoilt for Choice......Page 334 Notes......Page 337 The Cloakroom, the Pigeon & the Bucket......Page 339 Mapping Keys to Values......Page 340 Hashing......Page 345 Hashing Functions......Page 347 Floating Point Representation & Hashing......Page 355 Collisions......Page 358 Digital Fingerprints......Page 367 Bloom Filters......Page 372 Notes......Page 384 Bits & Trees......Page 387 Divination as Communications Problem......Page 388 Information & Entropy......Page 391 Classification......Page 396 Decision Trees......Page 398 Attribute Selection......Page 401 ID3 Algorithm......Page 408 Underlying Machinery......Page 415 Occam Razor......Page 421 Cost, Problems, Improvements......Page 423 Notes......Page 427 Stringing Along......Page 430 Brute Force String Matching......Page 433 Knuth-Morris-Pratt Algorithm......Page 436 Boyer-Moore-Horspool Algorithm......Page 448 Notes......Page 456 Leave to Chance......Page 458 Random Numbers......Page 460 Random Sampling......Page 468 Power Games......Page 474 Searching for Primes......Page 486 Notes......Page 495 Biblio......Page 498 Index......Page 509