Animated Program Design: Intermediate Program Design Using Video Game Development

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