Algorithmic Thinking : A Problem-Based Introduction

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? Brief Contents Contents in Detail Foreword Acknowledgments Introduction Chapter 1: Hash Tables Chapter 2: Trees and Recursion Chapter 3: Memoization and Dynamic Programming Chapter 4: Graphs and Breadth-First Search Chapter 5: Shortest Paths in Weighted Graphs Chapter 6: Binary Search Chapter 7: Heaps and Segment Trees Chapter 8: Union-Find Afterword Appendix A: Algorithm Runtime Appendix B: Because I Can't Resist Appendix C: Problem Credits Index 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 A Hands-on, Problem-based Introduction To Building Algorithms And Data Structures To Solve Problems With A Computer. Programming Is About Using A Computer To Solve Problems, And Algorithms And Data Structures Are The Building Blocks Of Computer Programs. For Each Problem That A Programmer Wants To Solve, They Employ An Algorithm: A Sequence Of Steps For Solving The Problem. Many Books Teach Algorithms Independently Of Specific Problems, But This Book Uses Careful Explanations, Examples, And Arguments, Rather Than Formal Mathematics And Proofs Which Make It Difficult For The Reader To Connect What They Are Learning To What They Can Do With That Learning. Algorithmic Thinking: A Problem-based Introduction Teaches The Reader To Use The Best Algorithms And Data Structures For A Given Situation By Walking Them Through Solving Real-world Problems Pulled From International Programming Competitions, Such As How To Determine Whether Snowflakes Are Unique; How To Win A Game In The Minimum Number Of Moves; How To Find The Number Of Ways To Get To Someone's House; How To Escape A Cave In As Few Steps As Possible; And So On.readers Tackle Challenging Topics Like Recursion, Dynamic Programming, Graphs, Greedy Algorithms, Heaps, Hash Tables, Segment Trees, And Other Data Structures For Efficiently Handling Data. The Book Contains No Pseudocode: All Code Is Written In C And Is Thoroughly Explained In The Text (c Is A De Facto Programming Language For Programming Competitions). Zingaro Also Shows How Several Problems Can Be Reduced To Algorithms On Graphs. By The End Of The Book, Readers Should Understand The Importance Of Modeling, How To Carefully Work Through A Problem, And Why It Pays To Organize Data Using Data Structures. "An introduction to solving problems with algorithms and data structures, using competitive programming examples. Topics covered include recursion, dynamic programming, graphs, greedy algorithms, heaps, hash tables, segment trees, and other data structures for efficiently handling data"-Provided by publisher"-- Provided by publisher