I Introduction

      1 Overview

        1.1 Our Philosophy

        1.2 Predictability as a Theme

        1.3 The Structure of This Book

        1.4 The Language of This Book

      2 Acknowledgments

    II Foundations

      3 Getting Started

        3.1 Motivating Example: Flags

        3.2 Numbers

        3.3 Expressions

        3.4 Terminology

        3.5 Strings

        3.6 Images

          3.6.1 Combining Images

          3.6.2 Making a Flag

        3.7 Stepping Back: Types, Errors, and Documentation

          3.7.1 Types and Contracts

          3.7.2 Format and Notation Errors

          3.7.3 Finding Other Functions: Documentation

      4 Naming Values

        4.1 The Definitions Window

        4.2 Naming Values

          4.2.1 Names Versus Strings

          4.2.2 Expressions versus Statements

        4.3 The Program Directory

          4.3.1 Understanding the Run Button

        4.4 Using Names to Streamline Building Images

      5 From Repeated Expressions to Functions

        5.1 Example: Similar Flags

        5.2 Defining Functions

          5.2.1 How Functions Evaluate

          5.2.2 Type Annotations

          5.2.3 Documentation

        5.3 Functions Practice: Moon Weight

        5.4 Documenting Functions with Examples

        5.5 Functions Practice: Cost of pens

        5.6 Recap: Defining Functions

      6 Conditionals and Booleans

        6.1 Motivating Example: Shipping Costs

        6.2 Conditionals: Computations with Decisions

        6.3 Booleans

          6.3.1 Other Boolean Operations

          6.3.2 Combining Booleans

        6.4 Asking Multiple Questions

        6.5 Evaluating by Reducing Expressions

        6.6 Composing Functions

        6.7 Nested Conditionals

        6.8 Recap: Booleans and Conditionals

      7 Introduction to Tabular Data

        7.1 Creating Tabular Data

        7.2 Extracting Rows and Cell Values

        7.3 Functions over Rows

        7.4 Processing Rows

          7.4.1 Finding Rows

          7.4.2 Ordering Rows

          7.4.3 Adding New Columns

          7.4.4 Calculating New Column Values

        7.5 Examples for Table-Producing Functions

      8 Processing Tables

        8.1 Cleaning Data Tables

          8.1.1 Loading Data Tables

          8.1.2 Dealing with Missing Entries

          8.1.3 Normalizing Data

          8.1.4 Normalization, Systematically

            8.1.4.1 Using Programs to Detect Data Errors

        8.2 Task Plans

        8.3 Preparing Data Tables

          8.3.1 Creating bins

        8.4 Managing and Naming Data Tables

        8.5 Visualizations and Plots

        8.6 Summary: Managing a Data Analysis

      9 From Tables to Lists

        9.1 Basic Statistical Questions

        9.2 Extracting a Column from a Table

        9.3 Understanding Lists

          9.3.1 Lists as Anonymous Data

          9.3.2 Creating Literal Lists

        9.4 Operating on Lists

          9.4.1 Built-In Operations on Lists of Numbers

          9.4.2 Built-In Operations on Lists in General

          9.4.3 An Aside on Naming Conventions

          9.4.4 Getting Elements By Position

          9.4.5 Transforming Lists

          9.4.6 Recap: Summary of List Operations

        9.5 Lambda: Anonymous Functions

        9.6 Combining Lists and Tables

      10 Processing Lists

        10.1 Making Lists and Taking Them Apart

        10.2 Some Example Exercises

        10.3 Structural Problems with Scalar Answers

          10.3.1 my-len: Examples

          10.3.2 my-sum: Examples

          10.3.3 From Examples to Code

        10.4 Structural Problems that Transform Lists

          10.4.1 my-doubles: Examples and Code

          10.4.2 my-str-len: Examples and Code

        10.5 Structural Problems that Select from Lists

          10.5.1 my-pos-nums: Examples and Code

          10.5.2 my-alternating: Examples and Code

        10.6 Structural Problems with Sub-Domains

          10.6.1 my-max: Examples

          10.6.2 my-max: From Examples to Code

        10.7 More Structural Problems with Scalar Answers

          10.7.1 my-avg: Examples

        10.8 Structural Problems with Accumulators

          10.8.1 my-running-sum: First Attempt

          10.8.2 my-running-sum: Examples and Code

          10.8.3 my-alternating: Examples and Code

        10.9 Dealing with Multiple Answers

          10.9.1 uniq: Problem Setup

          10.9.2 uniq: Examples

          10.9.3 uniq: Code

          10.9.4 uniq: Reducing Computation

          10.9.5 uniq: Example and Code Variations

          10.9.6 uniq: Why Produce a List?

        10.10 Monomorphic Lists and Polymorphic Types

      11 Introduction to Structured Data

        11.1 Understanding the Kinds of Compound Data

          11.1.1 A First Peek at Structured Data

          11.1.2 A First Peek at Conditional Data

        11.2 Defining and Creating Structured and Conditional Data

          11.2.1 Defining and Creating Structured Data

          11.2.2 Annotations for Structured Data

          11.2.3 Defining and Creating Conditional Data

        11.3 Programming with Structured and Conditional Data

          11.3.1 Extracting Fields from Structured Data

          11.3.2 Telling Apart Variants of Conditional Data

          11.3.3 Processing Fields of Variants

      12 Collections of Structured Data

        12.1 Lists as Collective Data

        12.2 Sets as Collective Data

          12.2.1 Picking Elements from Sets

          12.2.2 Computing with Sets

        12.3 Combining Structured and Collective Data

      13 Recursive Data

        13.1 Functions to Process Recursive Data

        13.2 A Template for Processing Recursive Data

      14 Trees

        14.1 Data Design Problem – Ancestry Data

          14.1.1 Computing Parents from an Ancestry Table

          14.1.2 Computing Grandparents from an Ancestry Table

          14.1.3 Creating a Datatype for Ancestor Trees

        14.2 Programs to Process Ancestor Trees

        14.3 Summarizing How to Approach Tree Problems

        14.4 Study Questions

      15 Interactive Games as Reactive Systems

        15.1 About Reactive Animations

        15.2 Preliminaries

        15.3 Version: Airplane Moving Across the Screen

          15.3.1 Updating the World State

          15.3.2 Displaying the World State

          15.3.3 Observing Time (and Combining the Pieces)

        15.4 Version: Wrapping Around

        15.5 Version: Descending

          15.5.1 Moving the Airplane

          15.5.2 Drawing the Scene

          15.5.3 Finishing Touches

        15.6 Version: Responding to Keystrokes

        15.7 Version: Landing

        15.8 Version: A Fixed Balloon

        15.9 Version: Keep Your Eye on the Tank

        15.10 Version: The Balloon Moves, Too

        15.11 Version: One, Two, ..., Ninety-Nine Luftballons!

      16 Examples, Testing, and Program Checking

        16.1 From Examples to Tests

        16.2 More Refined Comparisons

        16.3 When Tests Fail

        16.4 Oracles for Testing

    III Algorithms

      17 Functions as Data

        17.1 A Little Calculus

        17.2 A Helpful Shorthand for Anonymous Functions

        17.3 Streams From Functions

        17.4 Combining Forces: Streams of Derivatives

      18 Predicting Growth

        18.1 A Little (True) Story

        18.2 The Analytical Idea

        18.3 A Cost Model for Pyret Running Time

        18.4 The Size of the Input

        18.5 The Tabular Method for Singly-Structurally-Recursive Functions

        18.6 Creating Recurrences

        18.7 A Notation for Functions

        18.8 Comparing Functions

        18.9 Combining Big-Oh Without Woe

        18.10 Solving Recurrences

      19 Sets Appeal

        19.1 Representing Sets by Lists

          19.1.1 Representation Choices

          19.1.2 Time Complexity

          19.1.3 Choosing Between Representations

          19.1.4 Other Operations

        19.2 Making Sets Grow on Trees

          19.2.1 Converting Values to Ordered Values

          19.2.2 Using Binary Trees

          19.2.3 A Fine Balance: Tree Surgery

            19.2.3.1 Left-Left Case

            19.2.3.2 Left-Right Case

            19.2.3.3 Any Other Cases?

      20 Halloween Analysis

        20.1 A First Example

        20.2 The New Form of Analysis

        20.3 An Example: Queues from Lists

          20.3.1 List Representations

          20.3.2 A First Analysis

          20.3.3 More Liberal Sequences of Operations

          20.3.4 A Second Analysis

          20.3.5 Amortization Versus Individual Operations

        20.4 Reading More

      21 Sharing and Equality

        21.1 Re-Examining Equality

        21.2 The Cost of Evaluating References

        21.3 On the Internet, Nobody Knows You’re a DAG

        21.4 From Acyclicity to Cycles

      22 Graphs

        22.1 Understanding Graphs

        22.2 Representations

          22.2.1 Links by Name

          22.2.2 Links by Indices

          22.2.3 A List of Edges

          22.2.4 Abstracting Representations

        22.3 Measuring Complexity for Graphs

        22.4 Reachability

          22.4.1 Simple Recursion

          22.4.2 Cleaning up the Loop

          22.4.3 Traversal with Memory

          22.4.4 A Better Interface

        22.5 Depth- and Breadth-First Traversals

        22.6 Graphs With Weighted Edges

        22.7 Shortest (or Lightest) Paths

        22.8 Moravian Spanning Trees

          22.8.1 The Problem

          22.8.2 A Greedy Solution

          22.8.3 Another Greedy Solution

          22.8.4 A Third Solution

          22.8.5 Checking Component Connectedness

    IV Programming with State

      23 From Pyret to Python

        23.1 Expessions, Functions, and Types

        23.2 Returning Values from Functions

        23.3 Examples and Test Cases

        23.4 An Aside on Numbers

        23.5 Conditionals

        23.6 Creating and Processing Lists

          23.6.1 Filters, Maps, and Friends

        23.7 Data with Components

          23.7.1 Accessing Fields within Dataclasses

        23.8 Traversing Lists

          23.8.1 Introducing For Loops

            23.8.1.1 An Aside on Order of Processing List Elements

          23.8.2 Using For Loops in Functions that Produce Lists

          23.8.3 Summary: The List-Processing Template for Python

      24 Modifying Variables

        24.1 Modifying Variables in Memory

        24.2 Modifying Variables Associated with Lists

        24.3 Writing Functions that Modify Variables

          24.3.1 The global annotation

        24.4 Testing Functions that Modify global Variables

          24.4.1 The Internal Structure of a Test Function

          24.4.2 Takeaways on Testing Modifications

      25 Modifying Structured Data

        25.1 Modifying Fields of Structured Data

        25.2 Modifications to Shared Data

        25.3 Understanding Memory

        25.4 Modifications to Structured Data, Revisited

        25.5 Basic Data in Memory

        25.6 Variables and Equality

        25.7 Takeaways on Modifying Variables

      26 Revisiting Lists and Variables

        26.1 Sharing List Updates

          26.1.1 Operations that Mutate Lists

        26.2 Lists in Memory

        26.3 Practice: Data for Shared Bank Accounts

        26.4 Circular References

          26.4.1 Testing Circular Data

          26.4.2 Revisiting Variables: A Function to Create Accounts for New Customers

        26.5 The Many Roles of Variables

        26.6 Managing All Accounts

      27 Hashtables and Dictionaries

        27.1 Searching by Criteria Other than Keys

        27.2 Dictionaries with More Complex Values

        27.3 Using Structured Data as Keys

    V Advanced Topics

      28 Algorithms That Exploit State

        28.1 Disjoint Sets Redux

          28.1.1 Optimizations

          28.1.2 Analysis

        28.2 Set Membership by Hashing Redux

          28.2.1 Improving Access Time

          28.2.2 Better Hashing

          28.2.3 Bloom Filters

        28.3 Avoiding Recomputation by Remembering Answers

          28.3.1 An Interesting Numeric Sequence

            28.3.1.1 Using State to Remember Past Answers

            28.3.1.2 From a Tree of Computation to a DAG

            28.3.1.3 The Complexity of Numbers

            28.3.1.4 Abstracting Memoization

          28.3.2 Edit-Distance for Spelling Correction

          28.3.3 Nature as a Fat-Fingered Typist

          28.3.4 Dynamic Programming

            28.3.4.1 Catalan Numbers with Dynamic Programming

            28.3.4.2 Levenshtein Distance and Dynamic Programming

          28.3.5 Contrasting Memoization and Dynamic Programming

    VI Appendices

      29 Pyret for Racketeers and Schemers

        29.1 Numbers, Strings, and Booleans

        29.2 Infix Expressions

        29.3 Function Definition and Application

        29.4 Tests

        29.5 Variable Names

        29.6 Data Definitions

        29.7 Conditionals

        29.8 Lists

        29.9 First-Class Functions

        29.10 Annotations

        29.11 What Else?

      30 Glossary