Invitation to Computer Science

by Schneider,G.Michael

• ISBN13: 9780534419943
• ISBN10: 0534419941
• Format: Paperback
• Copyright: 2004-02-06
• Publisher: Cengage Learning

Summary

In this best-selling text, Mike Schneider and Judy Gersting unify and lend relevance to the topics of computer science within their proven framework of a six-layer hierarchy of abstractions. The authors begin by showing that computer science is the study of algorithms, which is the central theme of the book, then move up the next five levels of the hierarchy: hardware, virtual machine, software, applications, and ethics. Each layer in the hierarchy builds upon the ideas and concepts presented in earlier chapters. In addition to some motivational applications such as Web page design and interactive graphics, the book covers the fundamental issues of algorithms, hardware design, computer organization, system software, language models, theory of computation, and social and ethical issues of computing. Exposure to these deeper and more complex core ideas introduces students to the richness and beauty of the field and helps them appreciate the principles behind their creation and implementation. While feeling the excitement of computer science, students receive a solid grounding in the central concepts as well as in important uses of computing and information technology.

Table of Contents

An Introduction to Computer Science	1	(37)
Introduction	2	(2)
The Definition of Computer Science	4	(6)
Special Interest Box: Abu Ja far Muhammad ibn Musa Al-Khowavizmi (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	(14)
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	(3)
Special Interest Box: And the Verdict is ...	24	(1)
The Modern Era: 1950 to the Present	25	(1)
Special Interest Box: John Von Neumann (1903--1957)	25	(1)
Special Interest Box: Good Evening, This is Walter Cronkite	26	(2)
Special Interest Box: The World's First Microcomputer	28	(2)
Organization of the Text	30	(8)
Laboratory Experience 1	34	(1)
Exercises	35	(1)
Challenge Work	36	(1)
For Further Reading	36	(2)
LEVEL 1 The Algorithmic Foundations of Computer Science	38	(86)
Algorithm Discovery and Design	41	(36)
Introduction	42	(1)
Representing Algorithms	42	(12)
Pseudocode	42	(3)
Sequential Operations	45	(2)
Practice Problems	47	(1)
Conditional and Iterative Operations	48	(4)
Special Interest Box: From Little Primitives Mighty Algorithms Do Grow	52	(2)
Practice Problems	54	(1)
Examples of Algorithmic Problem Solving	54	(16)
Example 1: Looking, Looking, Looking	54	(4)
Laboratory Experience 2	58	(1)
Example 2: Big, Bigger, Biggest	58	(5)
Laboratory Experience 3	63	(1)
Practice Problems	64	(1)
Example 3: Meeting Your Match	64	(6)
Practice Problems	70	(1)
Conclusion	70	(7)
Exercises	72	(1)
Challenge Work	73	(2)
For Further Reading	75	(2)
The Efficiency of Algorithms	77	(47)
Introduction	78	(1)
Attributes of Algorithms	78	(5)
Practice Problem	82	(1)
Measuring Efficiency	83	(15)
Sequential Search	83	(2)
Order of Magnitude---Order n	85	(2)
Practice Problem	87	(1)
Selection Sort	87	(6)
Practice Problem	93	(1)
Order of Magnitude---Order n2	93	(3)
Special Interest Box: The Tortoise and the Hare	96	(1)
Laboratory Experience 4	97	(1)
Practice Problem	97	(1)
Analysis of Algorithms	98	(15)
Data Cleanup Algorithms	98	(6)
Practice Problem	104	(1)
Binary Search	105	(5)
Practice Problem	110	(1)
Laboratory Experience 5	111	(1)
Pattern Matching	111	(1)
Summary	112	(1)
Practice Problem	113	(1)
When Things Get Out of Hand	113	(5)
Laboratory Experience 6	117	(1)
Practice Problems	117	(1)
Summary of Level 1	118	(6)
Exercises	119	(3)
Challenge Work	122	(1)
For Further Reading	123	(1)
LEVEL 2 The Hardware World	124	(108)
The Building Blocks: Binary Numbers, Boolean Logic, and Gates	127	(56)
Introduction	128	(1)
The Binary Numbering System	129	(22)
Binary Representation of Numeric and Textual Information	129	(8)
Practice Problems	137	(1)
Binary Representation of Sound and Images	137	(7)
Practice Problems	144	(1)
The Reliability of Binary Representation	145	(1)
Binary Storage Devices	146	(5)
Special Interest Box: Dr. William Schockley (1910--1989)	151	(1)
Boolean Logic and Gates	151	(7)
Boolean Logic	151	(1)
Special Interest Box: George Boole (1815--1864)	152	(2)
Practice Problems	154	(1)
Gates	155	(3)
Building Computer Circuits	158	(15)
Introduction	158	(2)
A Circuit Construction Algorithm	160	(4)
Laboratory Experience 7	164	(1)
Practice Problems	164	(1)
Examples of Circuit Design and Construction	165	(7)
Practice Problems	172	(1)
Laboratory Experience 8	172	(1)
Summary	173	(1)
Control Circuits	173	(4)
Conclusion	177	(6)
Exercises	179	(1)
Challenge Work	180	(1)
For Further Reading	181	(2)
Computer Systems Organization	183	(49)
Introduction	184	(2)
The Components of a Computer System	186	(29)
Memory and Cache	188	(3)
Special Interest Box: Powers of 10	191	(7)
Practice Problems	198	(1)
Input/Output and Mass Storage	198	(5)
Practice Problems	203	(1)
The Arithmetic/Logic Unit	203	(3)
The Control Unit	206	(7)
Practice Problems	213	(2)
Putting All the Pieces Together---the Von Neumann Architecture	215	(6)
Special Interest Box: An Alphabet Soup of Speed Measures---MIPS, MFLOPS, MHz, and GHz	220	(1)
Laboratory Experience 9	221	(1)
The Future: Non--Von Neumann Architectures	221	(6)
Special Interest Box: Speed to Burn	226	(1)
Summary of Level 2	227	(5)
Exercises	229	(1)
Challenge Work	230	(1)
For Further Reading	231	(1)
LEVEL 3 The Virtual Machine	232	(102)
An Introduction to System Software and Virtual Machines	235	(52)
Introduction	236	(2)
System Software	238	(3)
The Virtual Machine	238	(1)
Types of System Software	239	(2)
Assemblers and Assembly Language	241	(19)
Assembly Language	241	(7)
Practice Problems	248	(1)
Examples of Assembly Language Code	248	(4)
Laboratory Experience 10	252	(1)
Practice Problems	253	(1)
Translation and Loading	253	(6)
Practice Problems	259	(1)
Operating Systems	260	(27)
Functions of an Operating System	260	(4)
Special Interest Box: A Machine for the Rest of Us	264	(2)
Special Interest Box: Hackers	266	(1)
Practice Problem	267	(3)
Special Interest Box: The Open Source Movement	270	(1)
Historical Overview of Operating Systems Development	271	(8)
The Future	279	(3)
Exercises	282	(2)
Challenge Work	284	(1)
For Further Reading	285	(2)
Computer Networks, the Internet, and the World Wide Web	287	(47)
Introduction	288	(1)
Basic Networking Concepts	289	(13)
Communication Links	289	(4)
Special Interest Box: Ubiquitous Computing	293	(1)
Practice Problems	294	(1)
Local Area Networks	294	(3)
Practice Problems	297	(1)
Wide Area Networks	298	(1)
Overall Structure of the Internet	299	(3)
Communication Protocols	302	(17)
Physical Layer	304	(1)
Data Link Layer	304	(4)
Practice Problems	308	(1)
Network Layer	308	(4)
Transport Layer	312	(1)
Practice Problems	312	(4)
Application Layer	316	(2)
Laboratory Experience 11	318	(1)
Network Services and Benefits	319	(3)
Special Interest Box: Spam	320	(2)
A Brief History of the Internet and the World Wide Web	322	(7)
The Internet	323	(4)
Special Interest Box: Geography Lesson	327	(1)
The World Wide Web	327	(2)
Conclusion	329	(1)
Summary of Level 3	329	(5)
Exercises	331	(1)
Challenge Work	332	(1)
For Further Reading	333	(1)
LEVEL 4 The Software World	334	(230)
Introduction to High-Level Language Programming	337	(96)
Where Do We Stand?	338	(1)
High-level Languages	339	(3)
Introduction to Java	342	(3)
A Simple Java Program	342	(1)
Special Interest Box: Java Is Born	343	(2)
Running a Java Program	345	(1)
Virtual Data Storage	345	(5)
Practice Problems	349	(1)
Statement Types	350	(24)
Input Statements	350	(1)
Special Interest Box: The Console Class	351	(2)
Practice Problem	353	(1)
Output Statements	353	(1)
Practice Problems	354	(1)
The Assignment Statement	354	(4)
Practice Problems	358	(1)
Control Statements	358	(12)
Practice Problems	370	(1)
Another Example	371	(3)
Laboratory Experience 12	374	(1)
Practice Problems	374	(1)
Meeting Expectations	374	(4)
Managing Complexity	378	(12)
Special Interest Box: Which Java?	379	(1)
Divide and Conquer	379	(1)
Using Methods	380	(3)
Writing Methods	383	(5)
Laboratory Experience 13	388	(1)
Practice Problems	389	(1)
Object-oriented Programming	390	(14)
What Is It?	390	(3)
Java and OOP	393	(5)
One More Example	398	(4)
What Have We Gained?	402	(2)
Practice Problems	404	(1)
Graphical Programming	404	(12)
Graphics Hardware	405	(1)
Graphics Software	406	(10)
Practice Problem	416	(1)
Laboratory Experience 14	416	(1)
The Big Picture: Software Engineering	416	(8)
Scaling Up	417	(2)
Special Interest Box: Vital Statistics for Real Code	419	(1)
The Software Life Cycle	419	(5)
Modern Environments	424	(1)
Conclusion	424	(9)
Exercises	426	(3)
Challenge Work	429	(1)
For Further Reading	430	(3)
The Tower of Babel	433	(44)
Why Babel?	434	(1)
Procedural Languages	435	(13)
Fortran	436	(2)
Special Interest Box: Old Dog, New Tricks #1	438	(1)
Practice Problem	438	(1)
Cobol	438	(2)
Practice Problem	440	(1)
C/C++	440	(4)
Practice Problems	444	(1)
Ada	444	(1)
Practice Problem	445	(1)
C# and .NET	446	(1)
Special Interest Box: Old Dog, New Tricks #2	446	(1)
Practice Problem	447	(1)
Special-purpose Languages	448	(6)
SQL	448	(1)
HTML	449	(2)
Special Interest Box: Beyond HTML	451	(1)
Laboratory Experience 15	451	(1)
JavaScript	451	(3)
Practice Problems	454	(1)
Alternative Programming Paradigms	454	(17)
Functional Programming	455	(5)
Special Interest Box: Simplicity Is in the Eye of the Beholder	460	(1)
Laboratory Experience 16	460	(1)
Practice Problems	460	(1)
Logic Programming	461	(5)
Practice Problems	466	(1)
Parallel Programming	467	(3)
Practice Problem	470	(1)
Conclusion	471	(6)
Exercises	473	(2)
Challenge Work	475	(1)
For Further Reading	476	(1)
Compilers and Language Translation	477	(46)
Introduction	478	(3)
The Compilation Process	481	(35)
Phase I: Lexical Analysis	482	(3)
Practice Problems	485	(1)
Phase II: Parsing	485	(6)
Practice Problems	491	(10)
Practice Problems	501	(1)
Phase III: Semantics and Code Generation	502	(7)
Laboratory Experience 17	509	(1)
Practice Problem	509	(2)
Phase IV: Code Optimization	511	(4)
Special Interest Box: ``I Do Not Understand,'' Said the Machine	515	(1)
Conclusion	516	(7)
Exercises	518	(2)
Challenge Work	520	(1)
For Further Reading	521	(2)
Models of Computation	523	(41)
Introduction	524	(1)
What Is a Model?	525	(1)
Practice Problems	526	(1)
A Model of a Computing Agent	526	(9)
Properties of a Computing Agent	526	(2)
The Turing Machine	528	(1)
Special Interest Box: Alan Turing, Brilliant Eccentric	528	(6)
Practice Problems	534	(1)
A Model of an Algorithm	535	(3)
Turing Machine Examples	538	(10)
A Bit Inverter	538	(2)
A Parity Bit Machine	540	(3)
Machines for Unary Incrementing	543	(3)
A Unary Addition Machine	546	(2)
Practice Problems	548	(1)
Laboratory Experience 18	548	(1)
The Church-Turing Thesis	548	(3)
Special Interest Box: The Turing Award	549	(2)
Unsolvable Problems	551	(6)
Special Interest Box: Couldn't Do, Can't Do, Never Will Be Able to. . .	556	(1)
Practice Problems	557	(1)
Laboratory Experience 19	557	(1)
Conclusion	557	(1)
Summary of Level 4	558	(6)
Exercises	560	(2)
Challenge Work	562	(1)
For Further Reading	563	(1)
LEVEL 5 Applications	564	(92)
Simulation and Modeling	567	(26)
Introduction	568	(1)
Computational Modeling	568	(13)
Introduction to Systems and Models	568	(3)
Computational Models, Accuracy, and Errors	571	(2)
An Example of Model Building	573	(8)
Laboratory Experience 20	581	(1)
Running the Model and Visualizing Results	581	(8)
Special Interest Box: The Mother of All Computations!	588	(1)
Conclusion	589	(4)
Exercises	590	(1)
Challenge Work	591	(1)
For Further Reading	592	(1)
Electronic Commerce and Information Security	593	(34)
Introduction	594	(2)
Special Interest Box: Shopping on the Web	595	(1)
E-Commerce	596	(10)
The Vision Thing	596	(1)
Decisions, Decisions	596	(2)
Anatomy of a Transaction	598	(2)
Special Interest Box: A Rose by Any Other Name	600	(3)
Designing Your Website	603	(2)
Behind the Scenes	605	(1)
Special Interest Box: The Price of Success	606	(1)
Practice Problem	606	(1)
Databases	606	(9)
Data Organization	607	(1)
Database Management Systems	608	(5)
Other Considerations	613	(1)
Laboratory Experience 21	614	(1)
Practice Problems	614	(1)
Information Security	615	(9)
Encryption Overview	615	(1)
Simple Encryption Algorithms	616	(3)
Practice Problems	619	(1)
Laboratory Experience 22	619	(1)
Des	619	(3)
Special Interest Box: Cracking Des	622	(1)
Public-Key Systems	622	(2)
Conclusion	624	(3)
Exercises	625	(1)
Challenge Work	625	(1)
For Further Reading	626	(1)
Artificial Intelligence	627	(29)
Introduction	628	(2)
Special Interest Box: To Whom Am I Speaking?	629	(1)
A Division of Labor	630	(2)
Knowledge Representation	632	(3)
Practice Problem	635	(1)
Recognition Tasks	635	(6)
Special Interest Box: Read Me a Story	640	(1)
Laboratory Experience 23	641	(1)
Practice Problem	641	(1)
Reasoning Tasks	641	(9)
Intelligent Searching	642	(2)
Special Interest Box: The Chess Challenge	644	(1)
Swarm Intelligence	645	(1)
Intelligent Agents	645	(2)
Expert Systems	647	(3)
Practice Problems	650	(1)
Conclusion	650	(1)
Summary of Level 5	650	(6)
Exercises	651	(1)
Challenge Work	652	(3)
For Further Reading	655	(1)
LEVEL 6 Social Issues in Computing	656	(29)
Making Decisions about Computers, Information, and Society	659	(26)
Introduction	660	(1)
Case Studies	660	(21)
Case 1: The Story of MP3---Compression Codes, Musicians, and Money	660	(6)
Practice Problems	666	(1)
Case 2: PGP: The U.S. Government vs. Phil Zimmerman	667	(4)
Practice Problems	671	(1)
Special Interest Box: The Cyborg	671	(1)
Case 3: Hackers: Public Enemies or Gadflies?	672	(3)
Practice Problems	675	(1)
Thinking Straight about Technology and Ethics	676	(1)
Case 4: Genetic Information and Medical Research	676	(5)
What We Covered and What We Did Not	681	(1)
Summary of Level 6	681	(4)
Exercises	682	(1)
For Further Reading	683	(2)
Appendix	685	(2)
Answers to Practice Problems	687	(24)
Index	711