Algorithms and Data Structures in Action
Marcello La Rocca
  • MEAP began July 2019
  • Publication in Fall 2020 (estimated)
  • ISBN 9781617295485
  • 325 pages (estimated)
  • printed in black & white

A different and a great way to introduce algorithms and data structures that can be used at work.

Ursula Cervantes

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. Algorithms and Data Structures in Action 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.

Table of Contents detailed table of contents

1 Introducing Data Structures

1.1 Welcome to Algorithms and Data Structures in Action

1.1.1 Why should you learn about Data Structures?

1.1.2 Algorithms and Data Structures: is there a difference?

1.1.3 Why should you read this book?

1.1.4 What you need to get started

1.2 Data Structures

1.2.1 Defining a Data Structure

1.2.2 Describing a Data Structure

1.3 Setting Goals: Your Expectations After Reading this Book

1.4 Packing your Knapsack: Data Structures Meet the Real World

1.4.1 Abstracting the Problem Away

1.4.2 Looking for Solutions

1.4.3 Algorithms to the Rescue

1.4.4 Thinking (literally) out of the Box

1.4.5 Happy Ending

1.5 Structure of This Book

1.6 Summary

Part 1: Improve Over Basic Data Structures

2 Improve priority queues: d-way heaps

2.1 Structure of this chapter

2.2 The problem: handling priority

2.2.1 Priority in practice: bug tracking

2.3 Solutions at hand: keeping a sorted list

2.3.1 From sorted lists to priority queues

2.4 Describing the data structure API: Priority queues

2.4.1 Priority Queue at work

2.4.2 Priority Matters: Generalize FIFO

2.5 Concrete Data Structures

2.5.1 Comparing performance

2.5.2 What’s the right concrete data structure?

2.5.3 Heap

2.5.4 Priority, min-heap and max-heap

2.5.5 Advanced variant: d-ary heap

2.6 How to implement a heap

2.6.1 BubbleUp

2.6.2 PushDown

2.6.3 Insert

2.6.4 Top

2.6.5 Update

2.6.6 Dealing with Duplicates

2.6.7 Heapify

2.6.8 Beyond API methods: contains

2.6.9 Performance recap

2.6.10 From Pseudo-code to implementation

2.7 Use case: find the k largest elements

2.7.1 The right data structure…​

2.7.2 …​ and the right use

2.7.3 Coding it up

2.8 More use-cases

2.8.1 Minimum distance in graphs: Dijkstra

2.8.2 Beyond Dijkstra: BFS, A*

2.8.3 More graphs: Prim’s algorithm

2.8.4 Data Compression: Huffman Codes

2.9 [Advanced] Analysis of branching factor

2.9.1 Do we need D-ary heaps?

2.9.2 Running time

2.9.3 Finding the optimal branching factor

2.9.4 Branching factor vs memory

2.10 Summary

3 Treap: Use priority to improve binary search trees

4 Bloom Filters: Reduce memory needed to keep track of content

5 Disjoint Set: Keep a dynamic list of distinct subsets

6 Use case: LRU Cache

7 Further improvement on cache: Splay Trees

Part 2: Multi-dimensional queries

8 Nearest Neighbors search

8.1 The Nearest Neighbors Search Problem

8.2 Solutions

8.2.1 First Attempts

8.2.2 Sometimes Caching is NOT the Answer

8.2.3 Simplify Things to Get a Hint

8.2.4 Carefully Choose a Data Structure

8.3 Description and API

8.4 Moving to k-dimensional Spaces

8.4.2 Moving to Higher Dimensions

8.4.3 Modeling 2D Partitions with a Data Structure

8.5 Summary

9 K-d Trees: Multi-dimensional Data Indexing

9.1 Right Where We Left

9.2 Moving to k-D Spaces: Cycle Through Dimensions

9.2.1 Constructing the BST

9.2.2 Invariants

9.2.3 The Importance of Being Balanced

9.3 Methods

9.3.2 Insert

9.3.3 Balanced Tree

9.3.4 Remove

9.3.5 Nearest Neighbor

