Foundations of Computer Science: From Data Manipulation to Theory of Computation
Subtitle: From Data Manipulation to Theory of Computation
Edition: 1 edition
Publisher: Course Technology
Published: May 6, 2002
Language: eng
Format: Paperback
Number of pages: 416
ISBN-13: 9780534391430
Subjects: Information technology industries; Systems management; Computers - General Information; Computers; Computer Books: General; Computer Science; Computers / Computer Science
Table of contents: label: Part I
title: Computer and Data
pagenum: 1; label: Chapter 1
title: Introduction
pagenum: 2; label: 1.1
title: The Computer as a Black Box
pagenum: 3; title: Data Processor
pagenum: 3; title: Programmable Data Processor
pagenum: 3; label: 1.2
title: Von Neumann Model
pagenum: 5; title: Four Subsystems
pagenum: 5; title: Stored Program Concept
pagenum: 6; title: Sequential Execution of Instructions
pagenum: 6; label: 1.3
title: Computer Hardware
pagenum: 6; label: 1.4
title: Data
pagenum: 6; title: Storing Data
pagenum: 6; title: Organizing Data
pagenum: 7; label: 1.5
title: Computer Software
pagenum: 7; title: Programs Must Be Stored
pagenum: 7; title: A Sequence of Instructions
pagenum: 7; title: Algorithms
pagenum: 8; title: Languages
pagenum: 8; title: Software Engineering
pagenum: 8; title: Operating Systems
pagenum: 8; label: 1.6
title: History
pagenum: 9; title: Mechanical Machines (Before 1930)
pagenum: 9; title: Birth of Electronic Computers (1930–1950)
pagenum: 9; label: 1.7
title: Key Terms
pagenum: 11; label: 1.8
title: Summary
pagenum: 11; label: 1.9
title: Practice Set
pagenum: 11; label: Chapter 2
title: Data Representation
pagenum: 14; label: 2.1
title: Data Types
pagenum: 15; label: 2.2
title: Data Inside the Computer
pagenum: 15; title: Bit
pagenum: 16; title: Bit Pattern
pagenum: 16; title: Byte
pagenum: 16; label: 2.3
title: Representing Data
pagenum: 17; title: Text
pagenum: 17; title: Numbers
pagenum: 19; title: Images
pagenum: 19; title: Audio
pagenum: 20; title: Video
pagenum: 21; label: 2.4
title: Hexadecimal Notation
pagenum: 21; title: Conversion
pagenum: 22; label: 2.5
title: Octal Notation
pagenum: 23; title: Conversion
pagenum: 23; label: 2.6
title: Key Terms
pagenum: 24; label: 2.7
title: Summary
pagenum: 24; label: 2.8
title: Practice Set
pagenum: 25; label: Chapter 3
title: Number Representation
pagenum: 27; label: 3.1
title: Decimal and Binary
pagenum: 28; title: Decimal System
pagenum: 28; title: Binary System
pagenum: 28; label: 3.2
title: Conversion
pagenum: 29; title: Binary to Decimal Conversion
pagenum: 29; title: Decimal to Binary Conversion
pagenum: 29; label: 3.3
title: Integer Representation
pagenum: 30; title: Unsigned Integers Format
pagenum: 31; title: Sign-and-Magnitude Format
pagenum: 33; title: One's Complement Format
pagenum: 35; title: Two's Complement Format
pagenum: 37; title: Summary of Integer Representation
pagenum: 39; label: 3.4
title: Excess System
pagenum: 40; label: 3.5
title: Floating-Point Representation
pagenum: 40; title: Converting to Binary
pagenum: 40; title: Normalization
pagenum: 42; title: Sign, Exponent, and Mantissa
pagenum: 42; title: IEEE Standards
pagenum: 42; label: 3.6
title: Hexadecimal Notation
pagenum: 44; label: 3.7
title: Key Terms
pagenum: 44; label: 3.8
title: Summary
pagenum: 45; label: 3.9
title: Practice Set
pagenum: 45; label: Chapter 4
title: Operations on Bits
pagenum: 50; label: 4.1
title: Arithmetic Operations
pagenum: 51; title: Arithmetic Operations on Integers
pagenum: 51; title: Arithmetic Operations on Floating-Point Numbers
pagenum: 54; label: 4.2
title: Logical Operations
pagenum: 55; title: Truth Tables
pagenum: 56; title: Unary Operator
pagenum: 56; title: Binary Operators
pagenum: 57; title: Applications
pagenum: 60; label: 4.3
title: Shift Operations
pagenum: 63; label: 4.4
title: Key Terms
pagenum: 64; label: 4.5
title: Summary
pagenum: 65; label: 4.6
title: Practice Set
pagenum: 65; label: Part II
title: Computer Hardware
pagenum: 69; label: Chapter 5
title: Computer Organization
pagenum: 70; label: 5.1
title: Central Processing Unit (CPU)
pagenum: 71; title: Arithmetic Logic Unit (ALU)
pagenum: 71; title: Registers
pagenum: 71; title: Control Unit
pagenum: 72; label: 5.2
title: Main Memory
pagenum: 72; title: Address Space
pagenum: 72; title: Memory Types
pagenum: 74; title: Memory Hierarchy
pagenum: 75; title: Cache Memory
pagenum: 75; label: 5.3
title: Input/Output
pagenum: 76; title: Nonstorage Devices
pagenum: 76; title: Storage Devices
pagenum: 76; label: 5.4
title: Subsystem Interconnection
pagenum: 83; title: Connecting CPU and Memory
pagenum: 83; title: Connecting I/O Devices
pagenum: 84; title: Addressing Input/Output Devices
pagenum: 86; label: 5.5
title: Program Execution
pagenum: 87; title: Machine Cycle
pagenum: 87; title: A Machine Cycle Example
pagenum: 88; title: Input/Output Operation
pagenum: 89; label: 5.6
title: Two Different Architectures
pagenum: 92; title: CISC
pagenum: 92; title: RISC
pagenum: 93; label: 5.7
title: Key Terms
pagenum: 93; label: 5.8
title: Summary
pagenum: 93; label: 5.9
title: Practice Set
pagenum: 94; label: Chapter 6
title: Computer Networks
pagenum: 99; label: 6.1
title: Networks, Large and Small
pagenum: 100; title: Model and Protocol
pagenum: 100; label: 6.2
title: OSI Model
pagenum: 100; title: Seven Layers
pagenum: 100; title: Functions of the Layers
pagenum: 101; label: 6.3
title: Categories of Networks
pagenum: 103; title: Local Area Network (LAN)
pagenum: 103; title: Metropolitan Area Network (MAN)
pagenum: 104; title: Wide Area Network (WAN)
pagenum: 104; label: 6.4
title: Connecting Devices
pagenum: 105; title: Repeaters
pagenum: 106; title: Bridges
pagenum: 107; title: Routers
pagenum: 108; title: Gateways
pagenum: 108; label: 6.5
title: The Internet and TCP/IP
pagenum: 109; title: Physical and Data-Link Layers
pagenum: 110; title: Network Layer
pagenum: 110; title: Transport Layer
pagenum: 111; title: Application Layer
pagenum: 111; label: 6.6
title: Key Terms
pagenum: 116; label: 6.7
title: Summary
pagenum: 116; label: 6.8
title: Practice Set
pagenum: 117; label: Part III
title: Computer Software
pagenum: 121; label: Chapter 7
title: Operating Systems
pagenum: 122; label: 7.1
title: Definition
pagenum: 123; label: 7.2
title: Evolution
pagenum: 123; title: Batch Systems
pagenum: 123; title: Time-Sharing Systems
pagenum: 123; title: Personal Systems
pagenum: 124; title: Parallel Systems
pagenum: 124; title: Distributed Systems
pagenum: 124; label: 7.3
title: Components
pagenum: 124; title: Memory Manager
pagenum: 125; title: Process Manager
pagenum: 129; title: Device Manager
pagenum: 135; title: File Manager
pagenum: 135; title: User Interface
pagenum: 136; label: 7.4
title: Popular Operating Systems
pagenum: 136; title: Windows 2000
pagenum: 136; title: UNIX
pagenum: 136; title: Linux
pagenum: 136; label: 7.5
title: Key Terms
pagenum: 137; label: 7.6
title: Summary
pagenum: 137; label: 7.7
title: Practice Set
pagenum: 138; label: Chapter 8
title: Algorithms
pagenum: 141; label: 8.1
title: Concept
pagenum: 142; title: Informal Definition
pagenum: 142; title: Example
pagenum: 142; title: Defining Actions
pagenum: 144; title: Refinement
pagenum: 144; title: Generalization
pagenum: 144; label: 8.2
title: Three Constructs
pagenum: 145; title: Sequence
pagenum: 146; title: Decision
pagenum: 146; title: Repetition
pagenum: 146; label: 8.3
title: Algorithm Representation
pagenum: 146; title: Flowchart
pagenum: 146; title: Pseudocode
pagenum: 146; label: 8.4
title: More Formal Definition
pagenum: 150; title: Ordered Set
pagenum: 150; title: Unambiguous Steps
pagenum: 150; title: Produce a Result
pagenum: 150; title: Terminate in a Finite Time
pagenum: 150; label: 8.5
title: Subalgorithms
pagenum: 150; title: Structure Chart
pagenum: 152; label: 8.6
title: Basic Algorithms
pagenum: 152; title: Summation
pagenum: 152; title: Product
pagenum: 152; title: Smallest and Largest
pagenum: 153; title: Sorting
pagenum: 153; title: Searching
pagenum: 158; label: 8.7
title: Recursion
pagenum: 160; title: Iterative Definition
pagenum: 160; title: Recursive Definition
pagenum: 161; label: 8.8
title: Key Terms
pagenum: 162; label: 8.9
title: Summary
pagenum: 162; label: 8.10
title: Practice Set
pagenum: 163; label: Chapter 9
title: Programming Languages
pagenum: 166; label: 9.1
title: Evolution
pagenum: 167; title: Machine Languages
pagenum: 167; title: Symbolic Languages
pagenum: 168; title: High-Level Languages
pagenum: 168; title: Natural Languages
pagenum: 169; label: 9.2
title: Building a Program
pagenum: 169; title: Writing and Editing Programs
pagenum: 169; title: Compiling Programs
pagenum: 170; title: Linking Programs
pagenum: 170; label: 9.3
title: Program Execution
pagenum: 171; label: 9.4
title: Categories of Languages
pagenum: 171; title: Procedural (Imperative) Languages
pagenum: 172; title: Object-Oriented Languages
pagenum: 173; title: Functional Languages
pagenum: 175; title: Declarative (Logic) Languages
pagenum: 176; title: Special Languages
pagenum: 177; label: 9.5
title: A Procedural Language: C
pagenum: 179; title: Identifiers
pagenum: 179; title: Data Types
pagenum: 179; title: Variables
pagenum: 180; title: Constants
pagenum: 181; title: Input and Output
pagenum: 182; title: Expressions
pagenum: 182; title: Statements
pagenum: 183; title: Functions
pagenum: 184; title: Selection
pagenum: 186; title: Repetition
pagenum: 187; title: Derived Data Types
pagenum: 189; title: Recursion
pagenum: 189; label: 9.6
title: Key Terms
pagenum: 189; label: 9.7
title: Summary
pagenum: 190; label: 9.8
title: Practice Set
pagenum: 191; label: Chapter 10
title: Software Engineering
pagenum: 195; label: 10.1
title: Software Life Cycle
pagenum: 196; title: Analysis Phase
pagenum: 197; title: Design Phase
pagenum: 197; title: Implementation Phase
pagenum: 197; title: Testing Phase
pagenum: 198; label: 10.2
title: Development Process Models
pagenum: 198; title: Waterfall Model
pagenum: 198; title: Incremental Model
pagenum: 199; label: 10.3
title: Modularity
pagenum: 200; title: Tools
pagenum: 200; title: Coupling
pagenum: 200; title: Cohesion
pagenum: 201; label: 10.4
title: Quality
pagenum: 202; title: Quality Defined
pagenum: 202; title: Quality Factors
pagenum: 203; title: The Quality Circle
pagenum: 205; label: 10.5
title: Documentation
pagenum: 206; title: User Documentation
pagenum: 206; title: System Documentation
pagenum: 206; title: Documentation as an Ongoing Process
pagenum: 207; label: 10.6
title: Key Terms
pagenum: 207; label: 10.7
title: Summary
pagenum: 208; label: 10.8
title: Practice Set
pagenum: 208; label: Part IV
title: Data Organization
pagenum: 213; label: Chapter 11
title: Data Structures
pagenum: 214; label: 11.1
title: Arrays
pagenum: 215; title: Array Applications
pagenum: 217; title: Two-Dimensional Arrays
pagenum: 218; label: 11.2
title: Records
pagenum: 219; title: Accessing Records
pagenum: 220; label: 11.3
title: Linked Lists
pagenum: 220; title: Nodes
pagenum: 221; title: Pointers to Linked Lists
pagenum: 221; title: Operations on Linked Lists
pagenum: 221; label: 11.4
title: Key Terms
pagenum: 223; label: 11.5
title: Summary
pagenum: 224; label: 11.6
title: Practice Set
pagenum: 224; label: Chapter 12
title: Abstract Data Types
pagenum: 227; label: 12.1
title: Background
pagenum: 228; title: Definition
pagenum: 228; title: Model for an Abstract Data Type
pagenum: 229; title: Operations on ADTs
pagenum: 229; label: 12.2
title: Linear Lists
pagenum: 229; title: Operations on Linear Lists
pagenum: 230; title: Implementation of a General Linear List
pagenum: 232; title: Linear List Applications
pagenum: 232; label: 12.3
title: Stacks
pagenum: 232; title: Operations on Stacks
pagenum: 233; title: Implementation of a Stack
pagenum: 234; title: Stack Applications
pagenum: 234; label: 12.4
title: Queues
pagenum: 235; title: Operations on Queues
pagenum: 235; title: Implementation of a Queue
pagenum: 237; title: Queue Applications
pagenum: 237; label: 12.5
title: Trees
pagenum: 237; title: Basic Tree Concepts
pagenum: 237; title: Operations on Trees
pagenum: 239; label: 12.6
title: Binary Trees
pagenum: 239; title: Operations on Binary Trees
pagenum: 241; title: Implementation of a Binary Tree
pagenum: 243; title: Binary Tree Applications
pagenum: 243; label: 12.7
title: Graphs
pagenum: 244; title: Terminology
pagenum: 244; title: Operations on Graphs
pagenum: 245; title: Implementation of a Graph
pagenum: 247; title: Graph Applications
pagenum: 248; label: 12.8
title: Key Terms
pagenum: 249; label: 12.9
title: Summary
pagenum: 249; label: 12.10
title: Practice Set
pagenum: 251; label: Chapter 13
title: File Structures
pagenum: 256; label: 13.1
title: Access Methods
pagenum: 257; title: Sequential Access
pagenum: 257; title: Random Access
pagenum: 257; label: 13.2
title: Sequential Files
pagenum: 257; title: Updating Sequential Files
pagenum: 258; label: 13.3
title: Indexed Files
pagenum: 259; title: Inverted Files
pagenum: 260; label: 13.4
title: Hashed Files
pagenum: 261; title: Hashing Methods
pagenum: 261; title: Collision
pagenum: 263; label: 13.5
title: Text versus Binary
pagenum: 265; title: Text Files
pagenum: 265; title: Binary Files
pagenum: 266; label: 13.6
title: Key Terms
pagenum: 266; label: 13.7
title: Summary
pagenum: 266; label: 13.8
title: Practice Set
pagenum: 267; label: Chapter 14
title: Databases
pagenum: 270; label: 14.1
title: Database Management System
pagenum: 271; label: 14.2
title: Architecture
pagenum: 272; title: Internal Level
pagenum: 272; title: Conceptual Level
pagenum: 272; title: External Level
pagenum: 272; label: 14.3
title: Database Models
pagenum: 273; title: Hierarchical Model
pagenum: 273; title: Network Model
pagenum: 273; title: Relational Model
pagenum: 274; label: 14.4
title: Relational Model
pagenum: 274; title: Relation
pagenum: 274; label: 14.5
title: Operations on Relations
pagenum: 275; title: Insert
pagenum: 275; title: Delete
pagenum: 275; title: Update
pagenum: 276; title: Select
pagenum: 276; title: Project
pagenum: 277; title: Join
pagenum: 277; title: Union
pagenum: 277; title: Intersection
pagenum: 278; title: Difference
pagenum: 278; label: 14.6
title: Structured Query Language
pagenum: 279; title: Statements
pagenum: 279; label: 14.7
title: Other Database Models
pagenum: 282; title: Distributed Databases
pagenum: 282; title: Object-Oriented Databases
pagenum: 282; label: 14.8
title: Key Terms
pagenum: 283; label: 14.9
title: Summary
pagenum: 283; label: 14.10
title: Practice Set
pagenum: 284; label: Part V
title: Advanced Topics
pagenum: 289; label: Chapter 15
title: Data Compression
pagenum: 290; label: 15.1
title: Lossless Compression
pagenum: 291; title: Run-Length Encoding
pagenum: 291; title: Huffman Coding
pagenum: 292; title: Lempel Ziv Encoding
pagenum: 294; label: 15.2
title: Lossy Compression Methods
pagenum: 298; title: Image Compression: JPEG
pagenum: 298; title: Video Compression: MPEG
pagenum: 301; label: 15.3
title: Key Terms
pagenum: 303; label: 15.4
title: Summary
pagenum: 303; label: 15.5
title: Practice Set
pagenum: 303; label: Chapter 16
title: Security
pagenum: 306; title: Privacy
pagenum: 307; title: Authentication
pagenum: 307; title: Integrity
pagenum: 307; title: Nonrepudiation
pagenum: 307; label: 16.1
title: Privacy
pagenum: 307; title: Encryption/Decryption
pagenum: 307; title: Privacy Using the Combination
pagenum: 311; label: 16.2
title: Digital Signature
pagenum: 311; title: Signing the Whole Document
pagenum: 312; title: Signing the Digest
pagenum: 312; label: 16.3
title: Key Terms
pagenum: 314; label: 16.4
title: Summary
pagenum: 314; label: 16.5
title: Practice Set
pagenum: 315; label: Chapter 17
title: Theory of Computation
pagenum: 317; label: 17.1
title: Simple Language
pagenum: 318; title: Increment Statement
pagenum: 318; title: Decrement Statement
pagenum: 318; title: Loop Statement
pagenum: 318; title: Power of the Simple Language
pagenum: 318; title: Conclusion
pagenum: 321; label: 17.2
title: Turing Machine
pagenum: 321; title: Turing Machine Components
pagenum: 322; title: Simulation of Simple Language
pagenum: 323; title: Conclusion
pagenum: 325; label: 17.3
title: Gödel Numbers
pagenum: 326; title: Representing a Program
pagenum: 326; title: Interpreting a Number
pagenum: 327; label: 17.4
title: Halting Problem
pagenum: 327; title: Halting Problem Is Not Solvable
pagenum: 328; label: 17.5
title: Solvable and Unsolvable Problems
pagenum: 329; title: Unsolvable Problems
pagenum: 329; title: Solvable Problems
pagenum: 330; label: 17.6
title: Key Terms
pagenum: 331; label: 17.7
title: Summary
pagenum: 331; label: 17.8
title: Practice Set
pagenum: 332; label: Appendix A
title: ASCII Code
pagenum: 335; label: Appendix B
title: Unicode
pagenum: 339; title: Alphabets
pagenum: 340; title: Symbols and Punctuation Marks
pagenum: 341; title: CJK Auxiliaries
pagenum: 341; title: CJK Unified Ideographs
pagenum: 341; title: Surrogates
pagenum: 342; title: Private Use
pagenum: 342; title: Miscellaneous Characters and Symbols
pagenum: 342; label: Appendix C
title: Flowcharts
pagenum: 343; label: C.1
title: Auxiliary Symbols
pagenum: 344; title: Start and Stop
pagenum: 344; title: Flow Lines
pagenum: 345; title: Connectors
pagenum: 345; label: C.2
title: Main Symbols
pagenum: 345; title: Sequence Statements
pagenum: 345; title: Selection Statements
pagenum: 347; title: Looping Statements
pagenum: 348; label: Appendix D
title: Pseudocode
pagenum: 350; label: D.1
title: Components
pagenum: 351; title: Algorithm Header
pagenum: 351; title: Purpose, Conditions, and Return
pagenum: 351; title: Statement Numbers
pagenum: 351; title: Statement Constructs
pagenum: 351; title: Sequence
pagenum: 352; title: Selection
pagenum: 352; title: Loop
pagenum: 352; label: Appendix E
title: Structure Charts
pagenum: 353; label: E.1
title: Structure Chart Symbols
pagenum: 354; title: Function Symbol
pagenum: 354; title: Selection in Structure Charts
pagenum: 355; title: Loops in Structure Charts
pagenum: 355; title: Data Flows
pagenum: 356; label: E.2
title: Reading Structure Charts
pagenum: 356; label: E.3
title: Rules of Structure Charts
pagenum: 357; label: Appendix F
title: Discrete Cosine Transform
pagenum: 358; label: F.1
title: Discrete Cosine Transform
pagenum: 359; label: F.2
title: Inverse Transform
pagenum: 359; label: Appendix G
title: Acronyms
pagenum: 360; title: Glossary
pagenum: 361; title: Index
pagenum: 377