15 Directed Acyclic Graphs
15.1 Sharing and Equality
15.1.1 Re-Examining Equality
15.1.2 The Cost of Evaluating References
15.1.3 Notations for Equality
15.1.4 On the Internet, Nobody Knows You’re a DAG
15.1.5 It’s Always Been a DAG
15.1.6 From Acyclicity to Cycles
15.2 The Size of a DAG
15.2.1 Stage 1
15.2.2 Stage 2
15.2.3 Stage 3
15.2.4 Stage 4
15.2.5 Stage 5
15.2.6 What We’ve Learned
15.2.7 More on Value Printing: An Aside from Racket
16 Graphs
16.1 Introducing Graphs
16.1.1 Understanding Graphs
16.1.2 Representations
16.1.2.1 Links by Name
16.1.2.2 Links by Indices
16.1.2.3 A List of Edges
16.1.2.4 Abstracting Representations
16.1.3 Measuring Complexity for Graphs
16.2 Basic Graph Traversals
16.2.1 Reachability
16.2.1.1 Simple Recursion
16.2.1.2 Cleaning up the Loop
16.2.1.3 Traversal with Memory
16.2.1.4 A Better Interface
16.2.2 Depth- and Breadth-First Traversals
16.3 Graphs With Weighted Edges
16.4 Shortest (or Lightest) Paths
16.5 Moravian Spanning Trees
16.5.1 The Problem
16.5.2 A Greedy Solution
16.5.3 Another Greedy Solution
16.5.4 A Third Solution
16.5.5 Checking Component Connectedness
17 Several Variations on Sets
17.1 Representing Sets as Lists
17.1.1 Representation Choices
17.1.2 Time Complexity
17.1.3 Choosing Between Representations
17.1.4 Other Operations
17.2 Making Sets Grow on Trees
17.2.1 Using Binary Trees
17.2.2 Checking the Complexity
17.2.3 A Fine Balance: Tree Surgery
17.2.3.1 Left-Left Case
17.2.3.2 Left-Right Case
17.2.3.3 Any Other Cases?
17.3 Union-Find
17.3.1 Implementing with State
17.3.2 Optimizations
17.3.3 Analysis
17.4 Hashes, Sets, and Key-Values
17.4.1 A Hash Function for Strings
17.4.2 Sets from Hashing
17.4.3 Arrays
17.4.4 Sets from Hashing and Arrays
17.4.5 Collisions
17.4.6 Resolving Collisions
17.4.7 Complexity
17.4.8 Bloom Filters
17.4.9 Generalizing from Sets to Key-Values
17.5 Equality, Ordering, and Hashing
17.5.1 Converting Values to Ordered Values
17.5.2 Hashing in Practice
17.5.3 Equality and Ordering
17.6 Sets as a Case Study
17.6.1 Nature of the Data
17.6.2 Nature of the Operations
17.6.3 Nature of the Guarantee