Algorithmic Thinking: A Problem-Based Introduction

Brief Contents
Contents in Detail
Foreword
Acknowledgments
Introduction
	Online Resources
	Who This Book Is For
	The Programming Language
		Why Use C?
		Static Keyword
		Include Files
		Freeing Memory
	Topics
	Judges
	Anatomy of a Problem Description
	Problem: Food Lines
		The Problem
		Solving the Problem
	Notes
Chapter 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: Compound Words
		The Problem
		Identifying Compound Words
		Solution
	Problem 3: Spelling Check: Deleting a Letter
		The Problem
		Thinking About Hash Tables
		An Ad Hoc Solution
	Summary
	Notes
Chapter 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
Chapter 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 Solution
		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
	Problem 4: Ways to Pass
		The Problem
		Solution: Memoization
	Summary
	Notes
Chapter 4: 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
	Problem 2: Rope Climb
		The Problem
		Solution 1: Finding the Moves
		Solution 2: A Remodel
	Problem 3: Book Translation
		The Problem
		Building the Graph
		The BFS
		Total Cost
	Summary
	Notes
Chapter 5: Shortest Paths in Weighted Graphs
	Problem 1: Mice Maze
		The Problem
		Moving On from BFS
		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
		Weird Paths
		Task 1: Shortest Paths
		Task 2: Number of Shortest Paths
	Summary
	Notes
Chapter 6: 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
		Binary Search
		Testing Feasibility
		Testing Feasibility More Quickly
	Problem 4: Cave Doors
		The Problem
		Solving a Subtask
		Using a Linear Search
		Using Binary Search
	Summary
	Notes
Chapter 7: 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
Chapter 8: 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
		Augmentation: Enemies
		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
Afterword
Appendix 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
Appendix 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
Appendix C: Problem Credits
Index