Preface
1 The Parts of the Book
2 Acknowledgments
Contents
Part I Basic Problem Solving and Program Design
1 The Science of Problem Solving
3 The Design Recipe
4 Computing the Area of a Triangle
4.1 Exercises
5 Doubling a List of Numbers
5.1 Step 1: Data Analysis and Design Idea
5.2 Step 2: Sample Expressions
5.3 Step 3: Differences Among Sample Expressions
5.4 Steps 4–5: Signature, Purpose Statement, and Function Header
5.5 Step 6: Tests
5.6 Step 7: Function Body
5.7 Step 8: Run Tests
5.8 Exercises
6 Code Refactoring
6.1 Exercises
7 Abstract Running Time
7.1 Exercises
8 What Have We Learned in This Chapter?
2 The N-Puzzle Problem
9 The world and the run Function
10 Useful Constants
11 The draw-world Handler
12 The game-over? Handler
13 The process-key Handler
13.1 The Design of vk?
13.2 The Design of process-vk
13.2.1 Computing the Position of the Empty Space
13.2.2 The Design of get-target-bpos
13.2.3 The Design of swap-empty
13.2.4 The Design of make-move
14 What Have We Learned in This Chapter?
3 Randomness
15 ISL+'s random Function
16 N-Puzzle Version 1
17 Generating Random Passwords
18 Distributed Fortune Teller Game
18.1 Design Recipe for Distributed Computing
18.2 The Components
18.3 Data Definitions
18.3.1 Player Data Definitions
18.3.2 Server Data Definitions
18.4 Communication Protocol
18.5 Marshaling and Unmarshaling Functions
18.6 The Player Component
18.6.1 The draw-world Handler
18.6.2 The process-key Handler
18.6.3 The process-message Handler
18.6.4 The finished? Handler
18.7 The Server Component
18.7.1 The add-new-iworld Handler
18.7.2 The rm-iworld Handler
18.7.3 The process-message Handler
19 What Have We Learned in This Chapter?
Part II Generative Recursion
4 Introduction to Generative Recursion
20 Generating a Nested Square Image
21 The Design Recipe for Generative Recursion
22 All Primes n
23 What Have We Learned in This Chapter?
5 Sorting
24 Insertion Sorting
25 Quick Sorting
25.1 Problem Analysis
25.2 Sample Expressions and Differences
25.3 Signature, Statements, and Function Header
25.4 Tests
25.5 Function Body
25.6 Termination Argument
25.7 Performance
25.8 Complexity Analysis
26 Merge Sorting
26.1 Problem Analysis
26.2 The merge-sorting Function
26.2.1 Problem Analysis
26.2.2 Sample Expressions and Differences
26.2.3 Signature, Purpose, and Function Header
26.2.4 Tests
26.2.5 Function Body
26.3 The merge-sort-helper Function
26.3.1 Problem Analysis
26.3.2 Sample Expressions and Differences
26.3.3 Signature, Statements, and Function Header
26.3.4 Tests
26.3.5 Function Body
26.3.6 Termination Argument
26.4 The merge-neighs Function
26.4.1 Problem Analysis
26.4.2 Sample Expressions and Differences
26.4.3 Signature, Statements, and Function Header
26.4.4 Tests
26.4.5 Function Body
26.4.6 Termination Argument
26.5 The merge Function
26.5.1 Problem Analysis
26.5.2 Sample Expressions and Differences
26.5.3 Signature, Statements, and Function Header
26.5.4 Tests
26.5.5 Function Body
26.6 Performance
26.7 Complexity Analysis
27 What Have We Learned in This Chapter?
6 Searching
28 Linear Searching
28.1 Problem Analysis
28.2 Sample Expressions and Differences
28.3 Signature, Purpose, and Function Header
28.4 Tests
28.5 Function Body
28.6 Performance and Complexity
29 Binary Search
29.1 The binary-search Function
29.1.1 Problem Analysis
29.1.2 Sample Expressions and Differences
29.1.3 Signature, Statements, and Function Header
29.1.4 Tests
29.1.5 Function Body
29.2 The bin-search Function
29.2.1 Problem Analysis
29.2.2 Sample Expressions and Differences
29.2.3 Signature, Statements, and Function Header
29.2.4 Tests
29.2.5 Function Body
29.3 Termination Argument
29.4 Performance and Complexity
30 Trees
31 Depth-First Search
31.1 Problem Analysis
31.2 Sample Expressions and Differences
31.3 Signature, Purpose, and Function Header
31.4 Tests
31.5 The Function Body
31.6 The node-dfs-contains? Function
31.6.1 Problem Analysis
31.6.2 Sample Expressions
31.7 Signature, Purpose, and Function Definition
31.7.1 Tests
31.8 Performance and Complexity
32 Breadth-First Search
32.1 Problem Analysis for ton-bfs-contains?
32.1.1 Queues
32.1.2 The Implementation of qempty? and qfirst
32.1.3 The Implementation of enqueue and dequeue
32.2 Sample Expressions and Differences for ton-bfs-contains?
32.3 Tests for ton-bfs-contains?
32.4 Function Definition for ton-bfs-contains?
32.5 Problem Analysis for bfs-helper
32.6 Sample Expressions and Differences for bfs-helper
32.7 Tests for bfs-helper
32.8 Signature, Statements, and Function Definition for bfs-helper
32.9 Performance and Complexity
33 What Have We Learned in This Chapter?
7 N-Puzzle Version 2
34 Design and Implementation of make-move
34.1 Problem Analysis
34.2 Sample Expressions and Differences
34.3 Signature, Purpose, and Function Header
34.4 Tests
34.5 Function Body
35 Design and Implementation of find-solution
35.1 Problem Analysis
35.2 Sample Expressions and Differences
35.3 Signature, Statements, and Function Header
35.4 Tests
35.5 Function Body
35.6 Termination Argument
36 New Tests for process-key
37 A Bug: Infinite Recursion
38 What Have We Learned in This Chapter?
8 N-Puzzle Version 3
39 The Design of make-move
39.1 Problem Analysis
39.2 Sample Expressions and Differences
39.3 Signature, Purpose, and Function Header
39.4 Tests
39.5 Function Body
40 The Design of find-solution-bfs
40.1 Problem Analysis
40.2 Sample Expressions and Differences
40.3 Signature, Statements, and Function Header
40.4 Tests
40.5 Function Body
40.6 Termination Argument
41 Performance
42 What Have We Learned in This Chapter?
Part III Accumulative Recursion
9 Accumulators
43 Running Totals
43.1 Problem Analysis for lon-running-totals
43.2 Sample Expressions and Differences for lon-running-totals
43.3 Signature, Function Definition, and Tests for lon-running-totals
43.4 Problem Analysis for lon-running-totals- helper
43.5 Sample Expressions and Differences for lon-running-totals-helper
43.6 Signature, Function Definition, and Tests for lon-running-totals-helper
43.7 The lon-sum Function
44 Running Totals Using an Accumulator
44.1 Problem Analysis
44.2 Sample Expressions and Differences for lon-running-totals-v2
44.3 Function Definition for lon-running-totals-v2
44.4 Tests for lon-running-totals-v2
44.5 Problem Analysis for lon-running-totals-helper-v2
44.6 Sample Expressions and Differences for lon-running-totals-helper-v2
44.7 Signature, Statements, and Function Header for lon-running-totals-helper-v2
44.8 Tests for lon-running-totals-helper-v2
44.9 Function Body for lon-running-totals- helper-v2
45 Performance and Complexity Analysis
46 Finding a Path in a Directed Graph
46.1 Data Analysis
46.2 Design and Implementation of find-path
46.2.1 Problem Analysis
46.2.2 Sample Expressions and Differences
46.2.3 Signature, Purpose, and Function Definition
46.2.4 Tests
46.3 Design and Implementation of find-path-acc
46.3.1 Problem Analysis
46.3.2 Sample Expressions and Differences
46.3.3 Signature, Purpose, Invariant, and Function Header
46.3.4 Tests
46.3.5 Function Body
46.4 Design and Implementation of find-path-from-neighbors
46.4.1 Problem Analysis
46.4.2 Sample Expressions and Differences
46.4.3 Signature, Purpose, Invariant, and Function Header
46.4.4 Tests
46.4.5 Function Body
46.5 Termination Argument
47 Revisiting Insertion Sorting
47.1 The Redesign of insert
47.1.1 Problem Analysis
47.1.2 Sample Expressions and Differences
47.1.3 Signature, Statements, and Function Header
47.1.4 Tests
47.1.5 Function Body
47.2 The Redesign of insertion-sorting
47.2.1 Problem Analysis
47.2.2 Sample Expressions and Differences
47.2.3 Signature, Purpose, Invariant, and Function Header
47.2.4 Tests
47.2.5 Function Body
47.3 Performance and Complexity Analysis
48 What Have We Learned in This Chapter?
10 N-Puzzle Versions 4 and 5
49 N-Puzzle Version 4
49.1 The Design and Implementation of find-solution
49.1.1 Problem Analysis
49.1.2 Sample Expressions and Differences
49.1.3 Signature, Statements, and Function Header
49.1.4 Tests
49.1.5 Function Body
49.2 The find-solution-from-any-succ Design and Implementation
49.2.1 Problem Analysis
49.2.2 Sample Expressions and Differences
49.2.3 Signature, Statements, and Function Header
49.2.4 Tests
49.2.5 Function Body
49.3 Termination Argument
50 N-Puzzle Version 5
50.1 Problem Analysis
50.2 Sample Expressions and Differences
50.3 Signature, Statements, and Function Header
50.4 Tests
50.5 Function Body
50.6 Termination Argument
51 Complexity and Performance
52 What Have We Learned in This Chapter?
11 Iteration
53 List-Folding Operations from the Left
53.1 Summing a List of Numbers
53.1.1 Problem Analysis
53.1.2 Refactoring sum-lon
53.1.3 sum-lon-accum's Sample Expressions and Differences
53.1.4 Signature, Statements, and Function Header for sum-lon-accum
53.1.5 Tests for sum-lon-accum
53.1.6 sum-lon-accum's Function Body
53.1.7 Performance
53.2 Reversing a List
53.2.1 Problem Analysis
53.2.2 Sample Expressions and Differences for rev-lox-accum
53.2.3 rev-lox-accum's Signature, Statements, and Function Header
53.2.4 Tests for rev-lox-accum
53.2.5 Function Body for rev-lox-accum
53.2.6 Performance
54 List-Folding Operations from the Right
54.1 Computing String Lengths from a List of Strings
54.1.1 Problem Analysis
54.1.2 Sample Expressions and Differences for lengths-lostr-accum
54.1.3 Signature, Statements, and Function Header for lengths-lostr-accum
54.1.4 Tests for lengths-lostr-accum
54.1.5 Function Body for lengths-lostr-accum
54.1.6 Performance
54.2 Summing a List of Numbers Revisited
55 Functional Abstraction
56 Abstraction over Left to Right Accumulating Folding Functions
56.1 The Abstraction
56.2 Performance
57 Abstraction Over Right to Left Accumulating Folding Functions
58 What Have We Learned in This Chapter?
12 N-Puzzle Version 6
59 The Manhattan Distance Heuristic
60 Problem Analysis
61 Sample Expressions and Differences for find-solution-a*
62 Signature, Statements, and Function Header
63 Tests for find-solution-a*
64 Function Body for find-solution-a*
65 Termination Argument
66 Performance
67 What Have We Learned in This Chapter?
13 Continuation-Passing Style
68 Accumulating Control
69 The CPS Design Recipe
70 Computing Fibonacci Numbers
70.1 Transforming to CPS
70.2 Performance
70.3 Going Beyond the Design Recipe
71 Revisiting List Reversal
72 What Have We Learned in This Chapter?
Part IV Mutation
14 Sharing Values
73 set! and begin Expressions
74 Design Recipe for Mutators
75 A Bank Account
75.1 Problem and Data Analysis
75.2 State Variable Definitions
75.3 State Variable Initializers
75.4 The Mutator for Deposits
75.4.1 Problem Analysis
75.4.2 Signature, Statements, and Function Header
75.4.3 Tests
75.4.4 Function Body
75.5 The Mutator for Withdrawals
75.5.1 Problem Analysis
75.5.2 Signature, Statements, and Function Header
75.5.3 Tests
75.5.4 Function Body
75.6 The Observer for Getting the Balance
76 Abstraction Over State Variables
76.1 Bank Account State Variables and Interface
76.2 Bank Account Class Template
76.3 Bank Account Message-Passing Function Design
76.4 Bank Account Auxiliary Function Design
76.5 Bank Account Wrapper Functions and Tests
77 A Design Recipe for Interfaces
78 Mutation and Structures
79 The Concept of Equality
80 What Have We Learned in This Chapter?
15 Mutation Sequencing
81 Hoare Logic
81.1 Using Hoare Triples
81.1.1 Developing fact-state!
81.2 Imperative Code Debugging
82 New Syntax: while Loops
82.1 Syntax and Semantics
82.2 Transformation from an Imperative Recursive Function to a while Loop
83 A Design Recipe for while loops
84 Determining if an Interval Contains a Prime
84.1 Problem Analysis
84.2 Signature, Statements, and Function Header
84.3 Tests
84.4 Loop Invariant
84.5 Function Body
84.6 The begin Expression
84.7 Post-Loop Code
84.8 Auxiliary Functions
84.9 Termination Argument
84.10 Run Tests
85 Finding the Maximum in a List of Numbers
85.1 Problem Analysis
85.2 Signature, Statements, and Function Header
85.3 Tests
85.4 Loop Invariant
85.5 Function Body
85.6 The begin Expression
85.7 Post-Loop Code
85.8 Termination Argument
85.9 Run Tests
86 What Have We Learned in This Chapter?
16 Vectors
87 Vector Basics
88 Vector Processing Using Structural Recursion
88.1 The Dot Product of Two Vectors of Numbers
88.1.1 Problem Analysis
88.1.2 Problem Analysis for sum-products
88.1.3 Signature, Statements, and Function Header for sum-products
88.1.4 Function Body for sum-products
88.2 Merging Two Sorted Vectors
88.2.1 Problem Analysis
88.2.2 Signature, Statements, and Function Header
88.2.3 Tests
88.2.4 Loop Invariant
88.2.5 Function's Local Declarations
88.2.6 The local-expression's Body
88.2.7 Post-Loop Code
88.2.8 Auxiliary Functions, Termination Argument, and Testing
89 Vector Processing Using Generative Recursion: Revisiting the Sieve of Eratosthenes
89.1 Problem Analysis
89.2 Signature, Statements, and Function Header
89.3 Tests
89.4 Loop Invariant
89.5 Function's Local Definitions
89.6 The local-expression's Body
89.7 Post-Loop Code
89.8 Auxiliary Functions
89.8.1 The Design of mark-multiples!
89.8.2 The Design of extract-primes
89.9 Termination Argument and Running Tests
89.10 Complexity and Performance
90 What Have We Learned in This Chapter?
17 In-Place Operations
91 Reversing a Vector
91.1 Problem Analysis
91.2 The reverse-vector-in-place! Mutator
91.2.1 Problem Analysis
91.3 Signature and Statements
91.3.1 Tests
91.3.2 Function Body
91.4 The rev-vector! Mutator
91.4.1 Problem Analysis
91.4.2 Signature and Statements
91.4.3 Testing
91.5 Function Body
91.6 The swap! Mutator and Running Tests
91.7 Performance
92 In-Place Quick Sorting
92.1 The qs-in-place! Mutator
92.1.1 Problem Analysis
92.1.2 Signature, Statements, and Function Header
92.1.3 Tests
92.1.4 Function Body
92.2 The qs-aux! Mutator
92.2.1 Problem Analysis
92.2.2 Signature, Statements, and Function Header
92.2.3 Function Body
92.2.4 Termination Argument
92.3 The partition! Mutator
92.3.1 Problem Analysis
92.3.2 Signature, Statements, and Function Header
92.3.3 Function Body
92.3.4 Termination Argument
92.4 The Design of first<=
92.4.1 Problem Analysis
92.4.2 Signature, Statements, and Function Header
92.4.3 Function Body
92.5 The Design of first>
92.5.1 Problem Analysis
92.5.2 Signature, Statements, and Function Header
92.5.3 Function Body
92.6 Completing the Design
93 In-Place Heap Sorting
93.1 Heaps
93.2 Sorting
93.3 Mapping a Heap to a Vector
93.4 The heap-sort-in-place! Mutator
93.4.1 Problem Analysis
93.4.2 Signature, Statements, and Function Header
93.4.3 Tests
93.4.4 Function Body
93.5 The sorter! Mutator
93.5.1 Problem Analysis
93.5.2 Signature, Statements, and Function Header
93.5.3 Function Body
93.6 The trickle-down! Mutator
93.6.1 Problem Analysis
93.6.2 Signature, Statements, and Function Header
93.6.3 Function Body
93.6.4 Termination Argument
93.7 The heapify! Mutator
93.7.1 Problem Analysis
93.7.2 Signature, Statements, and Function Header
93.7.3 Function Body
93.7.4 Complexity and Performance
94 Empirical Project
94.1 Radix Sorting
94.2 The Project
95 What Have We Learned in This Chapter?
18 The Chicken and the Egg Paradox
96 The Paradox in Programming
97 Solving the Paradox
97.1 Problem Analysis
97.2 Sample Expressions and Differences
97.3 Signature, Statements, and Function Header
97.4 Tests
97.5 Function Body
98 Adding Clients to a Bank
98.1 Problem and Data Analysis
98.2 State Variable Definition
98.3 Bank Initializer
98.4 The add-account! Mutator
98.4.1 Problem Analysis
98.4.2 Signature, Statements, and Function Header
98.4.3 Tests
98.4.4 Function Body
99 What Have We Learned in This Chapter?
Part V Epilogue
19 Where to Go from Here
