Algorithmic Thinking: Unlock Your Programming Potential

FOREWORD
ABOUT THE AUTHOR
BRIEF CONTENTS
CONTENTS IN DETAIL
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
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: 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
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 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
CHAPTER 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
CHAPTER 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
CHAPTER 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
CHAPTER 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
CHAPTER 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
CHAPTER 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
CHAPTER 10: RANDOMIZATION
	Problem 1: Yokan
		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
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
	Caps and Bottles: In-Place Sorting
APPENDIX C: PROBLEM CREDITS
INDEX