Algorithmic Thinking

Algorithmic Thinking

by Dan Zingaro
Released December 2020
Publisher(s): No Starch Press
ISBN: 9781718500808

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

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?

Table of contents

  1. Cover Page
  2. Title Page
  3. Copyright Page
  4. Dedication
  5. About the Author
  6. About the Technical Reviewer
  7. BRIEF CONTENTS
  8. CONTENTS IN DETAIL
  9. FOREWORD
  10. ACKNOWLEDGMENTS
  11. INTRODUCTION
    1. Online Resources
    2. Who This Book Is For
    3. The Programming Language
    4. Topics
    5. Judges
    6. Anatomy of a Problem Description
    7. Problem: Food Lines
    8. Notes
  12. 1 HASH TABLES
    1. Problem 1: Unique Snowflakes
    2. Hash Tables
    3. Problem 2: Compound Words
    4. Problem 3: Spelling Check: Deleting a Letter
    5. Summary
    6. Notes
  13. 2 TREES AND RECURSION
    1. Problem 1: Halloween Haul
    2. Why Use Recursion?
    3. Problem 2: Descendant Distance
    4. Summary
    5. Notes
  14. 3 MEMOIZATION AND DYNAMIC PROGRAMMING
    1. Problem 1: Burger Fervor
    2. Memoization and Dynamic Programming
    3. Problem 2: Moneygrubbers
    4. Problem 3: Hockey Rivalry
    5. Problem 4: Ways to Pass
    6. Summary
    7. Notes
  15. 4 GRAPHS AND BREADTH-FIRST SEARCH
    1. Problem 1: Knight Chase
    2. Graphs and BFS
    3. Problem 2: Rope Climb
    4. Problem 3: Book Translation
    5. Summary
    6. Notes
  16. 5 SHORTEST PATHS IN WEIGHTED GRAPHS
    1. Problem 1: Mice Maze
    2. Dijkstra’s Algorithm
    3. Problem 2: Grandma Planner
    4. Summary
    5. Notes
  17. 6 BINARY SEARCH
    1. Problem 1: Feeding Ants
    2. Binary Search
    3. Problem 2: River Jump
    4. Problem 3: Living Quality
    5. Problem 4: Cave Doors
    6. Summary
    7. Notes
  18. 7 HEAPS AND SEGMENT TREES
    1. Problem 1: Supermarket Promotion
    2. Heaps
    3. Problem 2: Building Treaps
    4. Segment Trees
    5. Problem 3: Two Sum
    6. Summary
    7. Notes
  19. 8 UNION-FIND
    1. Problem 1: Social Network
    2. Union-Find
    3. Problem 2: Friends and Enemies
    4. Problem 3: Drawer Chore
    5. Summary
    6. Notes
  20. AFTERWORD
  21. A ALGORITHM RUNTIME
    1. The Case for Timing ... and Something Else
    2. Big O Notation
  22. 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
    5. Compressing Path Compression
  23. C PROBLEM CREDITS
  24. INDEX

Product information

  • Title: Algorithmic Thinking
  • Author(s): Dan Zingaro
  • Release date: December 2020
  • Publisher(s): No Starch Press
  • ISBN: 9781718500808