Annotated Table of Contents of Concrete Abstractions

This is the table of contents for the textbook Concrete Abstractions: An Introduction to Computer Science Using Scheme, by Max Hailperin, Barbara Kaiser, and Karl Knight. Free access to the full text in PDF form and supporting materials are also available.

Each name of a part, chapter, or appendix is a link to a description of that portion of the book.


Prefaceix
Part I: Procedural Abstraction1
1Computer Science and Programming3
1.1What's It All About?3
1.2Programming in Scheme5
Sidebar: Responsible Computer Use5
1.3An Application: Quilting15
2Recursion and Induction22
2.1Recursion22
Sidebar: Exponents28
2.2Induction28
2.3Further Examples34
2.4An Application: Custom-Sized Quilts40
3Iteration and invariants48
3.1Iteration48
3.2Using Invariants54
3.3Perfect Numbers, Internal Definitions, and Let58
3.4Iterative Improvement: Approximating the Golden Ratio61
3.5An Application: The Josephus Problem65
4Orders of Growth and Tree Recursion75
4.1Orders of Growth75
Sidebar: Logarithms82
4.2Tree Recursion and Digital Signatures83
Sidebar: Modular Arithmetic87
4.3An Application: Fractal Curves95
5Higher-Order Procedures109
5.1Procedural Parameters109
5.2Uncomputability113
Sidebar: Alan Turing116
5.3Procedures That Make Procedures118
5.4An Application: Verifying ID Numbers120
Part II: Data Abstraction131
6Compound Data and Data Abstraction133
6.1Introduction133
6.2Nim135
6.3Representations and Implementations143
6.4Three-Pile Nim153
6.5An Application: Adding Strategies to Nim156
Sidebar: Type Checking157
7Lists167
7.1The Definition of a List167
7.2Constructing Lists169
7.3Basic List Processing Techniques172
7.4List Processing and Iteration179
7.5Tree Recursion and Lists182
7.6An Application: A Movie Query System187
Sidebar: Is There More to Intelligence Than the Appearance of Intelligence?202
8Trees212
8.1Binary Search Trees212
8.2Efficiency Issues with Binary Search Trees220
Sidebar: Privacy Issues225
8.3Expression Trees226
8.4An Application: Automated Phone Books229
9Generic Operations243
9.1Introduction243
9.2Multiple Representations244
9.3Exploiting Commonality253
9.4An Application: Computer Graphics262
10Implementing Programming Languages278
10.1Introduction278
10.2Syntax279
Sidebar: The Expressiveness of EBNF285
10.3Micro-Scheme289
10.4Global Definitions: Mini-Scheme303
10.5An Application: Adding Explanatory Output311
Part III: Abstractions of State331
11Computers with Memory333
11.1Introduction333
11.2An Example Computer Architecture333
11.3Programming the SLIM340
Sidebar: What Can Be Stored in a Location?342
11.4Iteration in Assembly Language349
11.5Recursion in Assembly Language357
11.6Memory in Scheme: Vectors361
11.7An Application: A Simulator for SLIM367
12Dynamic Programming379
12.1Introduction379
12.2Revisiting Tree Recursion380
12.3Memoization388
12.4Dynamic Programming398
12.5Comparing Memoization and Dynamic Programming406
12.6An Application: Formatting Paragraphs406
13Object-Based Abstractions420
13.1Introduction420
13.2Arithmetic Expressions Revisited421
13.3RA-Stack Implementations and Representation Invariants432
Sidebar: Strings and Characters433
13.4Queues446
13.5Binary Search Trees Revisited453
13.6An Application: Dictionaries472
14Object-Oriented Programming486
14.1Introduction486
14.2An Object-Oriented Program487
14.3Extensions and Variations511
14.4Implementing an Object-Oriented Programming System517
14.5An Application: Adventures in the Land of Gack543
15Java, Applets, and Concurrency577
15.1Introduction577
15.2Java578
15.3Event-Driven Graphical User Interfaces in Applets599
15.4Concurrency616
Sidebar: Nested Calls to Synchronized Methods and Deadlock625
15.5An Application: Simulating Compound Interest632
Appendix: Nonstandard Extensions to Scheme645
Bibliography649
Index653

For more information contact Max Hailperin:
Email: max@gustavus.edu
Voice: (507) 933-7466
Fax: (507) 933-7041
Mathematics and Computer Science Department
Gustavus Adolphus College
800 W. College Avenue
St. Peter, MN 56082
USA