Invitation to Computer Science: Java Version » (3rd Edition)

G. Michael Schneider is Professor of Mathematics and Computer Science at Macalester College in St. Paul, Minnesota and a Visiting Professor of Computer Science at Columbia University in New York. His interests include parallel processing, computer networks, and computer science education. He has written textbooks on software development, data structures, computer organization, and a breadth-first overview of computer science and was a member of the committee that authored the ACM/IEEE Computing Curriculum 2001. He has received Fulbright Grants to teach and do computer science curriculum development in Mauritius, Malaysia, Nepal, and Mongolia.

Judith Gersting is a Professor of Computer Science at the University of Hawaii, Hilo. She is also the department chair and has written a number of college textbooks. Her areas of specialization include theoretical computer science and computer science education.

This new edition of Invitation to Computer Science follows the breadth-first guidelines recommended by CC2001 to teach computer science topics from the ground up. The authors begin by showing that computer science is the study of algorithms, the central theme of the book, then move up the next five levels of the hierarchy: hardware, virtual machine, software, applications, and ethics. Utilizing rich pedagogy and a consistently engaging writing style, Schneider and Gersting provide students with a solid grounding in theoretical concepts, as well as important applications of computing and information technology. A laboratory manual and accompanying software is available as an optional bundle with this text.

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