| |
| |
| 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 | |