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 10
0.5 An Outline of Our Study 11
0.6 Social Repercussions 13
Chapter 1 Data Storage 19
1.1 Bits and Their Storage 20
1.2 Main Memory 27
1.3 Mass Storage 30
1.4 Representing Information as Bit Patterns 37
1.5 The Binary System 44
1.6 Storing Integers 49
1.7 Storing Fractions 56
1.8 Data Compression 61
1.9 Communication Errors 66
Chapter 2 Data Manipulation 79
2.1 Computer Architecture 80
2.2 Machine Language 83
2.3 Program Execution 89
2.4 Arithmetic/ Logic Instructions 97
2.5 Communicating with Other Devices 102
2.6 Other Architectures 107
Chapter 3 Operating Systems 119
3.1 The History of Operating Systems 120
3.2 Operating System Architecture 124
3.3 Coordinating the Machine’s Activities 131
3.4 Handling Competition Among Processes 134
3.5 Security 139
Chapter 4 Networking and the Internet 147
4.1 Network Fundamentals 148
4.2 The Internet 157
4.3 The World Wide Web 164
4.4 Internet Protocols 174
4.5 Security 180
Chapter 5 Algorithms 195
5.1 The Concept of an Algorithm 196
5.2 Algorithm Representation 199
5.3 Algorithm Discovery 207
5.4 Iterative Structures 213
5.5 Recursive Structures 224
5.6 Efficiency and Correctness 233
Chapter 6 Programming Languages 251
6.1 Historical Perspective 252
6.2 Traditional Programming Concepts 261
6.3 Procedural Units 272
6.4 Language Implementation 280
6.5 Object-Oriented Programming 289
6.6 Programming Concurrent Activities 295
6.7 Declarative Programming 298
Chapter 7 Software Engineering 311
7.1 The Software Engineering Discipline 312
7.2 The Software Life Cycle 315
7.3 Software Engineering Methodologies 319
7.4 Modularity 321
7.5 Tools of the Trade 328
7.6 Testing 336
7.7 Documentation 338
7.8 Software Ownership and Liability 339
Chapter 8 Data Abstractions 349
8.1 Data Structure Fundamentals 350
8.2 Implementing Data Structures 355
8.3 A Short Case Study 370
8.4 Customized Data Types 375
8.5 Classes and Objects 379
8.6 Pointers in Machine Language 381
Chapter 9 Database Systems 391
9.1 Database Fundamentals 392
9.2 The Relational Model 397
9.3 Object-Oriented Databases 408
9.4 Maintaining Database Integrity 411
9.5 Iraditional File Structures 414
9.6 Data Mining 423
9.7 Social Impact of Database Technology 425
Chapter 10 Artificial Intelligence 435
10.1 Intelligence and Machines 436
10.2 Perception 441
10.3 Reasoning 447
10.4 Additional Areas of Research 460
10.5 Artificial Neural Networks 464
10.6 Robotics 473
10.7 Considering the Consequences 475
Chapter 11 Theory of Computation 485
11.1 Functions and Their Computation 486
11.2 Turing Machines 488
11.3 Universal Programming Languages 493
11.4 A Noncomputable Function 499
11.5 Complexity of Problems 504
11.6 Public-Key Cryptography 513
Appendixes 525
A ASCII 527
B Circuits to Manipulate Two’s Complement Representations 529
C A Simple Machine Language 533
D High-Level Language Program Examples 535
E The Equivalence of Iterative and Recursive Structures 543
F Answers to Questions & Exercises 545
Index 585