Part I COMPUTER AND DATAChapter 1 Introduction 1.1 The Computer as a Black Box Data Processor Programmable Data Processor 1.2 von Neumann Model Four Subsystems Stored Program Concept Sequential Execution of Instructions 1.3 Computer Hardware 1.4 Data Storing Data Organizing Data 1.5 Computer Software Programs Must Be Stored A Sequence of Instructions Algorithms Languages Software Engineering Operating Systems 1.6 History Mechanical Machines (Before 1930) Birth of Electronic Computers (1930—1950) 1.7 Key Terms 1.8 Summary 1.9 Practice SetChapter 2 Data Representation 2.1 Data Types 2.2 Data Inside the Computer Bit Bit Pattern Byte 2.3 Representing Data Text Numbers Images Audio Video 2.4 Hexadecimal Notation Conversion 2.5 Octal Notation Conversion 2.6 Key Terms 2.7 Summary 2.8 Practice SetChapter 3 Number Representation 3.1 Decimal and Binary Decimal System Binary System 3.2 Conversion Binary to Decimal Conversion Decimal to Binary Conversion 3.3 Integer Representation Unsigned Integers Format Sign-and-Magnitude Format One's Complement Format Two's Complement Format Summary of Integer Representation 3.4 Excess System 3.5 Floating-Point Representation Converting to Binary Normalization Sign, Exponent, and Mantissa IEEE Standards 3.6 Hexadecimal Notation 3.7 Key Terms 3.8 Summary 3.9 Practice SetChapter 4 Operations on Bits 4.1 Arithmetic Operations Arithmetic Operations on Integers Arithmetic Operations on Floating-Point Numbers 4.2 Logical Operations Truth Tables Unary Operator Binary Operators Applications 4.3 Shift Operations 4.4 Key Terms 4.5 Summary 4.6 Practice SetPart II COMPUTER HARDWAREChapter 5 Computer Organization 5.1 Central Processing Unit (CPU) Arithmetic Logic Unit (ALU) Registers Control Unit 5.2 Main Memory Address Space Memory Types Memory Hierarchy Cache Memory 5.3 Input/Output Nonstorage Devices Storage Devices 5.4 Subsystems Interconnection Connecting CPU and Memory Connecting I/O Devices Addressing Input/Output Devices 5.5 Program Execution Machine Cycle A Machine Cycle Example Input/Output Operation 5.6 Two Different Architectures CISC RISC 5.7 Key Terms 5.8 Summary 5.9 Practice SetChapter 6 Computer Networks 6.1 Networks, Large and Small Model and Protocol 6.2 OSI Model Seven Layers Functions of the Layers 6.3 Categories of Networks Local Area Network (LAN) Metropolitan Area Network (MAN) Wide Area Network (WAN) 6.4 Connecting Devices Repeaters Bridges Routers Gateways 6.5 The Internet and TCP/IP Physical and Data-Link Layers Network Layer Transport Layer Application Layer 6.6 Key Terms 6.7 Summary 6.8 Practice SetPart III COMPUTER SOFTWAREChapter 7 Operating Systems 7.1 Definition 7.2 Evolution Batch Systems Time-Sharing Systems Personal Systems Parallel Systems Distributed Systems 7.3 Components Memory Manager Process Manager Device Manager File Manager User Interface 7.4 Popular Operating Systems Windows 2000 UNIX Linux 7.5 Key Terms 7.6 Summary 7.7 Practice SetChapter 8 Algorithms 8.1 Concept Informal Definition Example Defining Actions Refinement Generalization 8.2 Three Constructs Sequence Decision Repetition 8.3 Algorithm Representation Flowchart Pseudocode 8.4 A More Formal Definition Ordered Set Unambiguous Steps Produce a Result Terminate in a Finite Time 8.5 Subalgorithms Structure Chart 8.6 Basic Algorithms Summation Product Smallest and Largest Sorting Searching 8.7 Recursion Iterative Definition Recursive Definition 8.8 Key Terms 8.9 Summary 8.10 Practice SetChapter 9 Programming Languages 9.1 Evolution Machine Languages Symbolic Languages High-Level Languages Natural Languages 9.2 Building a Program Writing and Editing Programs Compiling Programs Linking Programs 9.3 Program Execution 9.4 Categories of Languages Procedural (Imperative) Languages Object-Oriented Languages Functional Languages Declarative (Logic) Languages Special Languages 9.5 A Procedural Language: C Identifiers Data Types Variables Constants Input and Output Expressions Statements Functions Selection Repetition Derived Data Types Recursion 9.6 Key Terms 9.7 Summary 9.8 Practice SetChapter 10 Software Engineering 10.1 Software Life Cycle Analysis Phase Design Phase Implementation Phase Testing Phase 10.2 Development Process Models Waterfall Model Incremental Model 10.3 Modularity Tools Coupling Cohesion 10.4 Quality Quality Defined Quality Factors The Quality Circle 10.5 Documentation User Documentation System Documentation Documentation as an Ongoing Process 10.6 Key Terms 10.7 Summary 10.8 Practice SetPart IV DATA ORGANIZATIONChapter 11 Data Structures 11.1 Arrays Array Applications Two-Dimensional Arrays 11.2 Records Accessing Records 11.3 Linked Lists Nodes Pointers to Linked Lists Operations on Linked Lists 11.4 Key Terms 11.5 Summary 11.6 Practice SetChapter 12 Abstract Data Types 12.1 Background Definition Model for an Abstract Data Type Operations on ADTs 12.2 Linear Lists Operations on Linear Lists Implementation of a General Linear List Linear List Applications 12.3 Stacks Operations on Stacks Implementation of a Stack Stack Applications 12.4 Queues Operations on Queues Implementation of a Queue Queue Applications 12.5 Trees Basic Tree Concepts Operations on Trees 12.6 Binary Trees Operations on Binary Trees Implementation of a Binary Tree Binary Tree Applications 12.7 Graphs Terminology Operations on Graphs Implementation of a Graph Graph Applications 12.8 Key Terms 12.9 Summary 12.10 Practice SetChapter 13 File Structures 13.1 Access Methods Sequential Access Random Access 13.2 Sequential Files Updating Sequential Files 13.3 Indexed Files Inverted Files 13.4 Hashed Files Hashing Methods Collision 13.5 Text versus Binary Text Files Binary Files 13.6 Key Terms 13.7 Summary 13.8 Practice SetChapter 14 Databases 14.1 Database Management System 14.2 Architecture Internal Level Conceptual Level External Level 14.3 Database Models Hierarchical Model Network Model Relational Model 14.4 Relational Model Relation 14.5 Operations on Relations Insert Delete Update Select Project Join Union Intersection Difference 14.6 Structured Query Language Statements 14.7 Other Database Models Distributed Databases Object-Oriented Databases 14.8 Key Terms 14.9 Summary 14.10 Practice SetPart V ADVANCED TOPICSChapter 15 Data Compression 15.1 Lossless Compression Run-Length Encoding Huffman Coding Lempel Ziv Encoding 15.2 Lossy Compression Methods Image Compression: JPEG Video Compression: MPEG 15.3 Key Terms 15.4 Summary 15.5 Practice SetChapter 16 Security Privacy Authentication Integrity Nonrepudiation 16.1 Privacy Encryption/Decryption Privacy Using the Combination 16.2 Digital Signature Signing the Whole Document Signing the Digest 16.3 Key Terms 16.4 Summary 16.5 Practice SetChapter 17 Theory of Computation 17.1 Simple Language Increment Statement Decrement Statement Loop Statement Power of the Simple Language Conclusion 17.2 Turing Machine Turing Machine Components Simulation of Simple Language Conclusion 17.3 Godel Numbers Representing a Program Interpreting a Number 17.4 Halting Problem Halting Problem is not Solvable 17.5 Solvable and Unsolvable Problems Unsolvable Problems Solvable Problems 17.6 Key Terms 17.7 Summary 17.8 Practice SetAppendix A ASCII CodeAppendix B UnicodeAppendix C Flowcharts C.1 Auxiliary Symbols C.2 Main SymbolsAppendix D Pseudocode D.1 ComponentsAppendix E Structure Charts E.1 Structure Chart Symbols E.2 Reading Structure Charts E.3 Rules of Structure ChartsAppendix F Discrete Cosine Transform F.1 Discrete Cosine Transform F.2 Inverse TransformAppendix G Acronyms