Computer Science Illuminated

Cover
Computer Science Illuminated
Copyright
Contents
1 Laying the Groundwork
Chapter 1 The Big Picture
1.1 Computing Systems
Layers of a Computing System
Abstraction
1.2 The History of Computing
A Brief History of Computing Hardware
A Brief History of Computing Software
Predictions
1.3 Computing as a Tool and a Discipline
The Big Ideas of Computing
Summary
Ethical Issues: Digital Divide
Key Terms
Exercises
Thought Questions
2 The Information Layer
Chapter 2 Binary Values and Number Systems
2.1 Numbers and Computing
2.2 Positional Notation
Binary, Octal, and Hexadecimal
Arithmetic in Other Bases
Power-of-2 Number Systems
Converting from Base 10 to Other Bases
Binary Values and Computers
Summary
Ethical Issues: The FISA Court
Key Terms
Exercises
Thought Questions
Chapter 3 Data Representation
3.1 Data and Computers
Analog and Digital Data
Binary Representations
3.2 Representing Numeric Data
Representing Negative Values
Representing Real Numbers
3.3 Representing Text
The ASCII Character Set
The Unicode Character Set
Text Compression
3.4 Representing Audio Data
Audio Formats
The MP3 Audio Format
3.5 Representing Images and Graphics
Representing Color
Digitized Images and Graphics
Vector Representation of Graphics
3.6 Representing Video
Video Codecs
Summary
Ethical Issues: The Fallout from Snowden’s Revelations
Key Terms
Exercises
Thought Questions
3 The Hardware Layer
Chapter 4 Gates and Circuits
4.1 Computers and Electricity
4.2 Gates
NOT Gate
AND Gate
OR Gate
XOR Gate
NAND and NOR Gates
Review of Gate Processing
Gates with More Inputs
4.3 Constructing Gates
Transistors
4.4 Circuits
Combinational Circuits
Adders
Multiplexers
4.5 Circuits as Memory
4.6 Integrated Circuits
4.7 CPU Chips
Summary
Ethical Issues: Codes of Ethics
Key Terms
Exercises
Thought Questions
Chapter 5 Computing Components
5.1 Individual Computer Components
5.2 The Stored-Program Concept
von Neumann Architecture
The Fetch–Execute Cycle
RAM and ROM
Secondary Storage Devices
Touch Screens
5.3 Embedded Systems
5.4 Parallel Architectures
Parallel Computing
Classes of Parallel Hardware
Summary
Ethical Issues: Is Privacy a Thing of the Past?
Key Terms
Exercises
Thought Questions
4 The Programming Layer
Chapter 6 Low-Level Programming Languages and Pseudocode
6.1 Computer Operations
6.2 Machine Language
Pep/9: A Virtual Computer
Input and Output in Pep/9
6.3 A Program Example
Pep/9 Simulator
Another Machine-Language Example
6.4 Assembly Language
Pep/9 Assembly Language
Numeric Data, Branches, and Labels
Loops in Assembly Language
6.5 Expressing Algorithms
Pseudocode Functionality
Following a Pseudocode Algorithm
Writing a Pseudocode Algorithm
Translating a Pseudocode Algorithm
6.6 Testing
Summary
Ethical Issues: Software Piracy
Key Terms
Exercises
Thought Questions
Chapter 7 Problem Solving and Algorithms
7.1 How to Solve Problems
Ask Questions
Look for Familiar Things
Divide and Conquer
Algorithms
Computer Problem-Solving Process
Summary of Methodology
Testing the Algorithm
7.2 Algorithms with Simple Variables
An Algorithm with Selection
Algorithms with Repetition
7.3 Composite Variables
Arrays
Records
7.4 Searching Algorithms
Sequential Search
Sequential Search in a Sorted Array
Binary Search
7.5 Sorting
Selection Sort
Bubble Sort
Insertion Sort
7.6 Recursive Algorithms
Subprogram Statements
Recursive Factorial
Recursive Binary Search
Quicksort
7.7 Important Threads
Information Hiding
Abstraction
Naming Things
Testing
Summary
Ethical Issues: Open-Source Software
Key Terms
Exercises
Thought Questions
Chapter 8 Abstract Data Types and Subprograms
8.1 What Is an Abstract Data Type?
8.2 Stacks
8.3 Queues
8.4 Lists
8.5 Trees
Binary Trees
Binary Search Trees
Other Operations
8.6 Graphs
Creating a Graph
Graph Algorithms
8.7 Subprograms
Parameter Passing
Value and Reference Parameters
Summary
Ethical Issues: Workplace Monitoring
Key Terms
Exercises
Thought Questions
Chapter 9 Object-Oriented Design and High-Level Programming Languages
9.1 Object-Oriented Methodology
Object Orientation
Design Methodology
Example
9.2 Translation Process
Compilers
Interpreters
9.3 Programming Language Paradigms
Imperative Paradigm
Declarative Paradigm
9.4 Functionality in High-Level Languages
Boolean Expressions
Data Typing
Input/Output Structures
Control Structures
9.5 Functionality of Object-Oriented Languages
Encapsulation
Classes
Inheritance
Polymorphism
9.6 Comparison of Procedural and Object-Oriented Designs
Summary
Ethical Issues: Hoaxes and Scams
Key Terms
Exercises
Thought Questions
5 The Operating Systems Layer
Chapter 10 Operating Systems
10.1 Roles of an Operating System
Memory, Process, and CPU Management
Batch Processing
Timesharing
Other OS Factors
10.2 Memory Management
Single Contiguous Memory Management
Partition Memory Management
Paged Memory Management
10.3 Process Management
The Process States
The Process Control Block
10.4 CPU Scheduling
First Come, First Served
Shortest Job Next
Round Robin
Summary
Ethical Issues: Medical Privacy: HIPAA
Key Terms
Exercises
Thought Questions
Chapter 11 File Systems and Directories
11.1 File Systems
Text and Binary Files
File Types
File Operations
File Access
File Protection
11.2 Directories
Directory Trees
Path Names
11.3 Disk Scheduling
First-Come, First-Served Disk Scheduling
Shortest-Seek-Time-First Disk Scheduling
SCAN Disk Scheduling
Summary
Ethical Issues: Privacy: Opt-In or Opt-Out?
Key Terms
Exercises
Thought Questions
6 The Applications Layer
Chapter 12 Information Systems
12.1 Managing Information
12.2 Spreadsheets
Spreadsheet Formulas
Circular References
Spreadsheet Analysis
12.3 Database Management Systems
The Relational Model
Relationships
Structured Query Language
Database Design
12.4 E-Commerce
12.5 Big Data
Summary
Ethical Issues: Politics and the Internet
Key Terms
Exercises
Thought Questions
Chapter 13 Artificial Intelligence
13.1 Thinking Machines
The Turing Test
Aspects of AI
13.2 Knowledge Representation
Semantic Networks
Search Trees
13.3 Expert Systems
13.4 Neural Networks
Biological Neural Networks
Artificial Neural Networks
13.5 Natural-Language Processing
Voice Synthesis
Voice Recognition
Natural-Language Comprehension
13.6 Robotics
The Sense–Plan–Act Paradigm
Subsumption Architecture
Physical Components
Summary
Ethical Issues: Initial Public Offerings
Key Terms
Exercises
Thought Questions
Chapter 14 Simulation, Graphics, Gaming, and Other Applications
14.1 What Is Simulation?
Complex Systems
Models
Constructing Models
14.2 Specific Models
Queuing Systems
Meteorological Models
Computational Biology
Other Models
Computing Power Necessary
14.3 Computer Graphics
How Light Works
Object Shape Matters
Simulating Light
Modeling Complex Objects
Getting Things to Move
14.4 Gaming
History of Gaming
Creating the Virtual World
Game Design and Development
Game Programming
Summary
Ethical Issues: Gaming as an Addiction
Key Terms
Exercises
Thought Questions
7 The Communications Layer
Chapter 15 Networks
15.1 Networking
Types of Networks
Internet Connections
Packet Switching
15.2 Open Systems and Protocols
Open Systems
Network Protocols
TCP/IP
High-Level Protocols
MIME Types
Firewalls
15.3 Network Addresses
Domain Name System
Who Controls the Internet?
15.4 Cloud Computing
15.5 Blockchain
Summary
Ethical Issues: The Effects of Social Networking
Key Terms
Exercises
Thought Questions
Chapter 16 The World Wide Web
16.1 Spinning the Web
Search Engines
Instant Messaging
Weblogs
Cookies
Web Analytics
16.2 HTML and CSS
Basic HTML Elements
Tag Attributes
More About CSS
More HTML5 Elements
16.3 Interactive Web Pages
Java Applets
Java Server Pages
16.4 XML
16.5 Social Network Evolution
Summary
Ethical Issues: Gambling and the Internet
Key Terms
Exercises
Thought Questions
Chapter 17 Computer Security
17.1 Security at All Levels
Information Security
17.2 Preventing Unauthorized Access
Passwords
CAPTCHA
Fingerprint Analysis
17.3 Malicious Code
Antivirus Software
Security Attacks
17.4 Cryptography
17.5 Protecting Your Information Online
Corporate Responsibility
Security and Portable Devices
WikiLeaks
Summary
Ethical Issues: Blogging and Journalism
Key Terms
Exercises
Thought Questions
8 In Conclusion
Chapter 18 Limitations of Computing
18.1 Hardware
Limits on Arithmetic
Limits on Components
Limits on Communications
18.2 Software
Complexity of Software
Current Approaches to Software Quality
Notorious Software Errors
18.3 Problems
Comparing Algorithms
Turing Machines
Halting Problem
Classification of Algorithms
Summary
Ethical Issues: Therac-25: Anatomy of a Disaster
Key Terms
Exercises
Thought Questions
Glossary
Endnotes
Index