Each name of a part, chapter, or appendix is a link to a description of that portion of the book.
Preface | ix | |
---|---|---|
Part I: Procedural Abstraction | 1 | |
1 | Computer Science and Programming | 3 |
1.1 | What's It All About? | 3 |
1.2 | Programming in Scheme | 5 |
Sidebar: Responsible Computer Use | 5 | |
1.3 | An Application: Quilting | 15 |
2 | Recursion and Induction | 22 |
2.1 | Recursion | 22 |
Sidebar: Exponents | 28 | |
2.2 | Induction | 28 |
2.3 | Further Examples | 34 |
2.4 | An Application: Custom-Sized Quilts | 40 |
3 | Iteration and invariants | 48 |
3.1 | Iteration | 48 |
3.2 | Using Invariants | 54 |
3.3 | Perfect Numbers, Internal Definitions, and Let | 58 |
3.4 | Iterative Improvement: Approximating the Golden Ratio | 61 |
3.5 | An Application: The Josephus Problem | 65 |
4 | Orders of Growth and Tree Recursion | 75 |
4.1 | Orders of Growth | 75 |
Sidebar: Logarithms | 82 | |
4.2 | Tree Recursion and Digital Signatures | 83 |
Sidebar: Modular Arithmetic | 87 | |
4.3 | An Application: Fractal Curves | 95 |
5 | Higher-Order Procedures | 109 |
5.1 | Procedural Parameters | 109 |
5.2 | Uncomputability | 113 |
Sidebar: Alan Turing | 116 | |
5.3 | Procedures That Make Procedures | 118 |
5.4 | An Application: Verifying ID Numbers | 120 |
Part II: Data Abstraction | 131 | |
6 | Compound Data and Data Abstraction | 133 |
6.1 | Introduction | 133 |
6.2 | Nim | 135 |
6.3 | Representations and Implementations | 143 |
6.4 | Three-Pile Nim | 153 |
6.5 | An Application: Adding Strategies to Nim | 156 |
Sidebar: Type Checking | 157 | |
7 | Lists | 167 |
7.1 | The Definition of a List | 167 |
7.2 | Constructing Lists | 169 |
7.3 | Basic List Processing Techniques | 172 |
7.4 | List Processing and Iteration | 179 |
7.5 | Tree Recursion and Lists | 182 |
7.6 | An Application: A Movie Query System | 187 |
Sidebar: Is There More to Intelligence Than the Appearance of Intelligence? | 202 | |
8 | Trees | 212 |
8.1 | Binary Search Trees | 212 |
8.2 | Efficiency Issues with Binary Search Trees | 220 |
Sidebar: Privacy Issues | 225 | |
8.3 | Expression Trees | 226 |
8.4 | An Application: Automated Phone Books | 229 |
9 | Generic Operations | 243 |
9.1 | Introduction | 243 |
9.2 | Multiple Representations | 244 |
9.3 | Exploiting Commonality | 253 |
9.4 | An Application: Computer Graphics | 262 |
10 | Implementing Programming Languages | 278 |
10.1 | Introduction | 278 |
10.2 | Syntax | 279 |
Sidebar: The Expressiveness of EBNF | 285 | |
10.3 | Micro-Scheme | 289 |
10.4 | Global Definitions: Mini-Scheme | 303 |
10.5 | An Application: Adding Explanatory Output | 311 |
Part III: Abstractions of State | 331 | |
11 | Computers with Memory | 333 |
11.1 | Introduction | 333 |
11.2 | An Example Computer Architecture | 333 |
11.3 | Programming the SLIM | 340 |
Sidebar: What Can Be Stored in a Location? | 342 | |
11.4 | Iteration in Assembly Language | 349 |
11.5 | Recursion in Assembly Language | 357 |
11.6 | Memory in Scheme: Vectors | 361 |
11.7 | An Application: A Simulator for SLIM | 367 |
12 | Dynamic Programming | 379 |
12.1 | Introduction | 379 |
12.2 | Revisiting Tree Recursion | 380 |
12.3 | Memoization | 388 |
12.4 | Dynamic Programming | 398 |
12.5 | Comparing Memoization and Dynamic Programming | 406 |
12.6 | An Application: Formatting Paragraphs | 406 |
13 | Object-Based Abstractions | 420 |
13.1 | Introduction | 420 |
13.2 | Arithmetic Expressions Revisited | 421 |
13.3 | RA-Stack Implementations and Representation Invariants | 432 |
Sidebar: Strings and Characters | 433 | |
13.4 | Queues | 446 |
13.5 | Binary Search Trees Revisited | 453 |
13.6 | An Application: Dictionaries | 472 |
14 | Object-Oriented Programming | 486 |
14.1 | Introduction | 486 |
14.2 | An Object-Oriented Program | 487 |
14.3 | Extensions and Variations | 511 |
14.4 | Implementing an Object-Oriented Programming System | 517 |
14.5 | An Application: Adventures in the Land of Gack | 543 |
15 | Java, Applets, and Concurrency | 577 |
15.1 | Introduction | 577 |
15.2 | Java | 578 |
15.3 | Event-Driven Graphical User Interfaces in Applets | 599 |
15.4 | Concurrency | 616 |
Sidebar: Nested Calls to Synchronized Methods and Deadlock | 625 | |
15.5 | An Application: Simulating Compound Interest | 632 |
Appendix: Nonstandard Extensions to Scheme | 645 | |
Bibliography | 649 | |
Index | 653 |