Invitation to Computer Science

by Schneider,G.Michael

• ISBN13: 9781423901433
• ISBN10: 1423901436
• Additional ISBN(s): 9781418836542
• Edition: 3rd
• Format: Paperback
• Copyright: 2006-02-03
• Publisher: Cengage Learning
• More Book Details

Summary

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.

Author Biography

G. Michael Schneider is a Professor of Computer Science at Macalester College Judith Gersting is Professor of Computer Science at the University of Hawaii, Hilo

Table of Contents

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 Modern 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
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-the Von Neumann Architecture	p. 219
Special Interest Box: An Alphabet Soup of Speed Measures-MIPS, MFLOPS, MHz, and GHz	p. 224
	p. 224
Non-Von Neumann Architectures	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 Java	p. 341
A Simple Java Program	p. 342
Special Interest Box: Java Is Born	p. 343
Running a Java Program	p. 345
Virtual Data Storage	p. 345
Practice Problems	p. 347
Statement Types	p. 348
Input Statements	p. 349
Special Interest Box: The Console Class	p. 349
Practice Problem	p. 351
Output Statements	p. 351
Practice Problems	p. 352
The Assignment Statement	p. 353
Practice Problems	p. 356
Control Statements	p. 356
Practice Problems	p. 366
Another Example	p. 368
Practice Problems	p. 370
	p. 371
Meeting Expectations	p. 371
Managing Complexity	p. 375
Divide and Conquer	p. 375
Special Interest Box: Which Java?	p. 375
Using Methods	p. 377
Writing Methods	p. 380
Practice Problems	p. 384
	p. 386
Object-Oriented Programming	p. 386
What Is It?	p. 386
Java and OOP	p. 388
One More Example	p. 393
What Have We Gained?	p. 397
Practice Problems	p. 399
Graphical Programming	p. 399
Graphics Hardware	p. 400
Graphics Software	p. 402
Practice Problem	p. 411
	p. 11
The Big Picture: Software Engineering	p. 412
Scaling Up	p. 412
The Software Life Cycle	p. 414
Special Interest Box: Vital Statistics for Real Code	p. 414
Modern Environments	p. 418
Conclusion	p. 419
Exercises	p. 420
Challenge Work	p. 423
For Further Reading	p. 424
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/C++	p. 432
Practice Problems	p. 435
Ada	p. 436
Practice Problem	p. 437
C# and .NET	p. 437
Practice Problem	p. 438
Special Interest Box: Old Dog, New Tricks #2	p. 439
Special-purpose Languages	p. 439
SQL	p. 439
HTML	p. 440
	p. 442
Special Interest Box: Beyond HTML	p. 442
JavaScript	p. 443
Practice Problems	p. 445
Special Interest Box: PHP	p. 445
Alternative Programming Paradigms	p. 446
Functional Programming	p. 446
Practice Problems	p. 451
Special Interest Box: Simplicity Is in the Eye of the Beholder	p. 451
	p. 452
Logic Programming	p. 452
Practice Problems	p. 457
Parallel Programming	p. 458
Practice Problem	p. 461
Conclusion	p. 461
Special Interest Box: Parallel Computing with Titanium	p. 461
Exercises	p. 464
Challenge Work	p. 466
For Further Reading	p. 467
Compilers and Language Translation	p. 469
Introduction	p. 470
The Compilation Process	p. 473
Phase I: Lexical Analysis	p. 474
Practice Problems	p. 477
Phase II: Parsing	p. 477
Practice Problems	p. 483
Practice Problems	p. 493
Phase III: Semantics and Code Generation	p. 494
Phase IV: Code Optimization	p. 503
	p. 503
Practice Problems	p. 503
Special Interest Box: "I Do Not Understand," Said the Machine	p. 508
Conclusion	p. 509
Exercises	p. 518
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
Appendix	p. 681
Answers to Practice Problems	p. 683
Index	p. 711
Table of Contents provided by Ingram. All Rights Reserved.