Invitation to Computer Science

by Schneider,G.Michael

• ISBN13: 9781418836535
• ISBN10: 1418836532
• Edition: 4th
• Format: Paperback
• Copyright: 2006-02-03
• Publisher: Cengage Learning

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.

Table of Contents

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