Algorithmic Thinking, 2nd Edition

Algorithmic Thinking, 2nd Edition

by Daniel Zingaro
Released January 2024
Publisher(s): No Starch Press
ISBN: 9781718503229

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Are you hitting a wall with data structures and algorithms? Whether you’re a student prepping for coding interviews or an independent learner, this book is your essential guide to efficient problem-solving in programming.

UNLOCK THE POWER OF DATA STRUCTURES & ALGORITHMS:

Learn the intricacies of hash tables, recursion, dynamic programming, trees, graphs, and heaps. Become proficient in choosing and implementing the best solutions for any coding challenge.

REAL-WORLD, COMPETITION-PROVEN CODE EXAMPLES:

The programs and challenges in this book aren’t just theoretical—they’re drawn from real programming competitions. Train with problems that have tested and honed the skills of coders around the world.

GET INTERVIEW-READY:

Prepare yourself for coding interviews with practice exercises that help you think algorithmically, weigh different solutions, and implement the best choices efficiently.

WRITTEN IN C, USEFUL ACROSS LANGUAGES:

The code examples are written in C and designed for clarity and accessibility to those familiar with languages like C++, Java, or Python. If you need help with the C code, no problem: We’ve got recommended reading, too.

Algorithmic Thinking is the complete package, providing the solid foundation you need to elevate your coding skills to the next level.

Publisher resources

View/Submit Errata