9.3.7 A Recap of all Methods

9.4 Limits and Possible Improvements

9.5 Summary

10 S-Trees

11 Applications of Nearest Neighbors Search

12 Use case: DBSCAN/OPTICS clustering algorithms

Part 3: Planar Graphs and Minimum Crossing Number

13 Planarity and Crossing Number

14 Gradient Descent to find MCN

15 Extending GD with Simulated Annealing to Find Global Minimum

16 Using Genetic Algorithms for Faster Convergence


Appendix A: A Quick Guide to Pseudo-Code

A.1 Variables and Basics

A.2 Arrays

A.3 Conditional Instructions

A.3.1 Else-if

A.3.2 Switch

A.4 Loops

A.4.1 For Loop

A.4.2 While Loop

A.4.3 Break and Continue

A.5 Blocks and Indent

A.6 Functions

A.6.1 Overloading and default arguments

A.6.2 Tuples

A.6.3 Tuples and destructuring objects

Appendix B: Big-O Notation

B.1 Algorithms and Performance

B.2 The RAM Model

B.3 Order of Magnitude

B.4 Notation

B.5 Examples

Appendix C: Core Data Structures

C.1 Core Data Structures

C.1.1 Array

C.1.2 Linked List

C.1.3 Tree

C.1.4 Starting drag operations

C.2 Hash Table

C.2.1 Storing key-value pairs

C.2.2 Hashing

C.2.3 Conflicts Resolution in Hashing

C.2.4 Performance

C.3 Comparative Analysis of Core Data Structures

Appendix D: Containers as priority queues

D.1 Bag

D.2 Stack

D.3 Queue

D.4 A Comparative Analysis for Containers

Appendix E: Recursion

E.1 Simple Recursion

E.1.1 Pitfalls

E.1.2 Good Recursion

E.1.3 Tail Recursion

E.1.4 Mutual Recursion

Appendix F: Classification problems Randomized algorithms Metrics

F.1 Decision Problems

F.2 Las Vegas Algorithms

F.3 Monte Carlo Algorithms

F.4 Classification Metrics

F.4.1 Accuracy

F.4.2 Precision and Recall

F.4.3 Other Metrics + Recap

Appendix G: A short Introduction to Graphs

About the Technology

Data structures and algorithms are the foundations for how programs store and process information. Choosing the optimal algorithms ensures that your programs are fast, efficient, and reliable.

About the book

Algorithms and Data Structures in Action introduces you to a diverse range of algorithms you’ll use in web applications, systems programming, and data manipulation. Chapter-by-chapter, the book expands on the basic algorithms you’ll already know to give you a better selection of solutions to different programming problems. In it, you’ll discover techniques for improving priority queues, efficient caching, clustering data, and more. Each example is fully illustrated with graphics, language-agnostic pseudo-code, and code samples in various languages. When you’re done, you will be able to implement advanced and little-known algorithms to deliver better performance from your code. You’ll even have the skills to design your own data structures to solve those cases when a custom solution is required.

What's inside

  • Improving on basic data structures
  • Efficient caching
  • Nearest neighbour search, including k-d trees and S-trees
  • Full ‘pseudo-code’ and samples in multiple languages

About the reader

For programmers with basic or intermediate skills. Written in a language-agnostic manner, no specific language knowledge is required.

About the author

Marcello La Rocca is a research scientist and a full-stack engineer focused on optimization algorithms, genetic algorithms, machine learning and quantum computing. He has contributed to large-scale web applications at companies like Twitter and Microsoft, has undertaken applied research in both academia and industry, and authored the Neatsort adaptive sorting algorithm.

Manning Early Access Program (MEAP) Read chapters as they are written, get the finished eBook as soon as it’s ready, and receive the pBook long before it's in bookstores.
MEAP combo $49.99 pBook + eBook + liveBook
MEAP eBook $39.99 pdf + ePub + kindle + liveBook
Prices displayed in rupees will be charged in USD when you check out.

placing your order...

Don't refresh or navigate away from the page.

FREE domestic shipping on three or more pBooks