book

Fabulous Adventures in Data Structures and Algorithms

Name: Fabulous Adventures in Data Structures and Algorithms
Author: Eric Lippert
ISBN: 9781633435032

by Eric Lippert

September 2026

Intermediate

368 pages

10h 37m

English

Manning Publications

Read now

Unlock full access

Fabulous Adventures in Data Structures and Algorithms
copyright
contents
foreword
preface
acknowledgments
about this book
about the author
about the cover illustration
1 Starting a fabulous adventure
1.1 Defining data structures, algorithms, and complexity1.2 An immutable linked list1.2.1 Performance so far1.2.2 Reversing an immutable linked list1.3 The challenges ahead

Part 1 Extending the basics
2 Immutable stacks and queues
2.1 Why immutability?2.1.1 Correctness2.1.2 Historical preservation2.1.3 Security2.1.4 Safer multithreading2.1.5 Memoization for time performance2.1.6 Persistence for space performance2.1.7 The functional programming attitude2.2 An immutable stack2.3 A covariant immutable stack2.4 A queue, a queue, an immutable queue2.5 Mutable wrappers2.6 Undo and redo2.6.1 Create an army of clones2.6.2 Use a different data structure and the command pattern2.6.3 Undo and redo with mutable-over-immutable data structures2.7 The Hughes list: Build it cheap, pay for it later2.7.1 Reverse redux2.7.2 Currying and partial application2.7.3 Implementing the Hughes list2.7.4 Complexity of the Hughes list2.7.5 Where is the data in this data structure?2.7.6 A couple more performance considerations2.7.7 Reverse a linked list
3 An immutable deque
3.1 An immutable deque abstract data type3.2 A bad naïve implementation3.3 A finger tree3.3.1 The mini-deque3.3.2 A new definition of a deque3.4 Visualizing the data structure3.5 Amortized performance of the deque3.6 Are we abusing the type system?3.7 Concatenation of deques3.8 Performance after adding concatenation3.9 Why is this tree called a finger tree?
4 Memoizing immutable quadtrees to make a better Life
4.1 The rules of Life4.2 A typical first attempt4.2.1 Performance of the naïve implementation4.2.2 Same algorithm, better constant factor4.2.3 Improving the algorithm with change tracking4.3 An immutable quadtree4.3.1 The IQuad interface4.3.2 Implementing the 0-quad leaf cells4.3.3 A strategy for compressing space4.3.4 A general-purpose memoizer4.3.5 A memoized quadtree implementation4.3.6 Indexing an immutable quadtree like an array4.3.7 A few more helpful extension methods4.4 The HashLife algorithm4.4.1 The base case: Stepping a 2-quad produces a 1-quad4.4.2 A first attempt at a recursive algorithm4.4.3 The grid always shrinks4.4.4 Is this algorithm inefficient?4.4.5 Take bigger steps forward4.4.6 Putting it all together
5 What’s up with you, Directed Acyclic Word Graph?
5.1 Two problems, two weak solutions5.1.1 Hash sets are a nonsolution5.1.2 Sorted lists are… fine?5.2 The prefix tree5.2.1 Nodes and edges5.2.2 The trie-building algorithm5.2.3 Using a trie as a word list5.2.4 How much memory are we saving with a trie?5.3 Tries are not-so-secretly finite state automata5.4 Building a DAWG5.4.1 What problems must we solve to build a DAWG?5.4.2 Equivalence of nodes5.4.3 The DAWG-building algorithm5.4.4 How much expense does optimizing the graph as you go add?5.5 DAWG vs. trie for ENABLE
6 Combinatorial algorithms
6.1 The Cartesian product6.1.1 The Cartesian product of a few sets or sequences6.1.2 The Cartesian product of arbitrarily many sequences6.1.3 The connection to the integers6.2 Permutations6.2.1 Lexicographic permutations with repetitions6.2.2 The factorial base representation of permutation numbers6.2.3 The Fisher–Yates shuffling algorithm6.2.4 A recursive change-ringing algorithm6.2.5 Even’s change-ringing algorithm6.3 Combinations6.3.1 Lexicographic combinations with a twist6.3.2 Counting combinations6.3.3 The combinatorial base representation of combinations
7 First abstract nonsense interlude: Category theory
7.1 Category theory is generalized abstract nonsense7.2 Covariant endofunctors in the category of types7.3 Contravariant endofunctors in the category of types
Part 2 Searching, solving, inferring
8 Coloring graphs with backtracking search
8.1 Coloring South America8.2 An immutable multidictionary8.3 An immutable undirected graph8.4 Coloring simple graphs8.5 Solving Sudokus with backtracking search8.5.1 Graph coloring is NP-complete8.5.2 Implementing a general backtracker8.5.3 How could we improve?8.5.4 Backtracking and the Cartesian product8.6 Scheduling problems are graph-coloring problems
9 Greedy iterative pretty printing
9.1 The pretty-printing problem9.2 Greedy algorithms and making change9.3 A greedy pretty-printing algorithm9.3.1 The doc data structure9.3.2 Visualizing a doc: How deep does it get?9.3.3 Phase 2: Implementing Fits() without recursion9.3.4 Phase 2 continued: Implementing Pretty() without recursion9.4 Phase 1: Transforming parse trees with the visitor pattern9.4.1 Implementing the visitor pattern9.4.2 From parse tree to doc
10 Unification and anti-unification
10.1 Unifying binary terms10.1.1 Unifying binary terms, first attempt10.1.2 Unifying binary terms, this time with an occurs check10.2 The performance of binary term unification10.3 Type inference and logic programming10.4 Anti-unifying binary terms10.5 The first-order binary-term anti-unification algorithm10.6 Clone detection and fix deduction
11 Second abstract nonsense interlude: Monads
11.1 What’s the value for OO programmers?11.2 How hard can it be to divide by 2?11.3 Generalizing to arbitrary functions with Map and Bind11.4 The sequence monad is an additive monad
Part 3 Probabilities
12 A better abstraction for randomness
12.1 What are probabilities?12.2 What are discrete probability distributions?12.3 Generating uniform samples with Random12.4 IDistribution<T> and IDiscreteDistribution<T>12.5 Flipping an unfair coin with Bernoulli12.6 Improving the ecosystem with extension methods12.7 Representing unfair die rolls by adding a projection12.8 Categorical algorithm 1: Make a big list12.9 Categorical algorithm 2: Climb a ladder12.10 Categorical algorithm 3: Rejecting rejection sampling12.11 Categorical algorithm 4: The alias algorithm12.12 Filtering out a category
13 Conditional probability with Bayes’ theorem
13.1 Bayes’ theorem13.2 Likelihood functions and joint distributions13.3 Updating priors by reasoning from effects to causes13.4 Some applications of Bayesian reasoning13.5 Unconditional likelihood functions are independent
14 Third abstract nonsense interlude: The probability monad
14.1 The requirements for a monad14.2 Probability distributions as additive monads14.3 A critique
15 Sampling continuous distributions
15.1 What is a continuous probability distribution?15.2 Sampling the continuous uniform distribution15.3 Sampling the normal distribution15.4 The inverse transform method15.5 Rejection sampling15.5.1 Clamping with rejection sampling15.5.2 Problems with rejection sampling
16 Markov processes and the Metropolis algorithm
16.1 What is a Markov process?16.2 Markov texts16.3 Computing posteriors of continuous distributions16.4 The Metropolis algorithm16.5 Sampling posteriors with Metropolis
appendix A Notes on C#
A.1 Value and reference typesA.2 Generic types are fully instantiated at runtimeA.3 Nullable typesA.4 SugarsA.5 Extension methodsA.6 Sequences, iterators, and lambdas
appendix B Further reading

Content preview from Fabulous Adventures in Data Structures and Algorithms

12 A better abstraction for randomness

In my university days, I paid little attention to my only required statistics class. I found the jargon confusing and foresaw little use for statistical reasoning in my future career. I was half right: the jargon is confusing. But because I ended up implementing programming tools for data scientists, my weak knowledge of probabilistic reasoning needed fixing in a hurry.

In this chapter, we’ll start with a refresher on statistics jargon. ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Publisher Resources

ISBN: 9781633435032Publisher Support Other Publisher Website Purchase Link

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Fabulous Adventures in Data Structures and Algorithms

by Eric Lippert

12 A better abstraction for randomness

In this chapter

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.