An Introduction to Computer Science | p. 1 |
Introduction | p. 2 |
The Definition of Computer Science | p. 4 |
Special Interest Box: Abu Ja' far Muhammad ibn Musa Al-Khowarizmi (a.d. 780-850?) | p. 7 |
Special Interest Box: In the Beginning... | p. 9 |
Algorithms | p. 10 |
The Formal Definition of an Algorithm | p. 10 |
The Importance of Algorithmic Problem Solving | p. 15 |
Practice Problems | p. 16 |
A Brief History of Computing | p. 16 |
The Early Period: Up to 1940 | p. 16 |
Special Interest Box: The Original "Technophobia" | p. 19 |
Special Interest Box: Charles Babbage (1791-1871) Ada Augusta Byron, Countess of Lovelace (1815-1852) | p. 20 |
The Birth of Computers: 1940-1950 | p. 21 |
Special Interest Box: And the Verdict Is... | p. 23 |
Special Interest Box: John Von Neumann (1903-1957) | p. 24 |
The Modem Era: 1950 to the Present | p. 25 |
Special Interest Box: Good Evening, This Is Walter Cronkite | p. 26 |
Special Interest Box: The World's First Microcomputer | p. 27 |
Organization of the Text | p. 28 |
p. 33 | |
Exercises | p. 34 |
Challenge Work | p. 35 |
For Further Reading | p. 35 |
The Algorithmic Foundations of Computer Science | p. 36 |
Algorithm Discovery and Design | p. 39 |
Introduction | p. 40 |
Representing Algorithms | p. 40 |
Pseudocode | p. 40 |
Sequential Operations | p. 43 |
Practice Problems | p. 45 |
Conditional and Iterative Operations | p. 46 |
Special Interest Box: From Little Primitives Mighty Algorithms Do Grow | p. 53 |
Practice Problems | p. 54 |
Examples of Algorithmic Problem Solving | p. 54 |
Example 1: Go Forth and Multiply | p. 54 |
Practice Problems | p. 57 |
Example 2: Looking, Looking, Looking | p. 57 |
p. 61 | |
Example 3: Big, Bigger, Biggest | p. 62 |
Practice Problems | p. 66 |
p. 67 | |
Example 4: Meeting Your Match | p. 67 |
Practice Problems | p. 73 |
Conclusion | p. 73 |
Exercises | p. 75 |
Challenge Work | p. 77 |
For Further Reading | p. 78 |
The Efficiency of Algorithms | p. 79 |
Introduction | p. 80 |
Attributes of Algorithms | p. 80 |
Practice Problems | p. 84 |
Measuring Efficiency | p. 84 |
Sequential Search | p. 84 |
Order of Magnitude-Order n | p. 86 |
Practice Problem | p. 88 |
Selection Sort | p. 88 |
Practice Problem | p. 94 |
Order of Magnitude-Order n[superscript 2] | p. 94 |
Special Interest Box: The Tortoise and the Hare | p. 97 |
Practice Problem | p. 98 |
p. 98 | |
Analysis of Algorithms | p. 99 |
Data Cleanup Algorithms | p. 99 |
Practice Problems | p. 105 |
Binary Search | p. 106 |
Practice Problem | p. 111 |
p. 111 | |
Pattern Matching | p. 112 |
Summary | p. 113 |
Practice Problem | p. 113 |
When Things Get Out of Hand | p. 113 |
Practice Problems | p. 117 |
p. 118 | |
Summary of Level 1 | p. 118 |
Exercises | p. 120 |
Challenge Work | p. 124 |
For Further Reading | p. 125 |
The Hardware World | p. 126 |
The Building Blocks: Binary Numbers, Boolean Logic, and Gates | p. 129 |
Introduction | p. 130 |
The Binary Numbering System | p. 130 |
Binary Representation of Numeric and Textual Information | p. 130 |
Practice Problems | p. 142 |
Binary Representation of Sound and Images | p. 142 |
The Reliability of Binary Representation | p. 149 |
Practice Problems | p. 150 |
Binary Storage Devices | p. 151 |
Boolean Logic and Gates | p. 156 |
Boolean Logic | p. 156 |
Special Interest Box: Dr. William Shockley (1910-1989) | p. 156 |
Special Interest Box: George Boole (1815-1864) | p. 157 |
Practice Problems | p. 159 |
Gates | p. 160 |
Building Computer Circuits | p. 162 |
Introduction | p. 162 |
A Circuit Construction Algorithm | p. 165 |
Practice Problems | p. 169 |
p. 170 | |
Examples of Circuit Design and Construction | p. 170 |
Practice Problems | p. 178 |
p. 178 | |
Control Circuits | p. 179 |
Conclusion | p. 182 |
Exercises | p. 184 |
Challenge Work | p. 185 |
For Further Reading | p. 186 |
Computer Systems Organization | p. 187 |
Introduction | p. 188 |
The Components of a Computer System | p. 190 |
Memory and Cache | p. 192 |
Special Interest Box: Powers of 10 | p. 195 |
Practice Problems | p. 201 |
Input/Output and Mass Storage | p. 202 |
Practice Problems | p. 207 |
The Arithmetic/Logic Unit | p. 207 |
The Control Unit | p. 211 |
Practice Problems | p. 215 |
Putting All the Pieces Together | p. 219 |
Special Interest Box: An Alphabet Soup of Speed Measures | p. 224 |
p. 224 | |
Non | p. 225 |
Special Interest Box: Speed to Burn | p. 229 |
Summary of Level 2 | p. 231 |
Special Interest Box: Quantum Computing | p. 231 |
Exercises | p. 233 |
Challenge Work | p. 234 |
For Further Reading | p. 235 |
The Virtual Machine | p. 236 |
An Introduction to System Software and Virtual Machines | p. 239 |
Introduction | p. 240 |
System Software | p. 241 |
The Virtual Machine | p. 241 |
Types of System Software | p. 243 |
Assemblers and Assembly Language | p. 245 |
Assembly Language | p. 245 |
Practice Problems | p. 251 |
Examples of Assembly Language Code | p. 252 |
Practice Problems | p. 256 |
p. 256 | |
Translation and Loading | p. 257 |
Practice Problems | p. 261 |
Operating Systems | p. 263 |
Functions of an Operating System | p. 264 |
Special Interest Box: A Machine for the Rest of Us | p. 266 |
Special Interest Box: Hackers | p. 269 |
Practice Problem | p. 270 |
Special Interest Box: The Open Source Movement | p. 273 |
Historical Overview of Operating Systems Development | p. 273 |
Special Interest Box: Now That's Big! | p. 274 |
The Future | p. 282 |
Exercises | p. 285 |
Challenge Work | p. 287 |
For Further Reading | p. 287 |
Computer Networks, the Internet, and the World Wide Web | p. 289 |
Introduction | p. 290 |
Basic Networking Concepts | p. 291 |
Communication Links | p. 291 |
Special Interest Box: Blogs | p. 291 |
Practice Problems | p. 296 |
Special Interest Box: Ubiquitous Computing | p. 297 |
Local Area Networks | p. 297 |
Practice Problems | p. 300 |
Wide Area Networks | p. 300 |
Overall Structure of the Internet | p. 302 |
Communication Protocols | p. 304 |
Physical Layer | p. 306 |
Data Link Layer | p. 307 |
Practice Problems | p. 310 |
Network Layer | p. 311 |
Practice Problems | p. 313 |
Transport Layer | p. 314 |
Application Layer | p. 317 |
p. 321 | |
Network Services and Benefits | p. 321 |
Special Interest Box: Spam | p. 322 |
A Brief History of the Internet and the World Wide Web | p. 324 |
The Internet | p. 324 |
The World Wide Web | p. 328 |
Special Interest Box: Geography Lesson | p. 328 |
Conclusion | p. 330 |
Summary of Level 3 | p. 330 |
Exercises | p. 332 |
Challenge Work | p. 333 |
For Further Reading | p. 333 |
The Software World | p. 334 |
Introduction to High-level Language Programming | p. 337 |
Where Do We Stand? | p. 338 |
High-level Languages | p. 339 |
Introduction to C++ | p. 342 |
Special Interest Box: A Remarkable History | p. 344 |
Virtual Data Storage | p. 345 |
Practice Problems | p. 349 |
Statement Types | p. 349 |
Input/Output Statements | p. 350 |
Practice Problems | p. 354 |
The Assignment Statement | p. 354 |
Practice Problems | p. 357 |
Control Statements | p. 357 |
Practice Problems | p. 369 |
Putting the Pieces Together | p. 370 |
The Complete Program | p. 370 |
Meeting Expectations | p. 370 |
Practice Problems | p. 374 |
p. 374 | |
Managing Complexity | p. 375 |
Divide and Conquer | p. 375 |
Using Functions | p. 376 |
Writing Functions | p. 378 |
Special Interest Box: Whither Art Thou, C++? | p. 379 |
Practice Problems | p. 388 |
p. 389 | |
Object-Oriented Programming | p. 389 |
A C++ Example | p. 391 |
What Have We Gained? | p. 396 |
Practice Problems | p. 397 |
Graphical Programming | p. 397 |
Graphics Primitives | p. 398 |
Practice Problem | p. 405 |
p. 406 | |
An Example of Graphics Programming | p. 406 |
The Big Picture: Software Engineering | p. 408 |
Scaling Up | p. 409 |
pecial Interest Box: Vital Statistics for Real Code | p. 411 |
The Software Life Cycle | p. 412 |
Modern Environments | p. 417 |
Conclusion | p. 417 |
Exercises | p. 419 |
Challenge Work | p. 421 |
For Further Reading | p. 422 |
The Tower of Babel | p. 425 |
Why Babel? | p. 426 |
Procedural Languages | p. 427 |
Fortran | p. 428 |
Special Interest Box: Old Dog, New Tricks #1 | p. 430 |
Practice Problem | p. 430 |
Cobol | p. 430 |
Practice Problem | p. 432 |
C | p. 432 |
Practice Problems | p. 435 |
Ada | p. 435 |
Practice Problem | p. 436 |
Java | p. 436 |
Practice Problem | p. 438 |
C# and .Net | p. 438 |
Special Interest Box: Old Dog, New Tricks #2 | p. 439 |
Practice Problem | p. 440 |
Special-purpose Languages | p. 440 |
SQL | p. 440 |
HTML | p. 441 |
p. 443 | |
Special Interest Box: Beyond HTML | p. 444 |
JavaScript | p. 444 |
Practice Problem | p. 446 |
Special Interest Box: PHP | p. 446 |
Alternative Programming Paradigms | p. 447 |
Functional Programming | p. 448 |
Special Interest Box: Simplicity Is in the Eye of the Beholder | p. 452 |
Practice Problems | p. 453 |
p. 453 | |
Logic Programming | p. 453 |
Practice Problems | p. 458 |
Parallel Programming | p. 458 |
Practice Problem | p. 462 |
Conclusion | p. 462 |
Special Interest Box: Parallel Computing with Titanium | p. 462 |
Exercises | p. 465 |
Challenge Work | p. 467 |
For Further Reading | p. 468 |
Compilers and Language Translation | p. 469 |
Introduction | p. 470 |
The Compilation Process | p. 473 |
Phase I: Lexical Analysis | p. 474 |
Practice Problem | p. 477 |
Phase II: Parsing | p. 477 |
Practice Problems | p. 483 |
Practice Problems | p. 493 |
Phase III: Semantics and Code Generation | p. 494 |
Practice Problem | p. 503 |
Phase IV: Code Optimization | p. 503 |
p. 503 | |
Special Interest Box: "I Do Not Understand," Said the Machine | p. 508 |
Conclusion | p. 509 |
Exercises | p. 510 |
Challenge Work | p. 512 |
For Further Reading | p. 513 |
Models of Computation | p. 515 |
Introduction | p. 516 |
What Is a Model? | p. 516 |
Practice Problems | p. 518 |
A Model of a Computing Agent | p. 518 |
Properties of a Computing Agent | p. 518 |
The Turing Machine | p. 519 |
Special Interest Box: Alan Turing, Brilliant Eccentric | p. 520 |
Practice Problems | p. 526 |
A Model of an Algorithm | p. 527 |
Turing Machine Examples | p. 530 |
A Bit Inverter | p. 530 |
A Parity Bit Machine | p. 532 |
Machines for Unary Incrementing | p. 535 |
A Unary Addition Machine | p. 538 |
Practice Problems | p. 540 |
p. 540 | |
The Church-Turing Thesis | p. 540 |
Special Interest Box: The Turing Award | p. 541 |
Unsolvable Problems | p. 543 |
Special Interest Box: Couldn't Do, Can't Do, Never Will Be Able to... | p. 548 |
Practice Problems | p. 548 |
p. 548 | |
Conclusion | p. 549 |
Summary of Level 4 | p. 549 |
Exercises | p. 551 |
Challenge Work | p. 553 |
For Further Reading | p. 555 |
Applications | p. 556 |
Simulation and Modeling | p. 559 |
Introduction | p. 560 |
Computational Modeling | p. 560 |
Introduction to Systems and Models | p. 560 |
Computational Models, Accuracy, and Errors | p. 562 |
An Example of Model Building | p. 565 |
Practice Problems | p. 572 |
p. 573 | |
Running the Model and Visualizing Results | p. 573 |
Conclusion | p. 580 |
Special Interest Box: The Mother of all Computations! | p. 581 |
Exercises | p. 582 |
Challenge Work | p. 583 |
For Further Reading | p. 584 |
Electronic Commerce and Information Security | p. 585 |
Introduction | p. 586 |
Special Interest Box: Shopping on the Web | p. 587 |
E-commerce | p. 588 |
The Vision Thing | p. 588 |
Decisions, Decisions | p. 589 |
Anatomy of a Transaction | p. 590 |
Special Interest Box: A Rose by Any Other Name... | p. 592 |
Special Interest Box: Gone Phishin' | p. 595 |
Designing Your Web Site | p. 595 |
Behind the Scenes | p. 597 |
Special Interest Box: The Price of Success | p. 598 |
Practice Problem | p. 598 |
Databases | p. 598 |
Data Organization | p. 599 |
Database Management Systems | p. 600 |
Other Considerations | p. 604 |
p. 605 | |
Practice Problems | p. 606 |
Information Security | p. 606 |
Encryption Overview | p. 607 |
Simple Encryption Algorithms | p. 608 |
Practice Problems | p. 610 |
DES | p. 610 |
p. 611 | |
Special Interest Box: Cracking DES | p. 612 |
Public-Key Systems | p. 614 |
Practice Problem | p. 616 |
Conclusion | p. 616 |
Exercises | p. 617 |
Challenge Work | p. 617 |
For Further Reading | p. 618 |
Artificial Intelligence | p. 619 |
Introduction | p. 620 |
Special Interest Box: To Whom Am I Speaking? | p. 621 |
A Division of Labor | p. 621 |
Knowledge Representation | p. 624 |
Practice Problem | p. 627 |
Recognition Tasks | p. 627 |
Special Interest Box: Read Me a Story | p. 632 |
p. 632 | |
Practice Problem | p. 633 |
Reasoning Tasks | p. 633 |
Intelligent Searching | p. 633 |
Swarm Intelligence | p. 635 |
Special Interest Box: The Chess Challenge | p. 636 |
Intelligent Agents | p. 637 |
Special Interest Box: Ants in Space! | p. 637 |
Expert Systems | p. 639 |
Practice Problems | p. 642 |
Robotics | p. 642 |
Conclusion | p. 643 |
Summary of Level 5 | p. 644 |
Special Interest Box: Shall We Dance? | p. 644 |
Exercises | p. 645 |
Challenge Work | p. 646 |
For Further Reading | p. 649 |
Social Issues in Computing | p. 650 |
Making Decisions about Computers, Information, and Society | p. 653 |
Introduction | p. 654 |
Case Studies | p. 654 |
Case 1: The Story of MP3-Compression Codes, Musicians, and Money | p. 654 |
Practice Problems | p. 660 |
Special Interest Box: The Sound of Music | p. 661 |
Case 2: PGP: The U.S. Government vs. Phil Zimmermann | p. 661 |
Case 3: Hackers: Public Enemies or Gadflies? | p. 665 |
Practice Problems | p. 666 |
Special Interest Box: The Cyborg | p. 667 |
Practice Problems | p. 670 |
Thinking Straight about Technology and Ethics | p. 670 |
Case 4: Genetic Information and Medical Research | p. 671 |
What We Covered and What We Did Not | p. 675 |
Summary of Level 6 | p. 676 |
Exercises | p. 677 |
For Further Reading | p. 678 |
Answers to Practice Problems | p. 681 |
Index | p. 709 |
Table of Contents provided by Ingram. All Rights Reserved. |
The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.
The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.