Skip to content

Foundations of Computer Science

Spend $50 to get a free DVD!

ISBN-10: 0716782332

ISBN-13: 9780716782339

Edition: 1992

Authors: Alfred V. Aho, Jeffrey D. Ullman

List price: $59.95
Blue ribbon 30 day, 100% satisfaction guarantee!
what's this?
Rush Rewards U
Members Receive:
Carrot Coin icon
XP icon
You have reached 400 XP and carrot coins. That is the daily max!

Customers also bought

Book details

List price: $59.95
Copyright year: 1992
Publisher: Freeman & Company, W. H.
Binding: Hardcover
Pages: 832
Weight: 4.290
Language: English

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