A Computer Science Tapestry
Table of Contents
Computer Science and Programming
page 1
1.1 What Is Computer Science?
1.2 Algorithms
1.3 Computer Science Themes and Concepts
1.4 Language, Architecture, and Programs
1.5 Language and Program Design
1.6 Chapter Review
1.7 Exercises
Part I: Foundations of C++ Programming
C++ Programs: Form and Function
page 29
2.1 Simple C++ Programs
2.1.1 Syntax and Semantics
2.2 How a Program Works
2.2.1 Flow of Control
2.3 What can be output?
2.4 Using Functions
2.5 Functions with parameters
2.5.1 Passing Parameters
2.6 Functions with Several Parameters
2.7 Program Style
2.7.1 Identifiers
2.8 Chapter Review
2.9 Exercises
2.10 A Computer Science Excursion: Program Complexity
C++ Programs: Input/Process/Output
page 81
3.1 The Input Phase of Computation
3.1.1 The Input Stream
cin
3.1.2 Variables
3.2 Processing Numbers
3.2.1 Numeric Data
3.2.2 Arithmetic Operators
3.2.3 Evaluating Expressions
3.3 Case Study: Pizza Slices
3.4 Classes and Types: An Introduction
3.4.1 Member Functions
3.4.2 Reading Programs
3.4.3 Private and Public
3.5 Compiling and Linking
3.6 Chapter Review
3.7 Exercises
Building Programs and Solving Problems
page 111
4.1 The Assignment Operator
4.2 Choices and Conditional Execution
4.2.1 The
if/else
statement
4.3 Operators
4.3.1 Relational Operators
4.3.2 Logical Operators
4.3.3 Short-Circuited Evaluation
4.3.4 Arithmetic Assignment Operators
4.4 Block Statements and Defensive Programming
4.4.1 Defensive Programming Conventions
4.4.2 Cascaded
if/else
statements
4.5 Functions that Return Values
4.5.1 The Math Library <math.h>
4.5.2 Function Return Types
4.6 Classes and Member Functions
4.6.1 String Member Functions
4.7 Chapter Review
4.8 Exercises
4.9 A Computer Science Excursion: Recursion and Exponentiation
4.9.1 Excursion Exercises
Iteration with Programs and Classes
page 175
5.1 Random Numbers and N-sided Dice
5.1.1 Using Constructors to Initialize
5.1.2 Class Documentation: The Interface
5.1.3 Class Documentation: The Implementation
5.2 Iteration: Testing the Dice Class
5.2.1 The While Loop
5.2.2 Infinite Loops
5.2.3 Improving the Test Program
5.3 Using and Developing Loops
5.3.1 Loops and Mathematical Functions
5.3.2 Computing Factorials
5.3.3 Computing Prime Numbers
5.3.4 Approximating Square Roots
5.3.5 Defining Constants
5.3.6 Numbers Written in English
5.3.7 Fencepost Problems
5.4 Alternative Looping Statements
5.4.1 The
for
loop
5.4.2 Operators ++ and --
5.4.3 The
do-while
loop
5.4.4 Infinite Loops
5.4.5 Choosing a Looping Statement
5.4.6 Nested Loops
5.5 Variable Scope
5.5.1 Scope of Private Variables
5.6 Case Study: Simulating Gambling Games
5.6.1 Selection with the
switch
statement
5.6.2 Simulating Dice Games
5.6.3 DeMorgan's Law
5.7 Chapter Review
5.8 Exercises
5.9 A Computer Science Excursion: Calendars and a Date Class
5.9.1 Constructors and Other Member Functions
5.9.2 Overloaded Arithmetic Operators
5.9.3 A Calendar Printing Program
5.9.4 C++ Details of the class
Date
5.9.5 Excursion Exercises
Part II: Program and Class Construction: Extending the Foundation
Sequential Access: Streams and Iterators
page 255
6.1 Reading Words: Stream Iteration
6.1.1 A Pseudocode Solution
6.1.2 Solving a Related Problem
6.1.3 The Final Program: Counting Words
6.2 Streams Associated with Files
6.2.1 Type Casting
6.2.2 Casting with
static_cast
6.2.3 A Word-reading Class using
ifstream
6.2.4 I/O Redirection
6.3 Finding Extreme Values
6.3.1 Largest/Smallest Values
6.3.2 Initialization: Another Fencepost Problem
6.3.3 Word Frequencies
6.4 Reference Parameters and Class Design
6.4.1 A Class Solution
6.4.2 Reference Parameters
6.4.3 Const Reference Parameters
6.5 Chapter Review
6.6 Exercises
6.7 A Computer Science Excursion: Lists
6.7.1 Lists and List Operations
6.7.2 Counting Words
6.7.3 Operator Details
6.7.4 Excursion Exercises
Class Design and Implementation via Simulation
page 309
7.1 Random Walks
7.1.1 One-dimensional Random Walks
7.1.2 A RandomWalk Class
7.1.3 Two-Dimensional Walks
7.2 Coordinating Several Classes
7.2.1 A Walk Observer Class
7.2.2 Using and Sharing Observers: Reference Variables
7.3 Language Tools for Designing Classes
7.3.1 Developing a Coin class
7.3.2 Enumerated Types or Enums
7.3.3 Constructors, Declarations, and Initializer lists
7.3.4 Structs as Data Aggregates
7.3.5 Structs for Storing Points
7.3.6 Operators for Structs
7.4 Chapter Review
7.5 Exercises
7.6 A Computer Science Excursion: Embedded Real-Time Systems
7.6.1 Collaborating Classes: Heart and Monitor
7.6.2 A Simulated Cardioverter
7.6.3 Implementing the Heart class
7.6.4 Excursion Exercises
Arrays, Data, and Random Access
page 359
8.1 Arrays and Vectors as Counters
8.1.1
Vector
Definition: AN Introduction
8.1.2 Vectors and Counting: Rolling Dice
8.2 Defining and Using Vectors/Arrays
8.2.1
Vector
Definition
8.2.2
Vector
Initialization
8.2.3
Vector
Parameters
8.2.4 A
Vector
Case Study: Shuffling CD Tracks
8.3 Vectors as Lists
8.4 Class Study: Word List
8.4.1 Binary Search
8.4.2 Maintaining a Sorted List
8.4.3 Case Study: Extended Author Fingerprints
8.5 Built-in Arrays (optional)
8.5.1 Subscript Errors
8.5.2 Defining an Array
8.5.3 Initializing an Array
8.5.4 Arrays as Parameters
8.5.5 Const Parameters
8.6 Chapter Review
8.7 Exercises
8.8 A Computer Science Excursion: Large Integers
8.8.1 Developing a Test Program
8.8.2 The BigInt Class
8.8.3 Excursion Exercises
Part III: Design, Use, and Analysis: Building on the Foundation
Characters, Strings, and Streams: Abstraction and Information Hiding
page 427
9.1 Characters: Building blocks for Strings
9.1.1 The Type char as an Abstraction
9.1.2 The Library <ctype.h>
9.1.3 Strings as char sequences
9.2 Streams and Files as Lines and Characters
9.2.1 Input Using
getline()
9.2.2 Parsing Line-oriented Data Using String Streams
9.2.3 Stream Member Functions
9.2.4 Strings, Streams, and Characters
9.3 Case Study: Removing Comments with State Machines
9.4 Formatting Output
9.5 Case Study: Manipulating Compact Disks
9.5.1 Throw-away Code vs Class Design
9.5.2 A
ClockTime
Class
9.5.3 Overloaded Operators
9.5.4 Testing the
ClockTime
Class
9.5.5 The Final Program
9.6 Chapter Review
9.7 Exercises
9.8 A Computer Science Excursion: Numerical Representation
9.8.1 Roundoff Error
9.8.2 Modified Types: Float, Short, Long
9.8.3 Numerical Details: Representation
9.8.4 Binary Printing: A Small Case Study
9.8.5 Excursion Exercises
Recursion, Scope, and Lifetime
page 485
10.1 Recursive Functions
10.1.1 Similar and Simpler Functions
10.1.2 General Rules for Recursion
10.1.3 Infinite Recursion
10.2 Recursion and Directories
10.2.1 Classes for Traversing Directories
10.2.2 Recursion and Directory Traversal
10.2.3 Properties of Recursive Functions
10.3 Comparing Recursion and Iteration
10.3.1 Fibonacci Numbers
10.4 Scope and Lifetime
10.4.1 Global Variables
10.4.2 Hidden Identifiers
10.5 Static Definitions
10.6 Chapter Review
10.7 Exercises
Sorting, Algorithms, and Matrices
page 527
11.1 Sorting an Array
11.1.1 Selection Sort
11.2 Function Templates
11.3 Analyzing Sorts
11.3.1 O-notation
11.4 Quicksort
11.4.1 The Partition/Pivot Function
11.4.2 Analysis of Quick sort
11.5 Two-dimensional Arrays
11.6 Class Study: A RoadMap
11.6.1 Initializer Lists
11.6.2 Vectors of Vectors
11.7 Built-in Multidimensional Arrays (optional)
11.7.1 Two-dimensional arrays as Variables and Parameters
11.8 Chapter Review
11.9 Exercises
Information Hiding and Dynamic Data
page 575
12.1 Pointers as Indirect References
12.1.1 Pointers as References: A Closer Look
12.1.2 Pointers as Parameters
12.1.3 Pointers to Class Objects
12.1.4 Defining and Initializing Pointers
12.2 Vectors of Pointers and Operator new
12.2.1 Allocation and Access using Vectors of Pointers
12.2.2 The Destructor member function
12.2.3 Pointers for Sorting on Two Keys
12.3 Linked Lists
12.3.1 Creating Nodes with Linked Lists
12.3.2 Iterating Over a Linked List
12.3.3 Testing Linked List Functions
12.3.4 Deleting Nodes in a Linked list
12.3.5 Counting Words with Linked Lists
12.4 Making a List Class
12.4.1 A Templated Node Class
12.4.2 A Templated List Class
12.4.3 Implementing the List Class
12.4.4 Const Member functions and Reference Return Types
12.4.5 Assignment Operator and Copy Constructor
12.5 Arrays and Pointers in C++ (optional)
12.5.1 Implementing the Vector Class
12.5.2 Array Indexing and Pointer Arithmetic
12.6 Chapter Review
12.7 Exercises
12.8 A Computer Science Excursion: Hash Search and Tree Search
12.8.1 Hashing
12.8.2 Complexity of Hashing
12.9 Tree Search
12.9.1 Complexity of Search Trees
Class Declarations and Implementations
page 653
A.1 Random Number Classes
A.3 The
string
class
A.4 The
Vector
class