Chapter 0 Introduction 1
0.1 The Role of Algorithms 2
0.2 The Origins of Computing Machines 4
0.3 The Science of Algorithms 9
0.4 Abstraction 9
0.5 An Outline of Our Study 11
0.6 Social Repercussions 12
Social Issues 13
Additional Reading 15
Chapter 1 Data Storage 17
1.1 Bits and Their Storage 18
1.2 Main Memory 26
1.3 Mass Storage 28
1.4 Representing Information as Bit Patterns 34
1.5 The Binary System 41
1.6 Storing Integers 46
1.7 Storing Fractions 53
1.8 Data Compression 57
1.9 Communication Errors 61
Chapter Review Problems 65
Social Issues 70
Additional Reading 71
Chapter 2 Data Manipulation 73
2.1 Computer Architecture 74
2.2 Machine Language 77
2.3 Program Execution 83
2.4 Arithmetic/Logic Instructions 90
2.5 Communicating with Other Devices 94
2.6 Other Architectures 99
Chapter Review Problems 102
Social Issues 107
Additional Reading 108
Chapter 3 Operating Systems 109
3.1 The Evolution of Operating Systems 110
3.2 Operating System Architecture 113
3.3 Coordinating the Machine's Activities 120
3.4 Handling Competition Among Processes 123
3.5 Security 127
Chapter Review Problems 129
Social Issues 132
Additional Reading 133
Chapter 4 Networking and the Internet 135
4.1 Network Fundamentals 136
4.2 The Internet 141
4.3 The World Wide Web 147
4.4 Network Protocols 156
4.5 Security 164
Chapter Review Problems 167
Social Issues 169
Additional Reading 170
Chapter 5 Algorithms 171
5.1 The Concept of an Algorithm 172
5.2 Algorithm Representation 175
5.3 Algorithm Discovery 182
5.4 Iterative Structures 188
5.5 Recursive Structures 199
5.6 Efficiency and Correctness 207
Chapter Review Problems 216
Social Issues 222
Additional Reading 223
Chapter 6 Programming Languages 225
6.1 Historical Perspective 226
6.2 Traditional Programming Concepts 235
6.3 Procedural Units 246
6.4 Language Implementation 254
6.5 Object-Oriented Programming 263
6.6 Programming Concurrent Activities 269
6.7 Declarative Programming 272
Chapter Review Problems 278
Social Issues 282
Additional Reading 283
Chapter 7 Software Engineering 285
7.1 The Software Engineering Discipline 286
7.2 The Software Life Cycle 288
7.3 Modularity 293
7.4 Design Methodologies 299
7.5 Tools of the Trade 303
7.6 Testing 308
7.7 Documentation 309
7.8 Software Ownership and Liability 311
Chapter Review Problems 313
Social Issues 316
Additional Reading 317
Chapter 8 Data Abstractions 319
8.1 Data Structure Fundamentals 320
8.2 Implernenting Data Structures 324
8.3 A Short Case Study 337
8.4 Customized Data Types 342
8.5 Classes and Objects 346
8.6 Pointers in Machine Language 348
Chapter Review Problems 350
Social Issues 355
Additional Reading 357
Chapter 9 Database Systems 359
9.1 Database Fundamentals 360
9.2 The Relational Model 364
9.3 Object-Oriented Databases 376
9.4 Maintaining Database Integrity 379
9.5 Traditional File Structures 382
9.6 Data Mining 391
9.7 Social Impact of Database Technology 393
Chapter Review Problems 395
Social Issues 400
Additional Reading 401
Chapter 10 Artificial Intelligence 403
10.1 Intelligence and Machines 404
10.2 Understanding Images 408
10.3 Reasoning 411
10.4 Artificial Neural Networks 423
10.5 Genetic Algorithms 434
10.6 Other Areas of Research 438
10.7 Considering the Consequences 446
Chapter Review Problems 448
Social Issues 453
Additional Reading 455
Chapter 11 Theory of Computation 457
11.1 Functions and Their Computation 458
11.2 Turing Machines 460
11.3 Universal Programming Languages 464
11.4 A Noncomputable Function 470
11.5 Complexity of Problems 476
11.6 Public Key Cryptography 485
Chapter Review Problems 489
Social Issues 493
Additional Reading 494
Appendixes 495
A ASCII 495
B Circuits to Manipulate Two's Complement Representations 497
C A Simple Machine Language 501
D High-Level Language Program Examples 503
E The Equivalence of Iterative and Recursive Structures 511
F Answers to Questions/Exercises 513
Index 550