An edition of Foundations of computer science (1992)

Foundations of computer science

by

  • 11 Want to read
  • 1 Currently reading
Cover of: Foundations of computer science by Alfred V. Aho, Alfred V. Aho
Preview
Borrow

My Reading Lists:

Create a new list
Notes
  • 11 Want to read
  • 1 Currently reading
Notes

Check nearby libraries

Buy this book

Last edited by Open Library Bot
April 28, 2010 | History
Edit
An edition of Foundations of computer science (1992)

Foundations of computer science

by

  • 11 Want to read
  • 1 Currently reading

This work doesn't have a description yet. Can you add one?

Publish Date
Publisher
Computer Science Press
Language
English
Pages
765

Check nearby libraries

Buy this book

Previews available in: English

Subjects

Computer science, C (Computer program language)
Edition Availability
Cover of: Foundations of computer science
Foundations of computer science
1995, Computer Science Press
in English - C ed.
Cover of: Foundations of Computer Science
Foundations of Computer Science: C Edition (Principles of Computer Science Series)
October 15, 1994, W. H. Freeman
Hardcover in English - New Ed edition
Cover of: Foundations of computer science
Foundations of computer science
1992, Computer Science Press
in English

Add another edition?

Book Details

Table of Contents

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

Edition Notes

Includes bibliographical references and index.

Published in
New York
Series
Principles of computer science series

Classifications

Dewey Decimal Class
004
Library of Congress
QA76 .A334 1992

The Physical Object

Pagination
xiii, 765 p. :
Number of pages
765

Edition Identifiers

Open Library
OL1557209M
Internet Archive
foundationsofcom00alfr
ISBN 10
0716782332
LCCN
91037894
LibraryThing
24201
Goodreads
2921301

Work Identifiers

Work ID
OL3509443W

Source records

Community Reviews (0)

No community reviews have been submitted for this work.

Lists

Loading indicator
Loading carousel
Loading indicator
Loading carousel

History

Download catalog record: RDF / JSON
April 28, 2010 Edited by Open Library Bot Linked existing covers to the work.
February 14, 2010 Edited by WorkBot add more information to works
December 10, 2009 Created by WorkBot add works page