Algorithmic Thinking: A Problem-Based Introduction

by Daniel Zingaro

Overview

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?

Product Details

ISBN-13:	9781718500808
Publisher:	No Starch Press
Publication date:	12/15/2020
Pages:	408
Product dimensions:	9.10(w) x 6.90(h) x 1.10(d)

About the Author

Dr. Daniel Zingaro is an award-winning Assistant Professor of Mathematical and Computational Sciences at the University of Toronto Mississauga, where he is well known for his uniquely interactive approach to teaching, and internationally recognized for his expertise in Active Learning.

Table of Contents

Foreword xv

Acknowledgments xvii

Introduction xix

Online Resources xx

Who This Book Is For xx

The Programming Language xx

Why Use C? xxi

Static Keyword xxi

Include Files xxii

Freeing Memory xxii

Topics xxii

Judges xxiii

Anatomy of a Problem Description xxv

Problem: Food Lines xxvi

The Problem xxvi

Solving the Problem xxvii

Notes xxix

1 Hash Tables 1

Problem 1: Unique Snowflakes 1

The Problem 2

Simplifying the Problem 3

Solving the Core Problem 4

Solution 1: Pairwise Comparisons 7

Solution 2: Doing Less Work 11

Hash Tables 16

Hash Table Design 16

Why Use Hash Tables? 19

Problem 2: Compound Words 19

The Problem 19

Identifying Compound Words 20

Solution 20

Problem 3: Spelling Check: Deleting a Letter 24

The Problem 24

Thinking About Hash Tables 25

An Ad Hoc Solution 27

Summary 30

Notes 30

2 Trees and Recursion 31

Problem 1: Halloween Haul 31

The Problem 32

Binary Trees 33

Solving the Sample Instance 35

Representing Binary Trees 35

Collecting All the Candy 39

A Completely Different Solution 45

Walking the Minimum Number of Streets 50

Reading the Input 53

Why Use Recursion? 59

Problem 2: Descendant Distance 59

The Problem 59

Reading the Input 62

Number of Descendants from One Node 65

Number of Descendants from All Nodes 67

Sorting Nodes 67

Outputting the Information 68

The main Function 69

Summary 70

Notes 70

3 Memoization and Dynamic Programming 71

Problem 1: Burger Fervor 72

The Problem 72

Forming a Plan 72

Characterizing Optimal Solutions 74

Solution 1: Recursion 75

Solution 2: Memoization 80

Solution 3: Dynamic Programming 85

Memoization and Dynamic Programming 88

Step 1: Structure of Optimal Solutions 88

Step 2: Recursive Solution 89

Step 3: Memoization 90

Step 4: Dynamic Programming 90

Problem 2: Moneygrubbers 91

The Problem 91

Characterizing Optimal Solutions 92

Solution 1: Recursion 94

The main Function 98

Solution 2: Memoization 100

Problem 3: Hockey Rivalry 102

The Problem 102

About Rivalries 103

Characterizing Optimal Solutions 105

Solution 1: Recursion 107

Solution 2: Memoization 110

Solution 3: Dynamic Programming 111

A Space Optimization 114

Problem 4: Ways to Pass 115

The Problem 116

Solution: Memoization 116

Summary 118

Notes 118

4 Graphs and Breadth-First Search 119

Problem 1: Knight Chase 119

The Problem 120

Moving Optimally 122

Best Knight Outcome 131

The Knight Flip-Flop 133

A Time Optimization 136

Graphs and BFS 137

What Are Graphs? 137

Graphs vs. Trees 138

BFS on Graphs 140

Problem 2: Rope Climb 141

The Problem 141

Solution 1: Finding the Moves 142

Solution 2: A Remodel 147

Problem 3: Book Translation 155

The Problem 155

Building the Graph 156

The BFS 160

Total Cost 162

Summary 162

Notes 163

5 Shortest Paths in Weighted Graphs 165

Problem 1: Mice Maze 166

The Problem 166

Moving On from BFS 166

Shortest Paths in Weighted Graphs 168

Building the Graph 171

Implementing Dijkstra's Algorithm 173

Two Optimizations 175

Dijkstra's Algorithm 177

Runtime of Dijkstra's Algorithm 177

Negative-weight Edges 178

Problem 2: Grandma Planner 180

The Problem 180

Adjacency Matrix 181

Building the Graph 182

Weird Paths 184

Task 1: Shortest Paths 187

Task 2: Number of Shortest Paths 189

