Chapter 0 Introduction 1
0．1 The Study of Algorithms 2
0．2 The Origins of Computing Machines 6
0．3 The Evolution of Computer Science 10
0．4 The Role of Abstraction 11
0．5 Ethical/Social/Legal Repercussions 12
Social Issues 13
Additional Reading 14
PART ONE: MACHINE ARCHITECTURE 15
Chapter 1 Data Storage 17
1．1 Storage of Bits 18
1．2 Main Memory 26
1．3 Mass Storage 29
1．4 Representing Information as Bit Patterns 35
1．5 The Binary System 44
1．6 Storing Integers 47
1．7 Storing Fractions 55
1．8 Data Compression 60
1．9 Communication Errors 65
Chapter Review Problems 70
Social Issues 76
Additional Reading 77
Chapter 2 Data Manipulation 79
2．1 The Central Processing Unit 80
2．2 The Stored-Program Concept 85
2．3 Program Execution 89
2．4 Arithmetic/Logic Instructions 95
2．5 Communicating with Other Devices 99
2．6 Other Architectures 104
Chapter Review Problems 108
Social Issucs 114
Additional Reading 115
PART TWO:SOFTWARE 117
Chapter 3 Operating Systems and Networks 119
3．1 The Evolution of Operating Systems 120
3．2 Operating System Architecture 124
3．3 Coordinating the Machine s Activities 130
3．4 Handling Competition Among Processes 136
3．5 Network 141
3．6 Network Protocols 149
3．7 Security 158
Chapter Review Problems 162
Social Issues 165
Additional Reading 166
Chapter 4 Algorithms 167
4．1 The Concept of an Algorithm 168
4．2 Algorithm Representation 170
4．3 Algorithm Discovery 178
4．4 Iterative Structures 184
4．5 Recursive Structures 196
4．6 Efficiency and Correctness 206
Chapter Review Problems 218
Social Issues 223
Additional Reading 224
Chapter 5 Programming Languages 225
5．1 Historical Perspective 226
5．2 Traditional Programming Concepts 236
5．3 Procedural Units 248
5．4 Language Implementation 255
5．5 Object-Oriented Programming 265
5．6 Programming Concurrent Activities 268
5．7 Declarative Programming 271
Chapter Review Problems 278
Social Issues 281
Additional Reading 283
Chapter 6 Software Engineering 285
6．1 The Software Engineering Discipline 286
6．2 The Software Life Cycle 288
6．3 Modularity 294
6．4 Design Methodologies 300
6．5 Testing 308
6．6 Documentation 310
6．7 Software Ownership and Liability 312
Chapter Review Problems 314
Social Issues 316
Additional Reading 317
PART THREE: DATA ORGANIZATION 319
Chapter 7 Data Structures 321
7．1 Arrays 322
7．2 Lists 325
7．3 Stacks 332
7．4 Queues 337
7．5 Trees 341
7．6 Customized Data Types 353
7．7 Pointers in Machine Language 360
Chapter Review Problems 361
Social Issues 366
Additional Reading 367
Chapter 8 File Structures 369
8．1 The Role of the Operating System 370
8．2 Sequential Files 371
8．3 Text Files 377
8．4 Indexing 381
8．5 Hashing 385
Chapter Review Problems 391
Social Issues 394
Additional Reading 395
Chapter 9 Database Structures 397
9．1 General Issues 398
9．2 The Layered Approach to Database Implementation 401
9．3 The Relational Model 404
9．4 Object-Oriented Databases 418
9．5 Maintaining Database Integrity 421
9．6 Social Impact of Database Technology 425
Chapter Review Problems 428
Social Issues 432
Additional Reading 433
PART FOUR: THE POTENTIAL OF ALGORITHMIC MACHINES 435
Chapter 10 Artificial Intelligence 437
10．1 Intelligence and Machines 438
10．2 Understanding Images 442
10．3 Reasoning 445
10．4 Artificial Neural Networks 459
10．5 Genetic Algorithms 468
10．6 Applications of Artificial Intelligence 473
10．7 Considering the Consequences 481
Chapter Review Problems 484
Social Issues 488
Additional Reading 489
Chapter 11 Theory of Computation 491
11．1 A Bare Bones Programming Language 492
11．2 Turing Machines 497
11．3 Computable Functions 503
11．4 A Noncomputable Function 507
11．5 Complexity of Problems 513
11．6 Public Key Cryptography 523
Chapter Review Problems 532
Social Issues 535
Additional Reading 536
Appendixes 537
A ASCII 539
B Circuits to Manipulate Two s Complement Representations 541
C A Typical Machine Language 545
D Program Examples 547
E The Equivalence of Iterative and Recursive Structures 557
F Answers to Questions /Exercises 559
Index 599