A hands-on, problem-based introduction to building algorithms and data structures to solve problems with a computer.
Algorithmic Thinking will teach you how to solve challenging programming problems and design your own algorithms. Daniel Zingaro, a master teacher, draws his examples from world-class programming competitions like USACO and IOI. You'll learn how to classify problems, choose data structures, and identify appropriate algorithms. You'll also learn how your choice of data structure, whether a hash table, heap, or tree, can affect runtime and speed up your algorithms; and how to adopt powerful strategies like recursion, dynamic programming, and binary search to solve challenging problems.
Line-by-line breakdowns of the code will teach you how to use algorithms and data structures like:
• The breadth-first search algorithm to find the optimal way to play a board game or find the best way to translate a book
• Dijkstra's algorithm to determine how many mice can exit a maze or the number of fastest routes between two locations
• The union-find data structure to answer questions about connections in a social network or determine who are friends or enemies
• The heap data structure to determine the amount of money given away in a promotion
• The hash-table data structure to determine whether snowflakes are unique or identify compound words in a dictionary
NOTE: Each problem in this book is available on a programming-judge website. You'll find the site's URL and problem ID in the description. What's better than a free correctness check?
Author(s): Daniel Zingaro
Edition: 1
Publisher: No Starch Press
Year: 2020
Language: English
Commentary: Vector PDF
Pages: 408
City: San Francisco, CA
Tags: Algorithms; Data Structures; Recursion; Dynamic Programming; C; Graph Algorithms; Trees; Heaps; Hashing; Memoization; Search Algorithms; Dijkstra's Algorithm; Segment Trees; Union-Find Trees
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
