As a software engineer, you’ll encounter countless programming challenges that initially seem confusing, difficult, or even impossible. Don’t despair! Many of these “new” problems already have well-established solutions. Advanced Algorithms and Data Structures teaches you powerful approaches to a wide …
As a software engineer, you’ll encounter countless programming challenges that initially seem confusing, difficult, or even impossible. Don’t despair! Many of these “new” problems already have well-established solutions. Advanced Algorithms and Data Structures teaches you powerful approaches to a wide range of tricky coding challenges that you can adapt and apply to your own applications. Providing a balanced blend of classic, advanced, and new algorithms, this practical guide upgrades your programming toolbox with new perspectives and hands-on techniques.
Can you improve the speed and efficiency of your applications without investing in new hardware? Well, yes, you can: Innovations in algorithms and data structures have led to huge advances in application performance. Pick up this book to discover a collection of advanced algorithms that will make you a more effective developer.
Advanced Algorithms and Data Structures introduces a collection of algorithms for complex programming challenges in data analysis, machine learning, and graph computing. You’ll discover cutting-edge approaches to a variety of tricky scenarios. You’ll even learn to design your own data structures for projects that require a custom solution.
For intermediate programmers.
Marcello La Rocca is a research scientist and a full-stack engineer. His focus is on optimization algorithms, genetic algorithms, machine learning, and quantum computing.
Easy to follow and filled with practical examples, this book is a fantastic introduction to data structures and algorithms.Chapter 1 Introducing data structures
Part 1. Improving over basic data structures
Chapter 1 Describing a data structure
Chapter 1 Packing your knapsack: Data structures meet the real world
Chapter 1 Algorithms to the rescue
Chapter 2 Improving priority queues: d-way heaps
Chapter 2 Solutions at hand: Keeping a sorted list
Chapter 2 Concrete data structures
Chapter 2 Priority, min-heap, and max-heap
Chapter 2 How to implement a heap
Chapter 2 PushDown
Chapter 2 Top
Chapter 2 Heapify
Chapter 2 Use case: Find the k largest elements
Chapter 2 More use cases
Chapter 2 Analysis of branching factor
Chapter 2 Performance analysis: Finding the best branching factor
Chapter 2 Interpreting results
Chapter 2 The mystery with heapify
Chapter 3 Treaps: Using randomization to balance binary search trees
Chapter 3 Treap
Chapter 3 A few design questions
Chapter 3 Delete
Chapter 3 Applications: Randomized treaps
Chapter 3 Performance analysis and profiling
Chapter 3 Profiling height
Chapter 3 Profiling memory usage
Chapter 4 Bloom filters: Reducing the memory for tracking content
Chapter 4 Alternatives to implementing a dictionary
Chapter 4 Concrete data structures
Chapter 4 Binary search tree: Every operation is logarithmic
Chapter 4 Implementation
Chapter 4 Constructor
Chapter 4 Applications
Chapter 4 Why Bloom filters work
Chapter 4 Performance analysis
Chapter 4 Explanation of the false-positive ratio formula
Chapter 4 Improved variants
Chapter 5 Disjoint sets: Sub-linear time processing
Chapter 5 Reasoning on solutions
Chapter 5 Naïve solution
Chapter 5 Using a tree-like structure
Chapter 5 Heuristics to improve the running time
Chapter 5 Applications
Chapter 6 Trie, radix trie: Efficient string search
Chapter 6 Trie
Chapter 6 Search
Chapter 6 Insert
Chapter 6 Keys matching a prefix
Chapter 6 Radix tries
Chapter 6 Search
Chapter 6 Applications
Chapter 6 String sorting
Chapter 7 Use case: LRU cache
Chapter 7 First attempt: Remembering values
Chapter 7 Handling asynchronous calls
Chapter 7 Memory is not enough (literally)
Chapter 7 Getting rid of stale data: LRU cache
Chapter 7 Temporal ordering
Chapter 7 When fresher data is more valuable: LFU
Chapter 7 How to use cache is just as important
Chapter 7 Solving concurrency (in Java)
Chapter 7 Read locks
Part 2. Multidimensional queries
Chapter 8 Nearest neighbors search
Chapter 8 Simplifying things to get a hint
Chapter 8 Moving to k-dimensional spaces
Chapter 9 K-d trees: Multidimensional data indexing
Chapter 9 Constructing the BST
Chapter 9 Methods
Chapter 9 Balanced tree
Chapter 9 Remove
Chapter 9 Nearest neighbor
Chapter 9 Region search
Chapter 10 Similarity Search Trees: Approximate nearest neighbors search for image retrieval
Chapter 10 R-tree
Chapter 10 Inserting points in an R-tree
Chapter 10 Similarity search tree
Chapter 10 SS-tree search
Chapter 10 Insert
Chapter 10 Insertion: Split nodes
Chapter 10 Delete
Chapter 10 Similarity Search
Chapter 10 Approximated similarity search
Chapter 10 SS+-tree
Chapter 10 Reducing overlap
Chapter 11 Applications of nearest neighbor search
Chapter 11.Centralized application
Chapter 11 Moving to a distributed application
Chapter 11 Other applications
Chapter 11 Multidimensional DB queries optimization
Chapter 12 Clustering
Chapter 12 Types of learning
Chapter 12 K-means
Chapter 12 The curse of dimensionality strikes again
Chapter 12 Boosting k-means with k-d trees
Chapter 12 DBSCAN
Chapter 12 From definitions to an algorithm
Chapter 12 And finally, an implementation
Chapter 12 OPTICS
Chapter 12 From reachability distance to clustering
Chapter 12 Hierarchical clustering
Chapter 12. Evaluating clustering results: Evaluation metrics
Chapter 13 Parallel clustering: MapReduce and canopy clustering
Chapter 13 Canopy clustering
Chapter 13 MapReduce
Chapter 13 First map, then reduce
Chapter 13 MapReduce k-means
Chapter 13 Parallelizing canopy clustering
Chapter 13 MapReduce canopy clustering
Chapter 13 MapReduce DBSCAN - Part 1
Chapter 13 MapReduce DBSCAN - Part 2
Part 3. Planar graphs and minimum crossing number
Chapter 14 An introduction to graphs: Finding paths of minimum distance
Chapter 14 Implementing graphs
Chapter 14 Graph properties
Chapter 14 Graph traversal: BFS and DFS
Chapter 14 Reconstructing the path to target
Chapter 14 Shortest path in weighted graphs: Dijkstra
Chapter 14 Beyond Dijkstra’s algorithm: A*
Chapter 14 How good is A* search?
Chapter 14 Heuristics as a way to balance real-time data
Chapter 15 Graph embeddings and planarity: Drawing graphs with minimal edge intersections
Chapter 15 Some basic definitions
Chapter 15 Planar graphs
Chapter 15 Planarity testing
Chapter 15 Improving performance
Chapter 15 Non-planar graphs
Chapter 15 Rectilinear crossing number
Chapter 15 Edge intersections
Chapter 15 Polylines
Chapter 15 Intersections between quadratic Bézier curves
Chapter 16 Gradient descent: Optimization problems (not just) on graphs
Chapter 16 Did you just say heuristics?
Chapter 16 How optimization works
Chapter 16 Gradient descent
Chapter 16 When is gradient descent appliable?
Chapter 16 Applications of gradient descent
Chapter 16 Gradient descent for graph embedding
Chapter 17 Simulated annealing: Optimization beyond local minima
Chapter 17 Sometimes you need to climb up to get to the bottom
Chapter 17 Why simulated annealing works
Chapter 17 Short-range vs long-range transitions
Chapter 17 Simulated annealing + traveling salesman
Chapter 17 Exact vs approximated solutions
Chapter 17 State transitions
Chapter 17 Simulated annealing and graph embedding
Chapter 17 Force-directed drawing
Chapter 18 Genetic algorithms: Biologically inspired, fast-converging optimization
Chapter 18 Inspired by nature
Chapter 18 Chromosomes
Chapter 18 Natural selection
Chapter 18 Selecting individuals for mating
Chapter 18 Crossover
Chapter 18 The genetic algorithm template
Chapter 18 TSP
Chapter 18 Results and parameters tuning
Chapter 18 Minimum vertex cover
Chapter 18 Other applications of the genetic algorithm
Chapter 18 Beyond genetic algorithms
Appendix A. A quick guide to pseudo-code
Appendix A Conditional instructions
Appendix A Blocks and indent
Appendix B. Big-O notation
Appendix B Notation
Appendix C. Core data structures
Appendix C Tree
Appendix C Hash table
Appendix D. Containers as priority queues
Appendix E. Recursion
Appendix E Tail recursion
Appendix F. Classification problems and randomnized algorithm metrics
Appendix F Classification metrics