1 Starting a fabulous adventure
This opening chapter sets the tone for a tour of algorithms and data structures that are memorable because they solve real problems in unexpected ways, travel well across domains, and encourage code that expresses meaning rather than mechanism. The author highlights how counterintuitive ideas—like using immutable structures for undo/redo—can yield robustness and clarity, how familiar techniques—such as backtracking—recur from trees to map coloring to pretty printing, and how reframing a problem—like HashLife’s quadtree view of cellular automata—can transform performance. Alongside moments that feel like “magic tricks” (for example, structures that seem to hold no data) and deep connections to theory, the goal is to expand a practitioner’s toolbox while rekindling the fun and curiosity that make programming satisfying.
The chapter then grounds that excitement with precise definitions and a practical view of complexity. A data structure is an organized way to store information; an algorithm is a finite process to solve a problem, potentially non-deterministic and not necessarily run by a computer. Complexity relates problem size to resource cost, presented through familiar growth classes: constant, logarithmic, linear, quasilinear, quadratic, and explosive exponential/factorial, each with concrete examples. It emphasizes choosing the right notion of “size,” considering memory as well as time, and distinguishing best-, average-, and worst-case behavior. Crucially, it cautions that superior asymptotics are not always superior in practice; for typical small inputs, a simple approach can beat a theoretically better one.
A brief, hands-on exercise builds an immutable linked list in C#, using a concise record-based definition and exploring the trade-offs that surface immediately. The design of an “empty” list, the subtle cost of equality and IsEmpty, the danger of recursive equality on long lists, and the classic “accidentally quadratic” ToString all illustrate how small choices affect performance and correctness. Reversing the list provides a clear, iterative O(n)-time and O(n)-space example that preserves immutability. The chapter closes by previewing the journey ahead: twists on familiar structures (stacks, queues, trees), persistence and memoization, elegant list-reordering techniques, surprising approaches to reversal, practical algorithms from developer tools (backtracking, unification/anti-unification), and a final leg building probabilistic tooling and Bayesian intuition, with occasional theoretical interludes—implemented in C# but accessible to developers in other mainstream languages.
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 topics does Chapter 1 cover?
- Exploring what makes some algorithms and data structures “fabulous”
- Defining data structures, algorithms, and complexity
- Implementing and reversing an immutable linked list
How does the book define a data structure and an algorithm?
- A data structure organizes information in a structured way (e.g., using arrays, classes, structs, records, interfaces).
- An algorithm is a finite sequence of steps that solves a problem; it can be nondeterministic, need not run on a computer, and can be conceptually simple even if it performs many steps.
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”.
What does algorithmic complexity mean in this chapter?
It’s the relationship between problem size and the cost to solve it, measured in resources like time or memory. The chapter uses Big-O notation to summarize how costs grow as input size increases.
What Big-O classes and examples are highlighted?
- O(1): First element of an array
- O(log n): Identifier length growth with n objects
- O(n): Summing n 32-bit integers
- O(n log n): Sorting n strings
- O(n²): Naïve string concatenation of n small strings (“accidentally quadratic”)
- O(2ⁿ), O(n!): Intractable growth (e.g., all orderings of n cards)
Why isn’t asymptotic performance the only consideration?
Real workloads matter. A Visual Basic string search used a naïve O(n²) worst-case method because typical inputs were short and the approach was faster in practice than more complex linear-time algorithms.
How is the immutable linked list represented, and what are the design trade-offs?
- It’s recursively defined: either empty, or a value with a tail list.
- The empty list is a real object (not null), represented as Value = null and Tail = null.
- Pros: safer OO design; concise immutability via record parameters.
- Cons: it’s still possible to create invalid states (e.g., non-empty with invalid Tail); improved empty-list design is deferred to the next chapter.
What performance pitfalls appear in the initial list implementation?
- Push/new is O(1); building n items is O(n) time and memory.
- IsEmpty using record equality is O(1) but comparatively expensive; Tail == null is cheaper.
- Record-generated value equality is O(k) in common prefix length and recursive, risking stack overflow on long lists.
- ToString with string concatenation is accidentally O(n²) in time and extra memory; use StringBuilder for O(n).
How do you reverse an immutable linked list here, and what’s the cost?
Iterate through the list, pushing each value onto a new list, leaving the original unchanged. The Reverse operation is O(n) in time and O(n) in extra memory.
What “fabulous” qualities and upcoming themes does the chapter set up?
- Solving real problems off the beaten path
- Counterintuitive wins (e.g., immutable structures aiding undo/redo)
- Cross-domain applicability (e.g., backtracking for maps, Sudoku, pretty printers)
- Expressing meaning over mechanisms; higher-level abstractions
- “Magic trick” data structures (e.g., Hughes list)
- Leveraging language features (e.g., C# generics vs C++ templates; finger trees)
- Reframing problems (e.g., HashLife with immutable quadtrees)
- Connections to theory (e.g., category-theoretic patterns)
- Having fun while building a practical toolbox (stacks, queues, trees, memoization, reordering, probability, Bayesian inference)
Fabulous Adventures in Data Structures and Algorithms ebook for free
