Advanced Algorithms and Data Structures

Marcello La Rocca

• Publisher: Manning
• Year: 2021
• Print ISBN: 9781617295485
• eBook ISBN: 9781638350224
• Topic: Computer Science
• Subtopic: Data Processing
• Index: Computer Science

"An accessible introduction to the fundamental algorithms used to run the world." - Richard Vaughan, Purple Monkey Collective Advanced Algorithms and Data Structures introduces a collection of algorithms for complex programming challenges in data analysis, machine learning, and graph computing. Summary
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.Purchase of the print book includes a free eBook in PDF, Kindle, and ePub formats from Manning Publications. About the technology
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. About the book
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. What's inside
Build on basic data structures you already know
Profile your algorithms to speed up application
Store and query strings efficiently
Distribute clustering algorithms with MapReduce
Solve logistics problems using graphs and optimization algorithms About the reader
For intermediate programmers. About the author
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. Table of Contents 1 Introducing data structures
PART 1 IMPROVING OVER BASIC DATA STRUCTURES
2 Improving priority queues: d-way heaps
3 Treaps: Using randomization to balance binary search trees
4 Bloom filters: Reducing the memory for tracking content
5 Disjoint sets: Sub-linear time processing
6 Trie, radix trie: Efficient string search
7 Use case: LRU cache
PART 2 MULTIDEMENSIONAL QUERIES
8 Nearest neighbors search
9 K-d trees: Multidimensional data indexing
10 Similarity Search Trees: Approximate nearest neighbors search for image retrieval
11 Applications of nearest neighbor search
12 Clustering
13 Parallel clustering: MapReduce and canopy clustering
PART 3 PLANAR GRAPHS AND MINIMUM CROSSING NUMBER
14 An introduction to graphs: Finding paths of minimum distance
15 Graph embeddings and planarity: Drawing graphs with minimal edge intersections
16 Gradient descent: Optimization problems (not just) on graphs
17 Simulated annealing: Optimization beyond local minima
18 Genetic algorithms: Biologically inspired, fast-converging optimization

1 Introducing data structures

This chapter covers

• Explaining why you should learn about data structures and algorithms
• Understanding the difference between algorithms and data structures
• Abstracting a problem
• Moving from problems to solutions

So, you want to learn about algorithms and data structures: excellent decision!

If you are still deciding whether this is for you, I hope this introductory chapter can dispel your doubts and spark your interest in this great topic.

Why should you learn about algorithms? The short answer is to try to become a better software developer. Knowing about data structures and algorithms is like adding a tool to your tool belt.

Have you ever heard of Maslow’s hammer, aka the law of the instrument? It’s a conjecture, driven by observation, about how people who only know one way to do things tend to apply what they know to all kinds of different situations.

If your tool belt only has a hammer, you will be tempted to treat everything as a nail. If you only know how to sort a list, you will be tempted to sort your tasks list every time you add a new task or have to pick the next one to tackle, and you will never be able to leverage the context to find more efficient solutions.

The purpose of this book is to give you many tools you can use when approaching a problem. We will build upon the basic algorithms normally presented in a computer science 101 course (or the like) and introduce you to more advanced material.

After reading this book, you should be able to recognize situations where you could improve the performance of your code by using a specific data structure and/or algorithm.

Obviously, your goal should not be to remember by heart all the details of all the data structures we will discuss. Rather, we will try to show you how to reason about issues, and where to find ideas about algorithms that might help you in solving problems. This book will also serve as a handbook, sort of like a recipe collection, with indications about some common scenarios that could be used to categorize those problems and the best structures you could use to attack them.

Keep in mind that some topics are quite advanced and, when we delve into the details, it might require a few reads to understand everything. The book is structured in such a way as to provide many levels of in-depth analysis, with advanced sections generally grouped together toward the end of each chapter, so if you’d like to only get an understanding of the topics, you are not required to delve into the theory.

1.1 Data structures

To start with our journey, we first need to agree on a common language to describe and evaluate algorithms.

Describing them is pretty much a standard process: algorithms are described in terms of the input they take and the output they provide. Their details can be illustrated with pseudo-code (ignoring implementation details of programming languages) or actual code.

Data structures (DS) follow the same conventions, but they also go slightly beyond. We also have to describe the actions you can perform on a data structure. Usually each action is described in term of an algorithm, with an input and an output, but in addition to those, for DSs we also need to describe side effects, the changes an action might cause to the data structure itself.

To fully understand what this means, we first need to properly define data structures.

1.1.1 Defining a data structure

A data structure is a specific solution for organizing data that provides storage for items and capabilities¹ for storing and retrieving them.

The simplest example of a DS is an array. For instance, an array of characters provides storage for a finite number of characters and methods to retrieve each character in the array based on its position. Figure 1.1 shows how array = [‘C’, ‘A’, ‘R’] is stored: an array of characters storing the characters C, A, and R, such that, for instance, array[1] corresponds to the value ‘A’.

Figure 1.1 The (simplified) internal representation of an array. Each element of the array in the picture corresponds to a byte of memory,² whose address is shown below it. Each element’s index is shown above it. An array is stored as a contiguous block of memory, and each element’s address can be obtained by adding its index within the array to the offset of the first element. For instance, the fourth character of the array (array[3], empty in the figure), has address 0xFF00 + 3 = 0xFF03.

Data structures can be abstract or concrete:

• An abstract data type (ADT) specifies the operations that can be performed on some data and the computational complexity of those operations. No details are provided on how data is stored or how physical memory is used.
• A data structure (DS) is a concrete implementation of the specification provided by an ADT.

What is an ADT?

You can think about an ADT as the blueprint, while a DS is the translation of those specifications into real code.

An ADT is defined from the point of view of the one who uses it, by describing its behavior in terms of possible values, possible operations on it, and the output and side effects of these operations.

A more formal definition would describe an ADT as a ...

Table of contents

• inside front cover
• Advanced Algorithms and Data Structures
• Copyright
• dedication
• contents
• front matter
• 1 Introducing data structures
• Part 1. Improving over basic data structures
• 2 Improving priority queues: d-way heaps
• 3 Treaps: Using randomization to balance binary search trees
• 4 Bloom filters: Reducing the memory for tracking content
• 5 Disjoint sets: Sub-linear time processing
• 6 Trie, radix trie: Efficient string search
• 7 Use case: LRU cache
• Part 2. Multidimensional queries
• 8 Nearest neighbors search
• 9 K-d trees: Multidimensional data indexing
• 10 Similarity Search Trees: Approximate nearest neighbors search for image retrieval
• 11 Applications of nearest neighbor search
• 12 Clustering
• 13 Parallel clustering: MapReduce and canopy clustering
• Part 3. Planar graphs and minimum crossing number
• 14 An introduction to graphs: Finding paths of minimum distance
• 15 Graph embeddings and planarity: Drawing graphs with minimal edge intersections
• 16 Gradient descent: Optimization problems (not just) on graphs
• 17 Simulated annealing: Optimization beyond local minima
• 18 Genetic algorithms: Biologically inspired, fast-converging optimization
• appendix A. A quick guide to pseudo-code
• appendix B. Big-O notation
• appendix C. Core data structures
• appendix D. Containers as priority queues
• appendix E. Recursion
• appendix F. Classification problems and randomnized algorithm metrics
• index
• inside back cover