Foundations of Computer Science : From Data Manipulation to Theory of Computation

by Forouzan, Behrouz A.

• ISBN13: 9780534391430
• ISBN10: 0534391435
• Format: Paperback
• Copyright: 2002-05-06
• Publisher: Course Technology

Summary

This text successfully addresses the need to provide students with an overview of the many disciplines within computer science. BehrouzForouzan has developed a five-part approach to introduce students to different aspects of the discipline without overwhelming them withtechnical detail.

Table of Contents

PART I COMPUTER AND DATA	1	(68)
Introduction	2	(12)
The Computer as a Black Box	3	(2)
Data Processor	3	(1)
Programmable Data Processor	3	(2)
von Neumann Model	5	(1)
Four Subsystems	5	(1)
Stored Program Concept	6	(1)
Sequential Execution of Instructions	6	(1)
Computer Hardware	6	(1)
Data	6	(1)
Storing Data	6	(1)
Organizing Data	7	(1)
Computer Software	7	(2)
Programs Must Be Stored	7	(1)
A Sequence of Instructions	7	(1)
Algorithms	8	(1)
Languages	8	(1)
Software Engineering	8	(1)
Operating Systems	8	(1)
History	9	(2)
Mechanical Machines (Before 1930)	9	(1)
Birth of Electronic Computers (1930--1950)	9	(2)
Key Terms	11	(1)
Summary	11	(1)
Practice Set	11	(3)
Data Representation	14	(13)
Data Types	15	(1)
Data inside the Computer	15	(2)
Bit	16	(1)
Bit Pattern	16	(1)
Byte	16	(1)
Representing Data	17	(4)
Text	17	(2)
Numbers	19	(1)
Images	19	(1)
Audio	20	(1)
Video	21	(1)
Hexadecimal Notation	21	(2)
Conversion	22	(1)
Octal Notation	23	(1)
Conversion	23	(1)
Key Terms	24	(1)
Summary	24	(1)
Practice Set	25	(2)
Number Representation	27	(23)
Decimal and Binary	28	(1)
Decimal System	28	(1)
Binary System	28	(1)
Conversion	29	(1)
Binary to Decimal Conversion	29	(1)
Decimal to Binary Conversion	29	(1)
Integer Representation	30	(10)
Unsigned Integers Format	31	(2)
Sign-and-Magnitude Format	33	(2)
One's Complement Format	35	(2)
Two's Complement Format	37	(2)
Summary of Integer Representation	39	(1)
Excess System	40	(1)
Floating-Point Representation	40	(4)
Converting to Binary	40	(2)
Normalization	42	(1)
Sign, Exponent, and Mantissa	42	(1)
IEEE Standards	42	(2)
Hexadecimal Notation	44	(1)
Key Terms	44	(1)
Summary	45	(1)
Practice Set	45	(5)
Operations on Bits	50	(19)
Arithmetic Operations	51	(4)
Arithmetic Operations on Integers	51	(3)
Arithmetic Operations on Floating-Point Numbers	54	(1)
Logical Operations	55	(8)
Truth Tables	56	(1)
Unary Operator	56	(1)
Binary Operators	57	(3)
Applications	60	(3)
Shift Operations	63	(1)
Key Terms	64	(1)
Summary	65	(1)
Practice Set	65	(4)
PART II COMPUTER HARDWARE	69	(52)
Computer Organization	70	(29)
Central Processing Unit (CPU)	71	(1)
Arithmetic Logic Unit (ALU)	71	(1)
Registers	71	(1)
Control Unit	72	(1)
Main Memory	72	(4)
Address Space	72	(2)
Memory Types	74	(1)
Memory Hierarchy	75	(1)
Cache Memory	75	(1)
Input/Output	76	(7)
Nonstorage Devices	76	(1)
Storage Devices	76	(7)
Subsystem Interconnection	83	(4)
Connecting CPU and Memory	83	(1)
Connecting I/O Devices	84	(2)
Addressing Input/Output Devices	86	(1)
Program Execution	87	(5)
Machine Cycle	87	(1)
A Machine Cycle Example	88	(1)
Input/Output Operation	89	(3)
Two Different Architectures	92	(1)
CISC	92	(1)
RISC	93	(1)
Key Terms	93	(1)
Summary	93	(1)
Practice Set	94	(5)
Computer Networks	99	(22)
Networks, Large and Small	100	(1)
Model and Protocol	100	(1)
OSI Model	100	(3)
Seven Layers	100	(1)
Functions of the Layers	101	(2)
Categories of Networks	103	(2)
Local Area Network (LAN)	103	(1)
Metropolitan Area Network (MAN)	104	(1)
Wide Area Network (WAN)	104	(1)
Connecting Devices	105	(4)
Repeaters	106	(1)
Bridges	107	(1)
Routers	108	(1)
Gateways	108	(1)
The Internet and TCP/IP	109	(7)
Physical and Data-Link Layers	110	(1)
Network Layer	110	(1)
Transport Layer	111	(1)
Application Layer	111	(5)
Key Terms	116	(1)
Summary	116	(1)
Practice Set	117	(4)
PART III COMPUTER SOFTWARE	121	(92)
Operating Systems	122	(19)
Definition	123	(1)
Evolution	123	(1)
Batch Systems	123	(1)
Time-Sharing Systems	123	(1)
Personal Systems	124	(1)
Parallel Systems	124	(1)
Distributed Systems	124	(1)
Components	124	(12)
Memory Manager	125	(4)
Process Manager	129	(6)
Device Manager	135	(1)
File Manager	135	(1)
User Interface	136	(1)
Popular Operating Systems	136	(1)
Windows 2000	136	(1)
UNIX	136	(1)
Linux	136	(1)
Key Terms	137	(1)
Summary	137	(1)
Practice Set	138	(3)
Algorithms	141	(25)
Concept	142	(3)
Informal Definition	142	(1)
Example	142	(2)
Defining Actions	144	(1)
Refinement	144	(1)
Generalization	144	(1)
Three Constructs	145	(1)
Sequence	146	(1)
Decision	146	(1)
Repetition	146	(1)
Algorithm Representation	146	(4)
Flowchart	146	(1)
Pseudocode	146	(4)
More Formal Definition	150	(1)
Ordered Set	150	(1)
Unambiguous Steps	150	(1)
Produce a Result	150	(1)
Terminate in a Finite Time	150	(1)
Subalgorithms	150	(2)
Structure Chart	152	(1)
Basic Algorithms	152	(8)
Summation	152	(1)
Product	152	(1)
Smallest and Largest	153	(1)
Sorting	153	(5)
Searching	158	(2)
Recursion	160	(2)
Iterative Definition	160	(1)
Recursive Definition	161	(1)
Key Terms	162	(1)
Summary	162	(1)
Practice Set	163	(3)
Programming Languages	166	(29)
Evolution	167	(2)
Machine Languages	167	(1)
Symbolic Languages	168	(1)
High-Level Languages	168	(1)
Natural Languages	169	(1)
Building a Program	169	(2)
Writing and Editing Programs	169	(1)
Compiling Programs	170	(1)
Linking Programs	170	(1)
Program Execution	171	(1)
Categories of Languages	171	(8)
Procedural (Imperative) Languages	172	(1)
Object-Oriented Languages	173	(2)
Functional Languages	175	(1)
Declarative (Logic) Languages	176	(1)
Special Languages	177	(2)
A Procedural Language: C	179	(10)
Identifiers	179	(1)
Data Types	179	(1)
Variables	180	(1)
Constants	181	(1)
Input and Output	182	(1)
Expressions	182	(1)
Statements	183	(1)
Functions	184	(2)
Selection	186	(1)
Repetition	187	(2)
Derived Data Types	189	(1)
Recursion	189	(1)
Key Terms	189	(1)
Summary	190	(1)
Practice Set	191	(4)
Software Engineering	195	(18)
Software Life Cycle	196	(2)
Analysis Phase	197	(1)
Design Phase	197	(1)
Implementation Phase	197	(1)
Testing Phase	198	(1)
Development Process Models	198	(2)
Waterfall Model	198	(1)
Incremental Model	199	(1)
Modularity	200	(2)
Tools	200	(1)
Coupling	200	(1)
Cohesion	201	(1)
Quality	202	(4)
Quality Defined	202	(1)
Quality Factors	203	(2)
The Quality Circle	205	(1)
Documentation	206	(1)
User Documentation	206	(1)
System Documentation	206	(1)
Documentation as an Ongoing Process	207	(1)
Key Terms	207	(1)
Summary	208	(1)
Practice Set	208	(5)
PART IV DATA ORGANIZATION	213	(76)
Data Structures	214	(13)
Arrays	215	(4)
Array Applications	217	(1)
Two-Dimensional Arrays	218	(1)
Records	219	(1)
Accessing Records	220	(1)
Linked Lists	220	(3)
Nodes	221	(1)
Pointers to Linked Lists	221	(1)
Operations on Linked Lists	221	(2)
Key Terms	223	(1)
Summary	224	(1)
Practice Set	224	(3)
Abstract Data Types	227	(29)
Background	228	(1)
Definition	228	(1)
Model for an Abstract Data Type	229	(1)
Operations on ADTs	229	(1)
Linear Lists	229	(3)
Operations on Linear Lists	230	(2)
Implementation of a General Linear List	232	(1)
Linear List Applications	232	(1)
Stacks	232	(3)
Operations on Stacks	233	(1)
Implementation of a Stack	234	(1)
Stack Applications	234	(1)
Queues	235	(2)
Operations on Queues	235	(2)
Implementation of a Queue	237	(1)
Queue Applications	237	(1)
Trees	237	(2)
Basic Tree Concepts	237	(2)
Operations on Trees	239	(1)
Binary Trees	239	(5)
Operations on Binary Trees	241	(2)
Implementation of a Binary Tree	243	(1)
Binary Tree Applications	243	(1)
Graphs	244	(5)
Terminology	244	(1)
Operations on Graphs	245	(2)
Implementation of a Graph	247	(1)
Graph Applications	248	(1)
Key Terms	249	(1)
Summary	249	(2)
Practice Set	251	(5)
File Structures	256	(14)
Access Methods	257	(1)
Sequential Access	257	(1)
Random Access	257	(1)
Sequential Files	257	(2)
Updating Sequential Files	258	(1)
Indexed Files	259	(2)
Inverted Files	260	(1)
Hashed Files	261	(4)
Hashing Methods	261	(2)
Collision	263	(2)
Text versus Binary	265	(1)
Text Files	265	(1)
Binary Files	266	(1)
Key Terms	266	(1)
Summary	266	(1)
Practice Set	267	(3)
Databases	270	(19)
Database Management System	271	(1)
Architecture	272	(1)
Internal Level	272	(1)
Conceptual Level	272	(1)
External Level	272	(1)
Database Models	273	(1)
Hierarchical Model	273	(1)
Network Model	273	(1)
Relational Model	274	(1)
Relational Model	274	(1)
Relation	274	(1)
Operations on Relations	275	(4)
Insert	275	(1)
Delete	275	(1)
Update	276	(1)
Select	276	(1)
Project	277	(1)
Join	277	(1)
Union	277	(1)
Intersection	278	(1)
Difference	278	(1)
Structured Query Language	279	(3)
Statements	279	(3)
Other Database Models	282	(1)
Distributed Databases	282	(1)
Object-Oriented Databases	282	(1)
Key Terms	283	(1)
Summary	283	(1)
Practice Set	284	(5)
PART V ADVANCED TOPICS	289	(46)
Data Compression	290	(16)
Lossless Compression	291	(7)
Run-Length Encoding	291	(1)
Huffman Coding	292	(2)
Lempel Ziv Encoding	294	(4)
Lossy Compression Methods	298	(5)
Image Compression: JPEG	298	(3)
Video Compression: MPEG	301	(2)
Key Terms	303	(1)
Summary	303	(1)
Practice Set	303	(3)
Security	306	(11)
Privacy	307	(1)
Authentication	307	(1)
Integrity	307	(1)
Nonrepudiation	307	(1)
Privacy	307	(4)
Encryption/Decryption	307	(4)
Privacy Using the Combination	311	(1)
Digital Signature	311	(3)
Signing the Whole Document	312	(1)
Signing the Digest	312	(2)
Key Terms	314	(1)
Summary	314	(1)
Practice Set	315	(2)
Theory of Computation	317	(18)
Simple Language	318	(3)
Increment Statement	318	(1)
Decrement Statement	318	(1)
Loop Statement	318	(1)
Power of the Simple Language	318	(3)
Conclusion	321	(1)
Turing Machine	321	(5)
Turing Machine Components	321	(2)
Simulation of Simple Language	323	(2)
Conclusion	325	(1)
Godel Numbers	326	(1)
Representing a Program	326	(1)
Interpreting a Number	327	(1)
Halting Problem	327	(2)
Halting Problem is not Solvable	328	(1)
Solvable and Unsolvable Problems	329	(2)
Unsolvable Problems	329	(1)
Solvable Problems	330	(1)
Key Terms	331	(1)
Summary	331	(1)
Practice Set	332	(3)
Appendix A ASCII Code	335	(4)
Appendix B Unicode	339	(4)
Alphabets	340	(1)
Symbols and Punctuation Marks	341	(1)
CJK Auxiliaries	341	(1)
CJK Unified Ideographs	341	(1)
Surrogates	342	(1)
Private Use	342	(1)
Miscellaneous Characters and Symbols	342	(1)
Appendix C Flowcharts	343	(7)
C.1 Auxiliary Symbols	344	(1)
Start and Stop	344	(1)
Flow Lines	345	(1)
Connectors	345	(1)
C.2 Main Symbols	345	(5)
Sequence Statements	345	(2)
Selection Statements	347	(1)
Looping Statements	348	(2)
Appendix D Pseudocode	350	(3)
D.1 Components	351	(2)
Algorithm Header	351	(1)
Purpose, Conditions, and Return	351	(1)
Statement Numbers	351	(1)
Statement Constructs	351	(1)
Sequence	352	(1)
Selection	352	(1)
Loop	352	(1)
Appendix E Structure Charts	353	(5)
E.1 Structure Chart Symbols	354	(2)
Function Symbol	354	(1)
Selection in Structure Charts	355	(1)
Loops in Structure Charts	355	(1)
Data Flows	356	(1)
Reading Structure Charts	356	(1)
Rules of Structure Charts	357	(1)
Appendix F Discrete Cosine Transform	358	(2)
F.1 Discrete Cosine Transform	359	(1)
F.2 Inverse Transform	359	(1)
Appendix G Acronyms	360	(1)
Glossary	361	(16)
Index	377