Table of contents

  1. Cover Page
  2. Title Page
  3. Copyright Page
  4. Dedication Page
  5. About the Author
  6. About the Technical Reviewer
  7. About the First Edition Technical Reviewer
  8. BRIEF CONTENTS
  9. CONTENTS IN DETAIL
  10. FOREWORD
  11. ACKNOWLEDGMENTS
  12. INTRODUCTION
    1. What We’ll Do
    2. New to the Second Edition
    3. Who This Book Is For
    4. Our Programming Language
      1. Why Use C?
      2. Static Keyword
      3. Include Files
      4. Freeing Memory
    5. Topic Selection
    6. Programming Judges
    7. Anatomy of a Problem Description
    8. Starter Problem: Food Lines
      1. The Problem
      2. Solving the Problem
    9. Online Resources
    10. Notes
  13. 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
      5. Solution 2: Doing Less Work
    2. Hash Tables
      1. Hash Table Design
      2. Why Use Hash Tables?
    3. Problem 2: Login Mayhem
      1. The Problem
      2. Solution 1: Looking at All Passwords
      3. Solution 2: Using a Hash Table
    4. Problem 3: Spelling Check
      1. The Problem
      2. Thinking About Hash Tables
      3. An Ad Hoc Solution
    5. Summary
    6. Notes
  14. 2 TREES AND RECURSION
    1. Problem 1: Halloween Haul
      1. The Problem
      2. Binary Trees
      3. Solving the Sample Instance
      4. Representing Binary Trees
      5. Collecting All the Candy
      6. A Completely Different Solution
      7. Walking the Minimum Number of Streets
      8. Reading the Input
    2. Why Use Recursion?
    3. Problem 2: Descendant Distance
      1. The Problem
      2. Reading the Input
      3. Number of Descendants from One Node
      4. Number of Descendants from All Nodes
      5. Sorting Nodes
      6. Outputting the Information
      7. The main Function
    4. Summary
    5. Notes
  15. 3 MEMOIZATION AND DYNAMIC PROGRAMMING
    1. Problem 1: Burger Fervor
      1. The Problem
      2. Forming a Plan
      3. Characterizing Optimal Solutions
      4. Solution 1: Recursion
      5. Solution 2: Memoization
      6. Solution 3: Dynamic Programming
    2. Memoization and Dynamic Programming
      1. Step 1: Structure of Optimal Solutions
      2. Step 2: Recursive Solution
      3. Step 3: Memoization
      4. Step 4: Dynamic Programming
    3. Problem 2: Moneygrubbers
      1. The Problem
      2. Characterizing Optimal Solutions
      3. Solution 1: Recursion
      4. The main Function
      5. Solution 2: Memoization
    4. Problem 3: Hockey Rivalry
      1. The Problem
      2. About Rivalries
      3. Characterizing Optimal Solutions
      4. Solution 1: Recursion
      5. Solution 2: Memoization
      6. Solution 3: Dynamic Programming
      7. A Space Optimization
    5. Summary
    6. Notes
  16. 4 ADVANCED MEMOIZATION AND DYNAMIC PROGRAMMING
    1. Problem 1: The Jumper
      1. The Problem
      2. Working Through an Example
      3. Solution 1: Backward Formulation
      4. Solution 2: Forward Formulation
    2. Problem 2: Ways to Build
      1. The Problem
      2. Working Through an Example
      3. Solution 1: Using “Exactly” Subproblems
      4. Solution 2: Adding More Subproblems
    3. Summary
    4. Notes
  17. 5 GRAPHS AND BREADTH-FIRST SEARCH
    1. Problem 1: Knight Chase
      1. The Problem
      2. Moving Optimally
      3. Best Knight Outcome
      4. The Knight Flip-Flop
      5. A Time Optimization
    2. Graphs and BFS
      1. What Are Graphs?
      2. Graphs vs. Trees
      3. BFS on Graphs
      4. Graphs vs. Dynamic Programming
    3. Problem 2: Rope Climb
      1. The Problem
      2. Solution 1: Finding the Moves
      3. Solution 2: A Remodel
    4. Problem 3: Book Translation
      1. The Problem
      2. Reading the Language Names
      3. Building the Graph
      4. The BFS
      5. The Total Cost
    5. Summary
    6. Notes
  18. 6 SHORTEST PATHS IN WEIGHTED GRAPHS
    1. Problem 1: Mice Maze
      1. The Problem
      2. Moving On from BFS
      3. Finding Shortest Paths in Weighted Graphs
      4. Building the Graph
      5. Implementing Dijkstra’s Algorithm
      6. Two Optimizations
    2. Dijkstra’s Algorithm
      1. Runtime of Dijkstra’s Algorithm
      2. Negative-Weight Edges
    3. Problem 2: Grandma Planner
      1. The Problem
      2. Adjacency Matrix
      3. Building the Graph
      4. Working Through a Weird Test Case
      5. Task 1: Shortest Paths
      6. Task 2: Number of Shortest Paths
    4. Summary
    5. Notes
  19. 7 BINARY SEARCH
    1. Problem 1: Feeding Ants
      1. The Problem
      2. A New Flavor of Tree Problem
      3. Reading the Input
      4. Testing Feasibility
      5. Searching for a Solution
    2. Binary Search
      1. Runtime of Binary Search
      2. Determining Feasibility
      3. Searching a Sorted Array
    3. Problem 2: River Jump
      1. The Problem
      2. A Greedy Idea
      3. Testing Feasibility
      4. Searching for a Solution
      5. Reading the Input
    4. Problem 3: Living Quality
      1. The Problem
      2. Sorting Every Rectangle
      3. Using Binary Search
      4. Testing Feasibility
      5. A Quicker Way to Test Feasibility
    5. Problem 4: Cave Doors
      1. The Problem
      2. Solving a Subtask
      3. Using Linear Search
      4. Using Binary Search
    6. Summary
    7. Notes
  20. 8 HEAPS AND SEGMENT TREES
    1. Problem 1: Supermarket Promotion
      1. The Problem
      2. Solution 1: Maximum and Minimum in an Array
      3. Max-Heaps
      4. Min-Heaps
      5. Solution 2: Heaps
    2. Heaps
      1. Two More Applications
      2. Choosing a Data Structure
    3. Problem 2: Building Treaps
      1. The Problem
      2. Recursively Outputting Treaps
      3. Sorting by Label
      4. Solution 1: Recursion
      5. Range Maximum Queries
      6. Segment Trees
      7. Solution 2: Segment Trees
    4. Segment Trees
    5. Problem 3: Two Sum
      1. The Problem
      2. Filling the Segment Tree
      3. Querying the Segment Tree
      4. Updating the Segment Tree
      5. The main Function
    6. Summary
    7. Notes
  21. 9 UNION-FIND
    1. Problem 1: Social Network
      1. The Problem
      2. Modeling as a Graph
      3. Solution 1: BFS
      4. Union-Find
      5. Solution 2: Union-Find
      6. Optimization 1: Union by Size
      7. Optimization 2: Path Compression
    2. Union-Find
      1. Relationships: Three Requirements
      2. Choosing Union-Find
      3. Optimizations
    3. Problem 2: Friends and Enemies
      1. The Problem
      2. Augmenting Union-Find
      3. The main Function
      4. Find and Union
      5. SetFriends and SetEnemies
      6. AreFriends and AreEnemies
    4. Problem 3: Drawer Chore
      1. The Problem
      2. Equivalent Drawers
      3. The main Function
      4. Find and Union
    5. Summary
    6. Notes
  22. 10 RANDOMIZATION
    1. Problem 1: Yōkan
      1. The Problem
      2. Randomly Choosing a Piece
      3. Generating Random Numbers
      4. Determining Number of Pieces
      5. Guessing Flavors
      6. How Many Attempts Do We Need?
      7. Filling the Flavor Arrays
      8. The main Function
    2. Randomization
      1. Monte Carlo Algorithms
      2. Las Vegas Algorithms
      3. Deterministic vs. Randomized Algorithms
    3. Problem 2: Caps and Bottles
      1. The Problem
      2. Solving a Subtask
      3. Solution 1: Recursion
      4. Solution 2: Adding Randomization
    4. Quicksort
      1. Implementing Quicksort
      2. Worst-Case and Expected Runtime
    5. Summary
    6. Notes
  23. AFTERWORD
  24. A ALGORITHM RUNTIME
    1. The Case for Timing . . . and Something Else
    2. Big O Notation
      1. Linear Time
      2. Constant Time
      3. Another Example
      4. Quadratic Time
      5. Big O in This Book
  25. B BECAUSE I CAN’T RESIST
    1. Unique Snowflakes: Implicit Linked Lists
    2. Burger Fervor: Reconstructing a Solution
    3. Knight Chase: Encoding Moves
    4. Dijkstra’s Algorithm: Using a Heap
      1. Mice Maze: Tracing with Heaps
      2. Mice Maze: Implementation with Heaps
    5. Compressing Path Compression
      1. Step 1: No More Ternary If
      2. Step 2: Cleaner Assignment Operator
      3. Step 3: Understand the Recursion
    6. Caps and Bottles: In-Place Sorting
  26. C PROBLEM CREDITS
  27. INDEX

Product information

  • Title: Algorithmic Thinking, 2nd Edition
  • Author(s): Daniel Zingaro
  • Release date: January 2024
  • Publisher(s): No Starch Press
  • ISBN: 9781718503229