1 Starting a fabulous adventure

This chapter introduces a playful, curiosity-driven lens on algorithms and data structures—what makes them “fabulous.” The author celebrates solutions born from real problems that go off the beaten path, counterintuitive wins like embracing immutability for clarity and robustness, and patterns that transfer across domains (for example, backtracking powering search, map coloring, sudoku, and pretty printing). The joy comes from emphasizing meaning over mechanisms, marveling at “magic trick” data structures, exploiting language features to their fullest, reframing problems for dramatic speedups, connecting practice to theory, and simply having fun. The book aims to take readers beyond the standard curriculum, adding practical tools while reshaping how they think about programming.

After setting the tone, the chapter defines data structures as organized ways to store information and algorithms as finite procedures (not necessarily deterministic or computer-bound) for solving problems. Complexity measures how cost (time, memory, or other resources) grows with problem size, using Big-O notation: constant, logarithmic, linear, quasilinear, quadratic, exponential, and factorial, each illustrated with everyday tasks and cautions about “accidentally quadratic” designs. It emphasizes choosing the right notion of size (elements, height, etc.) and the right cost model (time vs. memory; best-, average-, worst-case). A key lesson: asymptotically better is not always practically better—workloads with short inputs may favor simpler algorithms despite worse worst-case bounds.

The warmup builds an immutable linked list in C#, then reverses it by iterating and pushing onto a new list—an O(n) time and space solution that preserves the original. Along the way, subtle design and performance pitfalls surface: representing emptiness safely, avoiding expensive or recursive value equality that risks stack overflows, and fixing accidentally quadratic string concatenation. The road ahead promises twists on familiar structures (stacks, queues, trees), persistence and memoization, elegant list reorderings, a startling near-constant-time reverse trick, backtracking for coloring and pretty printing, unification and anti-unification, and a final toolkit for probability and Bayesian inference, with occasional detours into the shared abstractions of category theory. Though examples use C#, the ideas generalize broadly.

A graph comparing the growth curves for logarithmic, linear, quasilinear, quadratic and exponential growth. Logarithmic is the shallowest curve, growing very slowly, and exponential is the fastest.

• There are lots of books about standard data structures such as lists, trees and hash tables, and the algorithms for sorting and searching them. And there are lots of implementations of them already in class libraries. In this book we’ll look at the less well-known, more off-the-beaten-path data structures and algorithms that I had to learn about during my career. I’ve chosen the topics I found the most fabulous: the ones that are counterintuitive, or seemingly magical, or that push boundaries of languages.
• I had to learn about almost all the topics in this book when I needed a new tool in my toolbox to solve a job-related problem. I hope this book saves you from having to read all the abstruse papers that I had to digest if you too have such a problem to solve.
• But more important to me is that all these fabulous adventures gave me a deeper appreciation for what computer programmers are capable of. They changed how I think about the craft of programming. And I had a lot of fun along the way! I hope you do too.
• Asymptotic complexity gives a measurement of how a solution scales to the size of the problem you’re throwing at it. We generally want algorithms to be better than quadratic if we want them to scale to large problems.
• Complexity analysis can be subtle. It’s important to remember that time is not the only resource users care about, and that they might also have opinions on whether avoiding a bad worst-case scenario is more or less important than achieving an excellent average performance.
• If problems are always small, then asymptotic complexity matters less.
• Reversing a linked list is straightforward if you have an immutable list! We’ll look at other kinds of immutable lists next.

FAQ