CONTENTS IN DETAIL

ACKNOWLEDGMENTS

INTRODUCTION

About This Book

Prerequisites

Chosen Topics

Programming Style

Exercises

Why C++?

1
STRATEGIES FOR PROBLEM SOLVING

Classic Puzzles

The Fox, the Goose, and the Corn

Problem: How to Cross the River?

Sliding Tile Puzzles

Problem: The Sliding Eight

Problem: The Sliding Five

Sudoku

Problem: Completing a Sudoku Square

The Quarrasi Lock

Problem: Opening the Alien Lock

General Problem-Solving Techniques

Always Have a Plan

Restate the Problem

Divide the Problem

Start with What You Know

Reduce the Problem

Look for Analogies

Experiment

Don’t Get Frustrated

Exercises

2
PURE PUZZLES

Review of C++ Used in This Chapter

Output Patterns

Problem: Half of a Square

Problem: A Square (Half of a Square Reduction)

Problem: A Line (Half of a Square Further Reduction)

Problem: Count Down by Counting Up

Problem: A Sideways Triangle

Input Processing

Problem: Luhn Checksum Validation

Breaking Down the Problem

Problem: Convert Character Digit to Integer

Problem: Luhn Checksum Validation, Fixed Length

Problem: Simple Checksum Validation, Fixed Length

Problem: Positive or Negative

Putting the Pieces Together

Tracking State

Problem: Decode a Message

Problem: Reading a Number with Three or Four Digits

Problem: Reading a Number with Three or Four Digits, Further Simplified

Conclusion

Exercises

3
SOLVING PROBLEMS WITH ARRAYS

Review of Array Fundamentals

Store

Copy

Retrieval and Search

Sort

Compute Statistics

Solving Problems with Arrays

Problem: Finding the Mode

Refactoring

Arrays of Fixed Data

Non-scalar Arrays

Multidimensional Arrays

Deciding When to Use Arrays

Exercises

4
SOLVING PROBLEMS WITH POINTERS AND DYNAMIC MEMORY

Review of Pointer Fundamentals

Benefits of Pointers

Runtime-Sized Data Structures

Resizable Data Structures

Memory Sharing

When to Use Pointers

Memory Matters

The Stack and the Heap

Memory Size

Lifetime

Solving Pointer Problems

Variable-Length Strings

Problem: Variable-Length String Manipulation

Linked Lists

Problem: Tracking an Unknown Quantity of Student Records

Conclusion and Next Steps

Exercises

5
SOLVING PROBLEMS WITH CLASSES

Review of Class Fundamentals

Goals of Class Use

Encapsulation

Code Reuse

Dividing the Problem

Information Hiding

Readability

Expressiveness

Building a Simple Class

Problem: Class Roster

The Basic Class Framework

Support Methods

Classes with Dynamic Data

Problem: Tracking an Unknown Quantity of Student Records

Adding a Node

Rearranging the List

Destructor

Deep Copy

The Big Picture for Classes with Dynamic Memory

Mistakes to Avoid

The Fake Class

Single-Taskers

Exercises

6
SOLVING PROBLEMS WITH RECURSION

Review of Recursion Fundamentals

Head and Tail Recursion

Problem: How Many Parrots?

Approach 1

Approach 2

Problem: Who’s Our Best Customer?

Approach 1

Approach 2

The Big Recursive Idea

Problem: Computing the Sum of an Array of Integers

Common Mistakes

Too Many Parameters

Global Variables

Applying Recursion to Dynamic Data Structures

Recursion and Linked Lists

Problem: Counting Negative Numbers in a Singly Linked List

Recursion and Binary Trees

Problem: Find the Largest Value in a Binary Tree

Wrapper Functions

Problem: Find the Number of Leaves in a Binary Tree

When to Choose Recursion

Arguments Against Recursion

Problem: Display a Linked List in Order

Problem: Display a Linked List in Reverse Order

Exercises

7
SOLVING PROBLEMS WITH CODE REUSE

Good Reuse and Bad Reuse

Review of Component Fundamentals

Code Block

Algorithms

Patterns

Abstract Data Types

Libraries

Building Component Knowledge

Exploratory Learning

Problem: The First Student

As-Needed Learning

Problem: Efficient Traversal

Choosing a Component Type

Component Choice in Action

Problem: Sorting Some, Leaving Others Alone

Comparing the Results

Exercises

8
THINKING LIKE A PROGRAMMER

Creating Your Own Master Plan

Playing to Your Strengths and Weaknesses

Putting the Master Plan Together

Tackling Any Problem

Problem: Cheating at Hangman

Finding a Way to Cheat

Required Operations for Cheating at Hangman

Initial Design

Initial Coding

Analysis of Initial Results

The Art of Problem Solving

Learning New Programming Skills

New Languages

New Skills for a Language You Already Know

New Libraries

Take a Class

Conclusion

Exercises

INDEX