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