Foundations of computer science
By: Alfred V. Aho, Jeffrey D. Ullman.
Contributors: Ullman, Jeffrey D., 1942-
Series: Principles of computer science series
Publisher: Computer Science Press
Published: 1992
Place of publication: New York
Language: eng
Number of pages: 765
Subjects: Computer science
Notes: Includes bibliographical references and index.
Table of contents: title: Preface
pagenum: ix; label: Chapter 1
title: Computer Science: The Mechanization of Abstraction
pagenum: 1; label: 1.1
title: What This Book Is About
pagenum: 3; label: 1.2
title: What This Chapter Is About
pagenum: 6; label: 1.3
title: Data Models
pagenum: 6; label: 1.4
title: The Pascal Data Model
pagenum: 12; label: 1.5
title: Algorithms and the Design of Programs
pagenum: 19; label: 1.6
title: Summary of Chapter 1
pagenum: 21; label: 1.7
title: Bibliographic Notes for Chapter 1
pagenum: 21; label: Chapter 2
title: Iteration, Induction, and Recursion
pagenum: 23; label: 2.1
title: What This Chapter Is About
pagenum: 25; label: 2.2
title: Iteration
pagenum: 25; label: 2.3
title: Inductive Proofs
pagenum: 32; label: 2.4
title: Complete Induction
pagenum: 40; label: 2.5
title: Proving Properties of Programs
pagenum: 45; label: 2.6
title: Recursive Definitions
pagenum: 53; label: 2.7
title: Recursive Procedures
pagenum: 62; label: 2.8
title: Merge Sort: A Recursive Sorting Algorithm
pagenum: 68; label: 2.9
title: Proving Properties of Recursive Programs
pagenum: 79; label: 2.10
title: Summary of Chapter 2
pagenum: 82; label: 2.11
title: Bibliographic Notes for Chapter 2
pagenum: 82; label: Chapter 3
title: The Running Time of Programs
pagenum: 83; label: 3.1
title: What This Chapter Is About
pagenum: 83; label: 3.2
title: Choosing An Algorithm
pagenum: 84; label: 3.3
title: Measuring Running Time
pagenum: 85; label: 3.4
title: Big-Oh and Approximate Running Time
pagenum: 90; label: 3.5
title: Simplifying Big-Oh Expressions
pagenum: 94; label: 3.6
title: Analyzing the Running Time of a Program
pagenum: 101; label: 3.7
title: A Recursive Rule for Bounding the Running Time
pagenum: 108; label: 3.8
title: Analyzing Programs with Procedure Calls
pagenum: 115; label: 3.9
title: Analyzing Recursive Procedures
pagenum: 120; label: 3.10
title: Analysis of Merge Sort
pagenum: 124; label: 3.11
title: Solving Recurrence Relations
pagenum: 132; label: 3.12
title: Summary of Chapter 3
pagenum: 141; label: 3.13
title: Bibliographic Notes for Chapter 3
pagenum: 142; label: Chapter 4
title: Data Models for the Computer
pagenum: 143; label: 4.1
title: What This Chapter Is About
pagenum: 143; label: 4.2
title: The Hierarchy of Abstractions in a Computer
pagenum: 144; label: 4.3
title: A Look at a Typical Computer
pagenum: 146; label: 4.4
title: The Main Memory
pagenum: 148; label: 4.5
title: Secondary Storage Devices
pagenum: 155; label: 4.6
title: Machine Instructions and Their Execution
pagenum: 161; label: 4.7
title: A Typical Instruction Set
pagenum: 165; label: 4.8
title: Supporting the Pascal Data Model
pagenum: 174; label: 4.9
title: Representing Structures: The General Case
pagenum: 178; label: 4.10
title: The Running Time of Programs
pagenum: 186; label: 4.11
title: Representing Integers by Computer Words
pagenum: 192; label: 4.12
title: Representing Real Numbers
pagenum: 200; label: 4.13
title: The File Model of Secondary Storage
pagenum: 202; label: 4.14
title: Summary of Chapter 4
pagenum: 205; label: 4.15
title: Bibliographic Notes for Chapter 4
pagenum: 205; label: Chapter 5
title: The Tree Data Model
pagenum: 207; label: 5.1
title: What This Chapter Is About
pagenum: 207; label: 5.2
title: Basic Terminology
pagenum: 208; label: 5.3
title: Data Structures for Trees
pagenum: 215; label: 5.4
title: Recursions on Trees
pagenum: 222; label: 5.5
title: Structural Induction
pagenum: 231; label: 5.6
title: Binary Trees
pagenum: 236; label: 5.7
title: Generating Assembly Code from Binary Trees
pagenum: 241; label: 5.8
title: Binary Search Trees
pagenum: 248; label: 5.9
title: Efficiency of Binary Search Tree Operations
pagenum: 256; label: 5.10
title: Priority Queues and Partially Ordered Trees
pagenum: 259; label: 5.11
title: Heapsort: Sorting with Balanced POTs
pagenum: 267; label: 5.12
title: Summary of Chapter 5
pagenum: 271; label: 5.13
title: Bibliographic Notes for Chapter 5
pagenum: 272; label: Chapter 6
title: The List Data Model
pagenum: 273; label: 6.1
title: What This Chapter Is About
pagenum: 273; label: 6.2
title: Basic Terminology
pagenum: 274; label: 6.3
title: Operations on Lists
pagenum: 277; label: 6.4
title: The Linked-List Data Structure
pagenum: 280; label: 6.5
title: Array-Based Implementation of Lists
pagenum: 287; label: 6.6
title: Stacks
pagenum: 292; label: 6.7
title: Implementing Procedure Calls Using a Stack
pagenum: 298; label: 6.8
title: Queues
pagenum: 304; label: 6.9
title: Longest Common Subsequences
pagenum: 307; label: 6.10
title: Representing Character Strings
pagenum: 313; label: 6.11
title: Summary of Chapter 6
pagenum: 320; label: 6.12
title: Bibliographic Notes for Chapter 6
pagenum: 321; label: Chapter 7
title: The Set Data Model
pagenum: 323; label: 7.1
title: What This Chapter Is About
pagenum: 323; label: 7.2
title: Basic Definitions
pagenum: 323; label: 7.3
title: Operations on Sets
pagenum: 326; label: 7.4
title: List Implementation of Sets
pagenum: 336; label: 7.5
title: Characteristic Vector Implementation of Sets
pagenum: 342; label: 7.6
title: Hashing
pagenum: 346; label: 7.7
title: Relations and Functions
pagenum: 352; label: 7.8
title: Implementing Functions as Data
pagenum: 359; label: 7.9
title: Implementing Binary Relations
pagenum: 365; label: 7.10
title: Some Special Properties of Binary Relations
pagenum: 371; label: 7.11
title: Infinite Sets
pagenum: 381; label: 7.12
title: Summary of Chapter 7
pagenum: 385; label: 7.13
title: Bibliographic Notes for Chapter 7
pagenum: 386; label: Chapter 8
title: The Relational Data Model
pagenum: 387; label: 8.1
title: What This Chapter Is About
pagenum: 387; label: 8.2
title: Relations
pagenum: 388; label: 8.3
title: Keys
pagenum: 395; label: 8.4
title: Primary Storage Structures for Relations
pagenum: 398; label: 8.5
title: Secondary Index Structures
pagenum: 403; label: 8.6
title: Navigation among Relations
pagenum: 407; label: 8.7
title: An Algebra of Relations
pagenum: 412; label: 8.8
title: Implementing Relational Algebra Operations
pagenum: 419; label: 8.9
title: Algebraic Laws for Relations
pagenum: 424; label: 8.10
title: Summary of Chapter 8
pagenum: 433; label: 8.11
title: Bibliographic Notes for Chapter 8
pagenum: 434; label: Chapter 9
title: The Graph Data Model
pagenum: 435; label: 9.1
title: What This Chapter Is About
pagenum: 435; label: 9.2
title: Basic Concepts
pagenum: 436; label: 9.3
title: Implementation of Graphs
pagenum: 442; label: 9.4
title: Connected Components of an Undirected Graph
pagenum: 449; label: 9.5
title: Minimal Spanning Trees
pagenum: 460; label: 9.6
title: Depth-First Search
pagenum: 466; label: 9.7
title: Some Uses of Depth-First Search
pagenum: 477; label: 9.8
title: Dijkstra's Algorithm for Finding Shortest Paths
pagenum: 483; label: 9.9
title: Floyd's Algorithm for Shortest Paths
pagenum: 494; label: 9.10
title: An Introduction to Graph Theory
pagenum: 502; label: 9.11
title: Summary of Chapter 9
pagenum: 506; label: 9.12
title: Bibliographic Notes for Chapter 9
pagenum: 507; label: Chapter 10
title: Patterns, Automata, and Regular Expressions
pagenum: 509; label: 10.1
title: What This Chapter Is About
pagenum: 510; label: 10.2
title: State Machines and Automata
pagenum: 510; label: 10.3
title: Deterministic and Nondeterministic Automata
pagenum: 517; label: 10.4
title: From Nondeterminism to Determinism
pagenum: 527; label: 10.5
title: Regular Expressions
pagenum: 537; label: 10.6
title: The UNIX Extensions to Regular Expressions
pagenum: 544; label: 10.7
title: Algebraic Laws for Regular Expressions
pagenum: 548; label: 10.8
title: From Regular Expressions to Automata
pagenum: 551; label: 10.9
title: From Automata to Regular Expressions
pagenum: 562; label: 10.10
title: Summary of Chapter 10
pagenum: 568; label: 10.11
title: Bibliographic Notes for Chapter 10
pagenum: 569; label: Chapter 11
title: Recursive Description of Patterns
pagenum: 571; label: 11.1
title: What This Chapter Is About
pagenum: 571; label: 11.2
title: Context-Free Grammars
pagenum: 572; label: 11.3
title: Languages from Grammars
pagenum: 579; label: 11.4
title: Parse Trees
pagenum: 581; label: 11.5
title: Ambiguity and the Design of Grammars
pagenum: 589; label: 11.6
title: Constructing Parse Trees
pagenum: 596; label: 11.7
title: A Table-Driven Parsing Algorithm
pagenum: 603; label: 11.8
title: Grammars Versus Regular Expressions
pagenum: 610; label: 11.9
title: Summary of Chapter 11
pagenum: 617; label: 11.10
title: Bibliographic Notes for Chapter 11
pagenum: 617; label: Chapter 12
title: Propositional Logic
pagenum: 619; label: 12.1
title: What This Chapter Is About
pagenum: 619; label: 12.2
title: What Is Propositional Logic?
pagenum: 620; label: 12.3
title: Logical Expressions
pagenum: 621; label: 12.4
title: Truth Tables
pagenum: 625; label: 12.5
title: From Boolean Functions to Logical Expressions
pagenum: 630; label: 12.6
title: Designing Logical Expressions by Karnaugh Maps
pagenum: 636; label: 12.7
title: Tautologies
pagenum: 645; label: 12.8
title: Some Algebraic Laws for Logical Expressions
pagenum: 650; label: 12.9
title: Tautologies and Methods of Proof
pagenum: 657; label: 12.10
title: Deduction
pagenum: 662; label: 12.11
title: Proofs by Resolution
pagenum: 667; label: 12.12
title: Summary of Chapter 12
pagenum: 672; label: 12.13
title: Bibliographic Notes for Chapter 12
pagenum: 673; label: Chapter 13
title: Using Logic to Design Computer Components
pagenum: 675; label: 13.1
title: What This Chapter Is About
pagenum: 675; label: 13.2
title: Gates
pagenum: 676; label: 13.3
title: Circuits
pagenum: 677; label: 13.4
title: Logical Expressions and Circuits
pagenum: 681; label: 13.5
title: Some Physical Constraints on Circuits
pagenum: 686; label: 13.6
title: A Divide-and-Conquer Addition Circuit
pagenum: 692; label: 13.7
title: Design of a Multiplexer
pagenum: 699; label: 13.8
title: Memory Elements
pagenum: 707; label: 13.9
title: Summary of Chapter 13
pagenum: 708; label: 13.10
title: Bibliographic Notes for Chapter 13
pagenum: 709; label: Chapter 14
title: Predicate Logic
pagenum: 711; label: 14.1
title: What This Chapter Is About
pagenum: 711; label: 14.2
title: Predicates
pagenum: 712; label: 14.3
title: Logical Expressions
pagenum: 714; label: 14.4
title: Quantifiers
pagenum: 716; label: 14.5
title: Interpretations
pagenum: 722; label: 14.6
title: Tautologies
pagenum: 728; label: 14.7
title: Tautologies Involving Quantifiers
pagenum: 730; label: 14.8
title: Proofs in Predicate Logic
pagenum: 737; label: 14.9
title: Proofs from Rules and Facts
pagenum: 740; label: 14.10
title: Truth and Provability
pagenum: 746; label: 14.11
title: Summary of Chapter 14
pagenum: 752; label: 14.12
title: Bibliographic Notes for Chapter 14
pagenum: 753; title: Index
pagenum: 755