Algorithmic Thinking, 2nd Edition: Unlock Your Programming Potential

FOREWORD
ACKNOWLEDGMENTS
INTRODUCTION
What We’ll Do
New to the Second Edition
Who This Book Is For
Our Programming Language
Why Use C?
Static Keyword
Include Files
Freeing Memory
Topic Selection
Programming Judges
Anatomy of a Problem Description
Starter Problem: Food Lines
The Problem
Solving the Problem
Online Resources
Notes
1
HASH TABLES
Problem 1: Unique Snowflakes
The Problem
Simplifying the Problem
Solving the Core Problem
Solution 1: Pairwise Comparisons
Solution 2: Doing Less Work
Hash Tables
Hash Table Design
Why Use Hash Tables?
Problem 2: Login Mayhem
The Problem
Solution 1: Looking at All Passwords
Solution 2: Using a Hash Table
Problem 3: Spelling Check
The Problem
Thinking About Hash Tables
An Ad Hoc Solution
Summary
Notes
2
TREES AND RECURSION
Problem 1: Halloween Haul
The Problem
Binary Trees
Solving the Sample Instance
Representing Binary Trees
Collecting All the Candy
A Completely Different Solution
Walking the Minimum Number of Streets
Reading the Input
Why Use Recursion?
Problem 2: Descendant Distance
The Problem
Reading the Input
Number of Descendants from One Node
Number of Descendants from All Nodes
Sorting Nodes
Outputting the Information
The main Function
Summary
Notes
3
MEMOIZATION AND DYNAMIC PROGRAMMING
Problem 1: Burger Fervor
The Problem
Forming a Plan
Characterizing Optimal Solutions
Solution 1: Recursion
Solution 2: Memoization
Solution 3: Dynamic Programming
Memoization and Dynamic Programming
Step 1: Structure of Optimal Solutions
Step 2: Recursive Solution
Step 3: Memoization
Step 4: Dynamic Programming
Problem 2: Moneygrubbers
The Problem
Characterizing Optimal Solutions
Solution 1: Recursion
The main Function
Solution 2: Memoization
Problem 3: Hockey Rivalry
The Problem
About Rivalries
Characterizing Optimal Solutions
Solution 1: Recursion
Solution 2: Memoization
Solution 3: Dynamic Programming
A Space Optimization
Summary
Notes
4
ADVANCED MEMOIZATION AND DYNAMIC PROGRAMMING
Problem 1: The Jumper
The Problem
Working Through an Example
Solution 1: Backward Formulation
Solution 2: Forward Formulation
Problem 2: Ways to Build
The Problem
Working Through an Example
Solution 1: Using “Exactly” Subproblems
Solution 2: Adding More Subproblems
Summary
Notes
5
GRAPHS AND BREADTH-FIRST SEARCH
Problem 1: Knight Chase
The Problem
Moving Optimally
Best Knight Outcome
The Knight Flip-Flop
A Time Optimization
Graphs and BFS
What Are Graphs?
Graphs vs. Trees
BFS on Graphs
Graphs vs. Dynamic Programming
Problem 2: Rope Climb
The Problem
Solution 1: Finding the Moves
Solution 2: A Remodel
Problem 3: Book Translation
The Problem
Reading the Language Names
Building the Graph
The BFS
The Total Cost
Summary
Notes
6
SHORTEST PATHS IN WEIGHTED GRAPHS
Problem 1: Mice Maze
The Problem
Moving On from BFS
Finding Shortest Paths in Weighted Graphs
Building the Graph
Implementing Dijkstra’s Algorithm
Two Optimizations
Dijkstra’s Algorithm
Runtime of Dijkstra’s Algorithm
Negative-Weight Edges
Problem 2: Grandma Planner
The Problem
Adjacency Matrix
Building the Graph
Working Through a Weird Test Case
Task 1: Shortest Paths
Task 2: Number of Shortest Paths
Summary
Notes
7
BINARY SEARCH
Problem 1: Feeding Ants
The Problem
A New Flavor of Tree Problem
Reading the Input
Testing Feasibility
Searching for a Solution
Binary Search
Runtime of Binary Search
Determining Feasibility
Searching a Sorted Array
Problem 2: River Jump
The Problem
A Greedy Idea
Testing Feasibility
Searching for a Solution
Reading the Input
Problem 3: Living Quality
The Problem
Sorting Every Rectangle
Using Binary Search
Testing Feasibility
A Quicker Way to Test Feasibility
Problem 4: Cave Doors
The Problem
Solving a Subtask
Using Linear Search
Using Binary Search
Summary
Notes
8
HEAPS AND SEGMENT TREES
Problem 1: Supermarket Promotion
The Problem
Solution 1: Maximum and Minimum in an Array
Max-Heaps
Min-Heaps
Solution 2: Heaps
Heaps
Two More Applications
Choosing a Data Structure
Problem 2: Building Treaps
The Problem
Recursively Outputting Treaps
Sorting by Label
Solution 1: Recursion
Range Maximum Queries
Segment Trees
Solution 2: Segment Trees
Segment Trees
Problem 3: Two Sum
The Problem
Filling the Segment Tree
Querying the Segment Tree
Updating the Segment Tree
The main Function
Summary
Notes
9
UNION-FIND
Problem 1: Social Network
The Problem
Modeling as a Graph
Solution 1: BFS
Union-Find
Solution 2: Union-Find
Optimization 1: Union by Size
Optimization 2: Path Compression
Union-Find
Relationships: Three Requirements
Choosing Union-Find
Optimizations
Problem 2: Friends and Enemies
The Problem
Augmenting Union-Find
The main Function
Find and Union
SetFriends and SetEnemies
AreFriends and AreEnemies
Problem 3: Drawer Chore
The Problem
Equivalent Drawers
The main Function
Find and Union
Summary
Notes
10
RANDOMIZATION
Problem 1: Yōkan
The Problem
Randomly Choosing a Piece
Generating Random Numbers
Determining Number of Pieces
Guessing Flavors
How Many Attempts Do We Need?
Filling the Flavor Arrays
The main Function
Randomization
Monte Carlo Algorithms
Las Vegas Algorithms
Deterministic vs. Randomized Algorithms
Problem 2: Caps and Bottles
The Problem
Solving a Subtask
Solution 1: Recursion
Solution 2: Adding Randomization
Quicksort
Implementing Quicksort
Worst-Case and Expected Runtime
Summary
Notes
AFTERWORD
A
ALGORITHM RUNTIME
The Case for Timing . . . and Something Else
Big O Notation
Linear Time
Constant Time
Another Example
Quadratic Time
Big O in This Book
B
BECAUSE I CAN’T RESIST
Unique Snowflakes: Implicit Linked Lists
Burger Fervor: Reconstructing a Solution
Knight Chase: Encoding Moves
Dijkstra’s Algorithm: Using a Heap
Mice Maze: Tracing with Heaps
Mice Maze: Implementation with Heaps
Compressing Path Compression
Step 1: No More Ternary If
Step 2: Cleaner Assignment Operator
Step 3: Understand the Recursion
Caps and Bottles: In-Place Sorting
C
PROBLEM CREDITS
INDEX