| |

| |

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