Computer Science Illuminated

Laying the Groundwork 3
Chapter 1 The Big Picture . . . . . . . . . . . . . . . . . . . . . . .3
The Information Layer 33
Chapter 2 Binary Values and Number Systems . . . . . .33
Chapter 3 Data Representation . . . . . . . . . . . . . . . . .51
The Hardware Layer 87
Chapter 4 Gates and Circuits . . . . . . . . . . . . . . . . . . .87
Chapter 5 Computing Components . . . . . . . . . . . . . .115
The Programming Layer 141
Chapter 6 Problem Solving and Program Design . . .141
Chapter 7 Low-Level Programming Languages . . . . .187
Chapter 8 High-Level Programming Languages . . . . .225
Chapter 9 Abstract Data Types and Algorithms . . . . .275
The Operating Systems Layer 319
Chapter 10 Operating Systems . . . . . . . . . . . . . . . . .319
Chapter 11 File Systems and Directories . . . . . . . . . .349
The Applications Layer 373
Chapter 12 Information Systems . . . . . . . . . . . . . . .373
Chapter 13 Artificial Intelligence . . . . . . . . . . . . . . . .399
Chapter 14 Simulation and Other Applications . . . . .431
The Communications Layer 455
Chapter 15 Networks . . . . . . . . . . . . . . . . . . . . . . .455
Chapter 16 The World Wide Web . . . . . . . . . . . . . . .479
In Conclusion 501
Chapter 17 Limitations of Computing . . . . . . . . . . . .501Laying the Groundwork
Chapter 1 The Big Picture . . . . . . . . . . . . . . . . . . .3
1.1 Computing Systems 4
Layers of a Computing System 4
Abstraction 7
1.2 The History of Computing 9
A Brief History of Computing Hardware 9
A Brief History of Computing Software 17
Predictions 23
1.3 Computing as a Tool and a Discipline 24
Summary 26
Ethical Issues: Microsoft Anti-Trust Case 27
Key Terms 28
Exercises 28
Thought Questions 31
The Information Layer
Chapter 2 Binary Values and Number Systems . .33
2.1 Number Categories 34
2.2 Natural Numbers 35
Positional Notation 35
Binary, Octal, and Hexadecimal 38
Arithmetic in Other Bases 39
Power of Two Number Systems 40
Converting From Base 10 to Other Bases 42
x ContentsBinary Values and Computers 43
Summary 45
Ethical Issues: The Digital Divide 45
Key Terms 46
Exercises 46
Thought Questions 49
Chapter 3 Data Representation . . . . . . . . . . . . . .51
3.1 Data and Computers 52
Analog and Digital Information 53
Binary Representations 55
3.2 Representing Numeric Data 57
Representing Negative Values 57
Representing Real Numbers 61
3.3 Representing Text 63
The ASCII Character Set 64
The Unicode Character Set 65
Text Compression 66
3.4 Representing Audio Information 70
Audio Formats 72
The MP3 Audio Format 73
3.5 Representing Images and Graphics 73
Representing Color 73
Digitized Images and Graphics 76
Vector Representation of Graphics 77
3.6 Representing Video 78
Video Codecs 78
Summary 79
Ethical Issues: Napster 79
Key Terms 80
Exercises 81
Thought Questions 85
Contents xiThe Hardware Layer
Chapter 4 Gates and Circuits . . . . . . . . . . . . . . .87
4.1 Computers and Electricity 88
4.2 Gates 90
NOT Gate 90
AND Gate 92
OR Gate 92
XOR Gate 93
NAND and NOR Gates 94
Review of Gate Processing 95
Gates with More Inputs 95
4.3 Constructing Gates 96
Transistors 96
4.4 Circuits 99
Combinational Circuits 99
Adders 102
Multiplexers 104
4.5 Circuits as Memory 106
4.6 Integrated Circuits 107
4.7 CPU Chips 108
Summary 108
Ethical Issues: E-mail Privacy 109
Key Terms 110
Exercises 110
Thought Questions 113
Chapter 5 Computing Components . . . . . . . . . .115
5.1 Individual Computer Components 116
5.2 Stored-Program Concept 119
von Neumann Architecture 119
The Fetch-Execute Cycle 124
RAM and ROM 126
Secondary Storage Devices 127
xii Contents5.3 Non-von Neumann Architectures 131
5.4 Interpreting Ads 133
Summary 134
Ethical Issues: Facial Recognition/Privacy 135
Key Terms 136
Exercises 136
Thought Questions 139
The Programming Layer
Chapter 6 Problem Solving and
Algorithm Design . . . . . . . . . . . . . . . . . . . . . . .141
6.1 Problem Solving 142
How to Solve Problems 143
Computer Problem-Solving 148
Following an Algorithm 149
Developing an Algorithm 151
6.2 Top-Down Design 151
A General Example 153
A Computer Example 155
Summary of Methodology 160
Testing the Algorithm 160
6.3 Object-Oriented Design 162
Object Orientation 163
Relationships between Classes 163
Object-Oriented Design Methodology 164
General Example 169
Computer Example 171
6.4 Imprtant Threads 176
Information Hiding 176
Abstraction 177
Naming Things 178
Programming Languages 179
Testing 179
Contents xiiiSummary 179
Ethical Issues: Plagiarism 180
Key Terms 181
Exercises 182
Thought Questions 185
Chapter 7 Low-Level Programming
Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . .187
7.1 Computer Operations 188
7.2 Levels of Abstraction 189
7.3 Machine Language 189
Pep/7: A Virtual Computer 190
7.4 A Program Example 198
Problem and Algorithm 198
A Program 199
An Alternate Program for the Same Algorithm 203
An Enhanced Version of “Hello” 204
7.5 Assembly Language 207
Pep/7 Assembly Language 207
7.6 Other Imprtant Threads 215
Testing 216
Summary 218
Ethical Issues: Software Piracy, Copyrighting 219
Key Terms 220
Exercises 220
Thought Questions 223
Chapter 8 High-Level Programming
Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . .225
8.1 Translation Process 226
Compilers 226
Interpreters 227
8.2 Programming Language Paradigms 228
8.3 Functionality of Imperative Languages 231
Boolean Expressions 232
Strong Typing 234
Input/Output Structures 239
Control Structures 240
Composite Data Types 257
8.4 Functionality of Object-Oriented Languages 261
Encapsulation 261
xiv ContentsInheritance 262
Polymorphism 262
Summary 264
Ethical Issues: Hacking 265
Key Terms 266
Exercises 266
Thought Questions 272
Chapter 9 Abstract Data Types
and Algorithms . . . . . . . . . . . . . . . . . . . . . . . . .275
9.1 Abstract Data Types 276
9.2 Implementation 277
Array-Based Implementations 277
Linked Implementation 279
9.3 Lists 282
Basic List Operations 282
Additional List Operations 287
9.4 Sorting 287
Selection Sort 288
Bubble Sort 290
Quicksort 291
9.5 Binary Search 295
9.6 Stacks and Queues 298
Stacks 298
Queues 300
Implementation 300
9.7 Trees 300
Binary Trees 302
Binary Search Trees 303
Other Operations 309
Graphs 310
9.8 Programming Libraries 310
Summary 311
Ethical Issues: Web Content 312
Key Terms 313
Exercises 313
Thought Questions 317
Contents xvThe Operating Systems Layer
Chapter 10 Operating Systems . . . . . . . . . . . . .319
10.1 Roles of an Operating System 320
Memory, Process, and CPU Management 322
Batch Processing 323
Timesharing 324
Other OS Factors 325
10.2 Memory Management 326
Single Contiguous Memory Management 327
Partition Memory Management 329
Paged Memory Management 331
10.3 Process Management 333
The Process States 333
The Process Control Block 334
10.4 CPU Scheduling 335
First-Come, First-Served 336
Shortest Job Next 337
Round Robin 337
Summary 339
Ethical Issues: Privacy Invasion 340
Key Terms 341
Exercises 342
Thought Questions 347
Chapter 11 File Systems and Directories . . . . . .349
11.1 File Systems 350
Text and Binary Files 351
File Types 352
File Operations 353
File Access 354
File Protection 356
11.2 Directories 357
Directory Trees 357
Path Names 359
xvi Contents11.3 Disk Scheduling 363
First-Come, First-Served Disk Scheduling 364
Shortest-Seek-Time-First Disk Scheduling 365
SCAN Disk Scheduling 365
Summary 366
Ethical Issues: Computer Viruses and Denial of Service 367
Key Terms 368
Exercises 368
Thought Questions 371
The Applications Layer
Chapter 12 Information Systems . . . . . . . . . . .373
12.1 Managing Information 374
12.2 Spreadsheets 375
Spreadsheet Formulas 377
Circular References 382
Spreadsheet Analysis 382
12.3 Database Management Systems 383
The Relational Model 384
Relationships 387
Structured Query Language 388
Database Design 390
Summary 392
Ethical Issues: Encryption 393
Key Terms 394
Exercises 394
Thought Questions 397
Chapter 13 Artificial Intelligence . . . . . . . . . . . .399
13.1 Thinking Machines 400
The Turing Test 401
Contents xviiAspects of AI 403
13.2 Knowledge Representation 403
Semantic Networks 404
Search Trees 406
13.3 Expert Systems 409
13.4 Neural Networks 412
Biological Neural Networks 412
Artificial Neural Networks 413
13.5 Natural Language Processing 415
Voice Synthesis 416
Voice Recognition 417
Natural Language Comprehension 418
13.6 Robotics 419
The Sense-Plan-Act Paradigm 420
Subsumption Architecture 421
Physical Components 422
Summary 424
Ethical Issues: Deep Linking 425
Key Terms 426
Exercises 426
Thought Questions 429
Chapter 14 Simulation and Other
Applications . . . . . . . . . . . . . . . . . . . . . . . . . . .431
14.1 What Is Simulation? 432
Complex Systems 432
Models 433
Constructing Models 433
Queuing Systems 435
Meteorological Models 438
Other Models 444
Computing Power Necessary 444
14.2 Graphics and Computer-Aided Design (CAD) 445
14.3 Embedded Systems 447
Summary 449
Ethical Issues: Online Gambling 449
Key Terms 450
Exercises 451
Thought Questions 452
xviii ContentsThe Communications Layer
Chapter 15 Networks . . . . . . . . . . . . . . . . . . . .455
15.1 Networking 456
Types of Networks 457
Internet Connections 459
Packet Switching 462
15.2 Open Systems and Protocols 463
Open Systems 463
Network Protocols 464
TCP/IP 465
High-Level Protocols 465
MIME Types 466
Firewalls 467
15.3 Network Addresses 468
Domain Name System 469
Summary 471
Ethical Issues: Cybersquatting 473
Key Terms 474
Exercises 475
Thought Questions 477
Chapter 16 The World Wide Web . . . . . . . . . . .479
16.1 Spinning the Web 480
16.2 HTML 482
Basic HTML Formatting 485
Images and Links 486
16.3 Interactive Web Pages 487
Java Applets 487
Java Server Pages 488
16.4 XML 489
Summary 493
Ethical Issues: Cookies 495
Key Terms 496
Exercises 496
Thought Questions 498
Contents xixIn Conclusion
Chapter 17 Limitations of Computing . . . . . . . .501
17.1 Hardware 502
Limits on Arithmetic 502
Limits on Communications 509
17.2 Software 510
Complexity of Software 511
Current Approaches to Software Quality 512
Notorious Software Errors 516
17.3 Problems 518
Comparing Algorithms 519
Turing Machines 525
Halting Problem 528
Classification of Algorithms 531
Summary 532
Ethical Issues: Licensing Computer Professionals 533
Key Terms 535
Exercises 535
Thought Questions 538
Answers to Selected Exercises 539
Glossary 603
Endnotes 631
Index 639
xx Contents

Other Core of CS Books
Download