This opening chapter sets the stage by explaining what algorithms and data structures are and why some feel “fabulous.” The author highlights qualities that make certain ideas stand out: solving real problems off the beaten path, embracing counterintuitive techniques like immutability for undo/redo, spotting patterns that transfer across domains, and writing code that reflects problem meaning rather than just mechanisms. It also celebrates solutions that look like magic at first glance, clever use of language features (especially in C#), reframing problems for dramatic gains (as with HashLife), drawing energizing connections to theory, and, above all, keeping programming fun.
The chapter then gives crisp working definitions and a practical view of complexity. A data structure is an organized way to store information; an algorithm is a finite procedure to solve a problem and can be nondeterministic or even non-computational in execution. Complexity characterizes how cost grows with input size, illustrated through common classes—constant, logarithmic, linear, quasilinear, quadratic, and explosive exponential/factorial—along with guidance on choosing the right “size” metric and remembering costs beyond time, like memory. It cautions that asymptotically superior methods aren’t always best for typical workloads and reminds readers to consider best/average/worst cases when evaluating real-world performance.
To ground the ideas, the chapter builds a minimal immutable linked list in C#, using records and a sentinel for the empty list, and reviews both design tradeoffs and performance. It shows how small choices can hide costs: Push is O(1), but record-generated equality can recurse and risk stack overflows; a naive ToString is accidentally quadratic; and an improved emptiness check avoids unnecessary work. Reversing the immutable list is presented as a clear O(n) time and space routine that preserves the original. The chapter closes with a roadmap: classic structures with modern twists, persistence and memoization, surprising list tricks, backtracking for tasks from graph coloring to pretty printing, unification and anti-unification, and a practical toolkit for probability and Bayesian inference—punctuated by occasional theory interludes—all expressed in C# but broadly applicable.
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.
Summary
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
What does this chapter mean by “fabulous” algorithms and data structures?
They are solutions that:
- Solve real problems off the beaten path (e.g., learning anti-unification from research papers).
- Achieve counterintuitive results (e.g., undo/redo via immutable data).
- Apply across domains (e.g., backtracking for trees, map coloring, Sudoku, pretty printing).
- Emphasize meaning over mechanisms (code that reflects problem concepts).
- Feel like magic tricks (e.g., the Hughes list).
- Exploit language features deeply (e.g., C# generics vs C++ templates).
- Reframe problems to change the game (e.g., HashLife’s immutable quadtrees).
- Connect to theory (e.g., shared patterns across types).
- Keep programming fun and exploratory.
How does the chapter define a data structure, an algorithm, and complexity?
- Data structure: An organized way to store information.
- Algorithm: A finite sequence of steps to solve a problem; can be nondeterministic and need not run on a computer.
- Complexity: The relationship between problem size and cost (time, memory, etc.).
What common complexity classes are discussed, and what are their examples?
- O(1): Constant time (e.g., get first array element).
- O(log n): Logarithmic (e.g., ID length growth with n).
- O(n): Linear (e.g., summing n integers).
- O(n log n): Quasilinear (e.g., sorting strings).
- O(n²): Quadratic (e.g., naive repeated string concatenation).
- O(2ⁿ), O(n!): Exponential/factorial (e.g., listing all permutations).
Why isn’t the algorithm with the best asymptotic complexity always the best choice?
Asymptotics matter mainly at large scales. For typical small inputs, simpler “worse-case” methods can be faster due to lower constants and overhead. The chapter’s example: a naive O(n²) string search was chosen because typical VB inputs were short and the method was blazingly fast in practice.
How should I think about problem size and cost metrics when analyzing algorithms?
- Make the size metric explicit (e.g., for trees, “n” might mean height, not node count).
- Consider multiple resources (time, memory, other system resources).
- Distinguish best-, average-, and worst-case costs; each can matter differently.
What design choices were made in the immutable linked list, and why?
- Used record types for concise, read-only-by-default immutability.
- Represented the empty list as a valid object (both Value and Tail are null), avoiding null references for method calls.
- Added Push and IsEmpty for readability.
- Acknowledged this empty representation is error-prone and promised a better approach later.
What performance pitfalls exist in the initial linked list implementation?
- IsEmpty relied on record equality, making it O(1) but with a large constant; a direct Tail == null check is cheaper.
- Compiler-generated value equality is recursive and O(k) in shared prefix length, risking stack overflows on long lists.
- ToString used naive concatenation, making it accidentally quadratic in time and memory; a StringBuilder version should be O(n).
How does the Reverse method for an immutable linked list work, and what is its complexity?
It walks the original list and pushes each value onto a new list, yielding a reversed copy while leaving the original unchanged. Complexity: O(n) time and O(n) extra space.
What topics and themes will the book explore beyond the basics?
- Twists on stacks, queues, and trees (e.g., persistence, memoization, elegant reordering, surprising reversal tricks).
- Backtracking for graph coloring and pretty printing; unification and anti-unification of trees.
- Practical tools for probability and Bayesian inference.
- Occasional theoretical interludes (e.g., category-theoretic patterns).
- Implemented in C#, but broadly applicable to languages like C++, Java, and Python.
Where does the word “algorithm” come from?
From the name of the 9th-century Persian mathematician Al-Khwarizmi, whose work also gave us the word “algebra.”
pro $24.99 per month
access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
Fabulous Adventures in Data Structures and Algorithms ebook for free