Summary 196

Notes 196

6 Binary Search 197

Problem 1: Feeding Ants 197

The Problem 198

A New Flavor of Tree Problem 199

Reading the Input 201

Testing Feasibility 203

Searching for a Solution 205

Binary Search 206

Runtime of Binary Search 207

Determining Feasibility 208

Searching a Sorted Array 208

Problem 2: River Jump 209

The Problem 209

A Greedy Idea 210

Testing Feasibility 212

Searching for a Solution 216

Reading the Input 219

Problem 3: Living Quality 220

The Problem 220

Sorting Every Rectangle 221

Binary Search 224

Testing Feasibility 225

Testing Feasibility More Quickly 227

Problem 4: Cave Doors 233

The Problem 233

Solving a Subtask 234

Using a Linear Search 236

Using Binary Search 238

Summary 240

Notes 241

7 Heaps and Segment Trees 243

Problem 1: Supermarket Promotion 243

The Problem 243

Solution 1: Maximum and Minimum in an Array 244

Max-Heaps 248

Min-Heaps 259

Solution 2: Heaps 261

Heaps 263

Two More Applications 264

Choosing a Data Structure 265

Problem 2: Building Treaps 265

The Problem 265

Recursively Outputting Treaps 267

Sorting by Label 268

Solution 1: Recursion 269

Range Maximum Queries 272

Segment Trees 273

Solution 2: Segment Trees 281

Segment Trees 282

Problem 3: Two Sum 283

The Problem 283

Filling the Segment Tree 284

Querying the Segment Tree 288

Updating the Segment Tree 290

The Main Function 293

Summary 294

Notes 294

8 Problem 1: Social Network 296

The Problem 296

Modeling as a Graph 297

Solution 1: BFS 300

Union-Find 304

Solution 2: Union-Find 307

Optimization 1: Union by Size 310

Optimization 2: Path Compression 314

Union-Find 316

Relationships: Three Requirements 316

Choosing Union-Find 317

Optimizations 317

Problem 2: Friends and Enemies 317

The Problem 318

Augmentation: Enemies 319

The main Function 323

Find and Union 324

SetFriends and SetEnemies 325

AreFriends and AreEnemies 327

Problem 3: Drawer Chore 328

The Problem 328

Equivalent Drawers 329

The main Function 334

Find and Union 335

Summary 336

Notes 337

Afterword 339

A Algorithm Runtime 341

The Case for Timing … and Something Else 341

Big O Notation 343

Linear Time 343

Constant Time 344

Another Example 345

Quadratic Time 345

Big O in This Book 346

B Because I Can't Resist 347

Unique Snowflakes: Implicit Linked Lists 347

Burger Fervor: Reconstructing a Solution 350

Knight Chase: Encoding Moves 352

Dijkstra's Algorithm: Using a Heap 354

Mice Maze: Tracing with Heaps 354

Mice Maze: Implementation with Heaps 357

Compressing Path Compression 358

Step 1: No More Ternary If 358

Step 2: Cleaner Assignment Operator 359

Step 3: Understand the Recursion 360

C Problem Credits 361

Index 365

Editorial Reviews

A good choice for anyone who needs to understand and implement algorithms.”
—RedGreenCode

“With Zingaro as a tutor by your side, you'll learn, through practice on challenging competition problems, a repeatable process for figuring out and deftly applying the most appropriate algorithmic tools for the job. You'll learn it all from a book that exudes clarity, humor, and just the right dose of Canadian pride. Happy problem-solving!”
—Dr. Tim Roughgarden, Professor of Computer Science at Columbia University

"A clear and engaging text . . . By presenting problems first and their algorithm/data structure solutions later, it shows us exactly why those solutions are useful and how they fit into the big picture. . . . Far too many textbooks present solutions fully-formed with no mention of the dead ends and too-complicated solutions you’d hit along the way. But Algorithmic Thinking takes you from the initial idea to the final breakthrough, setbacks and all. Problem solving is a raw, real journey, and this book captures its spirit perfectly. I highly recommend it."
—Ava Pun, medal winner in the International Olympiad in Informatics Programming Competition

"The strength of the book is that the process of discovering and improving algorithms is described in detail and various different approaches are analyzed. Compared to traditional textbooks, there are also interesting topics that are not usually covered . . . Overall, the book is clearly written, the topics are well-chosen, and the book is a good introduction to some important competitive programming techniques."
—Antti Laaksonen, Olympiads in Informatics

From the Publisher