La Rocca Marcello - Advanced Algorithms and Data Structures [2021, PDF/EPUB, ENG] + code

foreword xv
preface xvii
acknowledgments xix
about this book xxi
about the author xxvi
about the cover illustration xxvii
1 Introducing data structures 1
1.1 Data structures 2
1.2 Setting goals: Your expectations after reading this book 6
1.3 Packing your knapsack: Data structures meet the real world 7
PART 1 IMPROVING OVER BASIC DATA STRUCTURES ................13
2 Improving priority queues: d-way heaps 15
2.1 Structure of this chapter 16
2.2 The problem: Handling priority 17
2.3 Solutions at hand: Keeping a sorted list 19
2.4 Describing the data structure API: Priority queues 19
2.5 Concrete data structures 22
2.6 How to implement a heap 28
2.7 Use case: Find the k largest elements 47
2.8 More use cases 49
2.9 Analysis of branching factor 55
2.10 Performance analysis: Finding the best branching factor 58
3 Treaps: Using randomization to balance binary search trees 69
3.1 Problem: Multi-indexing 70
3.2 Solution: Description and API 71
3.3 Treap 72
3.4 Applications: Randomized treaps 91
3.5 Performance analysis and profiling 97
4 Bloom filters: Reducing the memory for tracking content 110
4.1 The dictionary problem: Keeping track of things 111
4.2 Alternatives to implementing a dictionary 113
4.3 Describing the data structure API: Associative array 114
4.4 Concrete data structures 115
4.5 Under the hood: How do Bloom filters work? 120
4.6 Implementation 122
4.7 Applications 132
4.8 Why Bloom filters work 135
4.9 Performance analysis 138
4.10 Estimating Bloom filter precision 139
4.11 Improved variants 144
5 Disjoint sets: Sub-linear time processing 147
5.1 The distinct subsets problem 148
5.2 Reasoning on solutions 151
5.3 Describing the data structure API: Disjoint set 153
5.4 Naive solution 154
5.5 Using a tree-like structure 159
5.6 Heuristics to improve the running time 162
5.7 Applications 168
6 Trie, radix trie: Efficient string search 173
6.1 Spell-check 174
6.2 Trie 177
6.3 Radix tries 197
6.4 Applications 211
7 Use case: LRU cache 218
7.1 Don’t compute things twice 219
7.2 First attempt: Remembering values 222
7.3 Memory is not enough (literally) 228
7.4 Getting rid of stale data: LRU cache 230
7.5 When fresher data is more valuable: LFU 238
7.6 How to use cache is just as important 244
7.7 Introducing synchronization 245
7.8 Cache applications 254
PART 2 MULTIDIMENSIONAL QUERIES ...............................257
8 Nearest neighbors search 259
8.1 The nearest neighbors search problem 260
8.2 Solutions 261
8.3 Description and API 266
8.4 Moving to k-dimensional spaces 268
9 K-d trees: Multidimensional data indexing 273
9.1 Right where we left off 274
9.2 Moving to k-D spaces: Cycle through dimensions 275
9.3 Methods 282
9.4 Limits and possible improvements 316
10 Similarity Search Trees: Approximate nearest neighbors search for
10.1 Right where we left off 320
10.2 R-tree 322
10.3 Similarity search tree 330
10.4 Similarity Search 359
10.5 SS+-tree 367
11 Applications of nearest neighbor search 375
11.1 An application: Find nearest hub 376
11.2 Centralized application 380
11.3 Moving to a distributed application 386
11.4 Other applications 391
12 Clustering 400
12.1 Intro to clustering 401
12.2 K-means 405
12.3 DBSCAN 418
12.4 OPTICS 426
12.5 Evaluating clustering results: Evaluation metrics 442
13 Parallel clustering: MapReduce and canopy clustering 448
13.1 Parallelization 449
13.2 MapReduce 455
13.3 MapReduce k-means 463
13.4 MapReduce DBSCAN 475
PART 3 PLANAR GRAPHS AND MINIMUM CROSSING NUMBER....483
14 An introduction to graphs: Finding paths of minimum
14.1 Definitions 486
14.2 Graph properties 491
14.3 Graph traversal: BFS and DFS 495
14.4 Shortest path in weighted graphs: Dijkstra 507
14.5 Beyond Dijkstra’s algorithm: A* 513
15 Graph embeddings and planarity: Drawing graphs with minimal
15.1 Graph embeddings 523
15.2 Planar graphs 528
15.3 Non-planar graphs 539
15.4 Edge intersections 545
16 Gradient descent: Optimization problems (not just) on graphs 558
16.1 Heuristics for the crossing number 560
16.2 How optimization works 568
16.3 Gradient descent 574
16.4 Applications of gradient descent 581
16.5 Gradient descent for graph embedding 585
17 Simulated annealing: Optimization beyond local minima 591
17.1 Simulated annealing 593
17.2 Simulated annealing + traveling salesman 604
17.3 Simulated annealing and graph embedding 615
18 Genetic algorithms: Biologically inspired, fast-converging optimization 624
18.1 Genetic algorithms 625
18.2 TSP 652
18.3 Minimum vertex cover 661
18.4 Other applications of the genetic algorithm 665
appendix A A quick guide to pseudo-code 671
appendix B Big-O notation 682
appendix C Core data structures 690
appendix D Containers as priority queues 704
appendix E Recursion 708
appendix F Classification problems and randomnized algorithm metrics 716
index 723