Introduction 1
0-1 The Study of Algorithms 1
0-2 The Development of Algorithmic Machines 5
0-3 Modern Machine Architecture 9
0-4 The Evolution of Computer Science 12
Additional Reading 14
PART ONE MACHINE ARCHITECTURE 15
Chapter 1 Data Storage 17
1-1 Main Memory 18
1-2 Mass Storage 23
1-3 Coding Information for Storage 29
1-4 The Binary System 33
1-5 Storing Integers 36
1-6 Storing Fractions 44
1-7 Communication Errors 47
Review Problems 52
Problems for the Programmer 55
Additional Reading 55
Chapter 2 Data Manipulation 57
2-1 The Central Processing Unit 58
2-2 The Stored-Program Concept 62
2-3 Program Execution 66
2-4 Other Architectures 71
2-5 Arithmetic/Logic Instructions 75
2-6 Computer/Peripheral Communication 80
Review Problems 85
Problems for the Programmer 88
Additional Reading 89
PART TWO SOFTWARE 91
Chapter 3 Operating Systems 93
3-1 Functions of Operating Systems 94
3-2 Virtual Characteristics and Abstraction 97
3-3 The Evolution of Operating Systems 99
3-4 Operating System Architecture 105
3-5 Rudiments of Time-Sharing 109
3-6 Resource Allocation 112
3-7 Getting It Started 116
3-8 A Closer Look at Networks 118
Review Problems 127
Problems for the Programmer 129
Additional Reading 130
Chapter 4 Algorithms 131
4-1 Definition 132
4-2 Algorithm Representation 133
4-3 Algorithm Discovery 142
4-4 Iterative Structures 148
4-5 Recursive Structures 158
4-6 Efficiency and Correctness 173
Review Problems 182
Problems for the Programmer 186
Additional Reading 186
Chapter 5 Programming Languages 187
5-1 Historical Perspective 188
5-2 Language Implementation 197
5-3 Programming Language Design 201
5-4 Procedural Language Components 206
5-5 Parallel Computing 229
5-6 Declarative Programming 232
Review Problems 238
Problems for the Programmer 241
Additional Reading 242
Chapter 6 Software Engineering 243
6-1 The Software Engineering Discipline 244
6-2 The Software Life Cycle 246
6-3 Modularity 250
6-4 Development Tools and Techniques 255
6-5 Documentation 261
Review Problems 263
Problems for the Programmer 266
Additional Reading 266
PART THREE DATA ORGANIZATION 267
Chapter 7 Data Structures 269
7-1 Arrays 270
7-2 Lists 273
7-3 Stacks 280
7-4 Queues 284
7-5 Trees 289
7-6 Abstract Data Types 298
7-7 Object-Oriented Programming 302
Review Problems 306
Problems for the Programmer 310
Additional Reading 310
Chapter 8 File Structures 311
8-1 Sequential Files 312
8-2 Text Files 317
8-3 Indexed Files 319
8-4 Hashed Files 324
8-5 The Role of the Operating System 330
Review Problems 332
Problems for the Programmer 334
Additional Reading 334
Chapter 9 Database Structures 335
9-1 General Issues 336
9-2 The Layered Approach to Database Implementation 339
9-3 The Relational Model 342
9-4 The Network Model 352
9-5 Object-Oriented Databases 360
9-6 Concurrency Control 363
Review Problems 368
Problems for the Programmer 372
Additional Reading 372
PART FOUR THE POTENTIAL OF ALGORITHMIC MACHINES 375
Chapter 10 Artificial Intelligence 377
10-1 Some Philosophical Issues 378
10-2 Image Analysis 382
10-3 Reasoning 384
10-4 Control System Activities 388
10-5 Using Heuristics 393
10-6 Artificial Neural Networks 399
10-7 Applications of Artif Icial Intelligence 405
Review Problems 412
Problems for the Programmer 415
Additional Reading 415
Chapter 11 Theory of Computation 417
11-1 A Bare Bones Programming Language 418
11-2 Turing Machines 424
11-3 Computable Functions 428
11-4 A Noncomputable Function 432
11-5 Complexity and Its Measure 437
11-6 Problem Classification 444
Review Problems 449
Problems for the Programmer 451
Additional Reading 452
Appendix A Popular Codes 454
Appendix B A Typical Machine Language 455
Appendix C Insertion Sort in Assembly Language 457
Appendix D Syntax Diagrams for Pascal 459
Appendix E The Equivalence of Loop and Recursive Structures 469
Appendix F Answers to Questions/Exercises 471
Index 499