8.14

VI Data Structures with Analysis🔗

    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