| |
| |
Preface | |
| |
| |
| |
Computer Science: The Mechanization of Abstraction | |
| |
| |
| |
What This Book Is About | |
| |
| |
| |
What This Chapter Is About | |
| |
| |
| |
Data Models | |
| |
| |
| |
The Pascal Data Model | |
| |
| |
| |
Algorithms and the Design of Programs | |
| |
| |
| |
Summary of Chapter 1 | |
| |
| |
| |
Bibliographic Notes for Chapter 1 | |
| |
| |
| |
Iteration, Induction, and Recursion | |
| |
| |
| |
What This Chapter Is About | |
| |
| |
| |
Iteration | |
| |
| |
| |
Inductive Proofs | |
| |
| |
| |
Complete Induction | |
| |
| |
| |
Proving Properties of Programs | |
| |
| |
| |
Recursive Definitions | |
| |
| |
| |
Recursive Procedures | |
| |
| |
| |
Merge Sort: A Recursive Sorting Algorithm | |
| |
| |
| |
Proving Properties of Recursive Programs | |
| |
| |
| |
Summary of Chapter 2 | |
| |
| |
| |
Bibliographic Notes for Chapter 2 | |
| |
| |
| |
The Running Time of Programs | |
| |
| |
| |
What This Chapter Is About | |
| |
| |
| |
Choosing An Algorithm | |
| |
| |
| |
Measuring Running Time | |
| |
| |
| |
Big-Oh and Approximate Running Time | |
| |
| |
| |
Simplifying Big-Oh Expressions | |
| |
| |
| |
Analyzing the Running Time of a Program | |
| |
| |
| |
A Recursive Rule for Bounding the Running Time | |
| |
| |
| |
Analyzing Programs with Procedure Calls | |
| |
| |
| |
Analyzing Recursive Procedures | |
| |
| |
| |
Analysis of Merge Sort | |
| |
| |
| |
Solving Recurrence Relations | |
| |
| |
| |
Summary of Chapter 3 | |
| |
| |
| |
Bibliographic Notes for Chapter 3 | |
| |
| |
| |
Data Models for the Computer | |
| |
| |
| |
What This Chapter Is About | |
| |
| |
| |
The Hierarchy of Abstractions in a Computer | |
| |
| |
| |
A Look at a Typical Computer | |
| |
| |
| |
The Main Memory | |
| |
| |
| |
Secondary Storage Devices | |
| |
| |
| |
Machine Instructions and Their Execution | |
| |
| |
| |
A Typical Instruction Set | |
| |
| |
| |
Supporting the Pascal Data Model | |
| |
| |
| |
Representing Structures: The General Case | |
| |
| |
| |
The Running Time of Programs | |
| |
| |
| |
Representing Integers by Computer Words | |
| |
| |
| |
Representing Real Numbers | |
| |
| |
| |
The File Model of Secondary Storage | |
| |
| |
| |
Summary of Chapter 4 | |
| |
| |
| |
Bibliographic Notes for Chapter 4 | |
| |
| |
| |
The Tree Data Model | |
| |
| |
| |
What This Chapter Is About | |
| |
| |
| |
Basic Terminology | |
| |
| |
| |
Data Structures for Trees | |
| |
| |
| |
Recursions on Trees | |
| |
| |
| |
Structural Induction | |
| |
| |
| |
Binary Trees | |
| |
| |
| |
Generating Assembly Code from Binary Trees | |
| |
| |
| |
Binary Search Trees | |
| |
| |
| |
Efficiency of Binary Search Tree Operations | |
| |
| |
| |
Priority Queues and Partially Ordered Trees | |
| |
| |
| |
Heapsort: Sorting with Balanced POTs | |
| |
| |
| |
Summary of Chapter 5 | |
| |
| |
| |
Bibliographic Notes for Chapter 5 | |
| |
| |
| |
The List Data Model | |
| |
| |
| |
What This Chapter Is About | |
| |
| |
| |
Basic Terminology | |
| |
| |
| |
Operations on Lists | |
| |
| |
| |
The Linked-List Data Structure | |
| |
| |
| |
Array-Based Implementation of Lists | |
| |
| |
| |
Stacks | |
| |
| |
| |
Implementing Procedure Calls Using a Stack | |
| |
| |
| |
Queues | |
| |
| |
| |
Longest Common Subsequences | |
| |
| |
| |
Representing Character Strings | |
| |
| |
| |
Summary of Chapter 6 | |
| |
| |
| |
Bibliographic Notes for Chapter 6 | |
| |
| |
| |
The Set Data Model | |
| |
| |
| |
What This Chapter Is About | |
| |
| |
| |
Basic Definitions | |
| |
| |
| |
Operations on Sets | |
| |
| |
| |
List Implementation of Sets | |
| |
| |
| |
Characteristic Vector Implementation of Sets | |
| |
| |
| |
Hashing | |
| |
| |
| |
Relations and Functions | |
| |
| |
| |
Implementing Functions as Data | |
| |
| |
| |
Implementing Binary Relations | |
| |
| |
| |
Some Special Properties of Binary Relations | |
| |
| |
| |
Infinite Sets | |
| |
| |
| |
Summary of Chapter 7 | |
| |
| |
| |
Bibliographic Notes for Chapter 7 | |
| |
| |
| |
The Relational Data Model | |
| |
| |
| |
What This Chapter Is About | |
| |
| |
| |
Relations | |
| |
| |
| |
Keys | |
| |
| |
| |
Primary Storage Structures for Relations | |
| |
| |
| |
Secondary Index Structures | |
| |
| |
| |
Navigation among Relations | |
| |
| |
| |
An Algebra of Relations | |
| |
| |
| |
Implementing Relational Algebra Operations | |
| |
| |
| |
Algebraic Laws for Relations | |
| |
| |
| |
Summary of Chapter 8 | |
| |
| |
| |
Bibliographic Notes for Chapter 8 | |
| |
| |
| |
The Graph Data Model | |
| |
| |
| |
What This Chapter Is About | |
| |
| |
| |
Basic Concepts | |
| |
| |
| |
Implementation of Graphs | |
| |
| |
| |
Connected Components of an Undirected Graph | |
| |
| |
| |
Minimal Spanning Trees | |
| |
| |
| |
Depth-First Search | |
| |
| |
| |
Some Uses of Depth-First Search | |
| |
| |
| |
Dijkstra's Algorithm for Finding Shortest Paths | |
| |
| |
| |
Floyd's Algorithm for Shortest Paths | |
| |
| |
| |
An Introduction to Graph Theory | |
| |
| |
| |
Summary of Chapter 9 | |
| |
| |
| |
Bibliographic Notes for Chapter 9 | |
| |
| |
| |
Patterns, Automata, and Regular Expressions | |
| |
| |
| |
What This Chapter Is About | |
| |
| |
| |
State Machines and Automata | |
| |
| |
| |
Deterministic and Nondeterministic Automata | |
| |
| |
| |
From Nondeterministism to Deterministism | |
| |
| |
| |
Regular Expressions | |
| |
| |
| |
The UNIX Extensions to Regular Expressions | |
| |
| |
| |
Algebraic Laws for Regular Expressions | |
| |
| |
| |
From Regular Expressions to Automata | |
| |
| |
| |
From Automata to Regular Expressions | |
| |
| |
| |
Summary of Chapter 10 | |
| |
| |
| |
Bibliographic Notes for Chapter 10 | |
| |
| |
| |
Recursive Description of Patterns | |
| |
| |
| |
What This Chapter Is About | |
| |
| |
| |
Context-Free Grammars | |
| |
| |
| |
Languages from Grammars | |
| |
| |
| |
Parse Trees | |
| |
| |
| |
Ambiguity and the Design of Grammars | |
| |
| |
| |
Constructing Parse Trees | |
| |
| |
| |
A Table-Driven Parsing Algorithm | |
| |
| |
| |
Grammars Versus Regular Expressions | |
| |
| |
| |
Summary of Chapter 11 | |
| |
| |
| |
Bibliographic Notes for Chapter 11 | |
| |
| |
| |
Propositional Logic | |
| |
| |
| |
What This Chapter Is About | |
| |
| |
| |
What Is Propositional Logic? | |
| |
| |
| |
Logical Expressions | |
| |
| |
| |
Truth Tables | |
| |
| |
| |
From Boolean Functions to Logical Expressions | |
| |
| |
| |
Designing Logical Expressions by Karnaugh Maps | |
| |
| |
| |
Tautologies | |
| |
| |
| |
Some Algebraic Laws for Logical Expressions | |
| |
| |
| |
Tautologies and Methods of Proof | |
| |
| |
| |
Deduction | |
| |
| |
| |
Proofs by Resolution | |
| |
| |
| |
Summary of Chapter 12 | |
| |
| |
| |
Bibliographic Notes for Chapter 12 | |
| |
| |
| |
Using Logic to Design Computer Components | |
| |
| |
| |
What This Chapter Is About | |
| |
| |
| |
Gates | |
| |
| |
| |
Circuits | |
| |
| |
| |
Logical Expressions and Circuits | |
| |
| |
| |
Some Physical Constraints on Circuits | |
| |
| |
| |
A Divide-and-Conquer Addition Circuit | |
| |
| |
| |
Design of a Multiplexer | |
| |
| |
| |
Memory Elements | |
| |
| |
| |
Summary of Chapter 13 | |
| |
| |
| |
Bibliographic Notes for Chapter 13 | |
| |
| |
| |
Predicate Logic | |
| |
| |
| |
What This Chapter Is About | |
| |
| |
| |
Predicates | |
| |
| |
| |
Logical Expressions | |
| |
| |
| |
Quantifiers | |
| |
| |
| |
Interpretations | |
| |
| |
| |
Tautologies | |
| |
| |
| |
Tautologies Involving Quantifiers | |
| |
| |
| |
Proofs in Predicate Logic | |
| |
| |
| |
Proofs from Rules and Facts | |
| |
| |
| |
Truth and Provability | |
| |
| |
| |
Summary of Chapter 14 | |
| |
| |
| |
Bibliographic Notes for Chapter 14 | |
| |
| |
Index | |