book

Algorithmic Thinking, 2nd Edition

Name: Algorithmic Thinking, 2nd Edition
Author: Daniel Zingaro
ISBN: 9781718503229

by Daniel Zingaro

January 2024

Intermediate to advanced

480 pages

12h 36m

English

No Starch Press

Read now

Unlock full access

Cover Page
Title Page
Copyright Page
Dedication Page
About the Author
About the Technical Reviewer
About the First Edition Technical Reviewer
BRIEF CONTENTS
CONTENTS IN DETAIL
FOREWORD

ACKNOWLEDGMENTS
INTRODUCTION
What We’ll DoNew to the Second EditionWho This Book Is ForOur Programming LanguageWhy Use C?Static KeywordInclude FilesFreeing MemoryTopic SelectionProgramming JudgesAnatomy of a Problem DescriptionStarter Problem: Food LinesThe ProblemSolving the ProblemOnline ResourcesNotes
1 HASH TABLES
Problem 1: Unique SnowflakesThe ProblemSimplifying the ProblemSolving the Core ProblemSolution 1: Pairwise ComparisonsSolution 2: Doing Less WorkHash TablesHash Table DesignWhy Use Hash Tables?Problem 2: Login MayhemThe ProblemSolution 1: Looking at All PasswordsSolution 2: Using a Hash TableProblem 3: Spelling CheckThe ProblemThinking About Hash TablesAn Ad Hoc SolutionSummaryNotes
2 TREES AND RECURSION
Problem 1: Halloween HaulThe ProblemBinary TreesSolving the Sample InstanceRepresenting Binary TreesCollecting All the CandyA Completely Different SolutionWalking the Minimum Number of StreetsReading the InputWhy Use Recursion?Problem 2: Descendant DistanceThe ProblemReading the InputNumber of Descendants from One NodeNumber of Descendants from All NodesSorting NodesOutputting the InformationThe main FunctionSummaryNotes
3 MEMOIZATION AND DYNAMIC PROGRAMMING
Problem 1: Burger FervorThe ProblemForming a PlanCharacterizing Optimal SolutionsSolution 1: RecursionSolution 2: MemoizationSolution 3: Dynamic ProgrammingMemoization and Dynamic ProgrammingStep 1: Structure of Optimal SolutionsStep 2: Recursive SolutionStep 3: MemoizationStep 4: Dynamic ProgrammingProblem 2: MoneygrubbersThe ProblemCharacterizing Optimal SolutionsSolution 1: RecursionThe main FunctionSolution 2: MemoizationProblem 3: Hockey RivalryThe ProblemAbout RivalriesCharacterizing Optimal SolutionsSolution 1: RecursionSolution 2: MemoizationSolution 3: Dynamic ProgrammingA Space OptimizationSummaryNotes
4 ADVANCED MEMOIZATION AND DYNAMIC PROGRAMMING
Problem 1: The JumperThe ProblemWorking Through an ExampleSolution 1: Backward FormulationSolution 2: Forward FormulationProblem 2: Ways to BuildThe ProblemWorking Through an ExampleSolution 1: Using “Exactly” SubproblemsSolution 2: Adding More SubproblemsSummaryNotes
5 GRAPHS AND BREADTH-FIRST SEARCH
Problem 1: Knight ChaseThe ProblemMoving OptimallyBest Knight OutcomeThe Knight Flip-FlopA Time OptimizationGraphs and BFSWhat Are Graphs?Graphs vs. TreesBFS on GraphsGraphs vs. Dynamic ProgrammingProblem 2: Rope ClimbThe ProblemSolution 1: Finding the MovesSolution 2: A RemodelProblem 3: Book TranslationThe ProblemReading the Language NamesBuilding the GraphThe BFSThe Total CostSummaryNotes
6 SHORTEST PATHS IN WEIGHTED GRAPHS
Problem 1: Mice MazeThe ProblemMoving On from BFSFinding Shortest Paths in Weighted GraphsBuilding the GraphImplementing Dijkstra’s AlgorithmTwo OptimizationsDijkstra’s AlgorithmRuntime of Dijkstra’s AlgorithmNegative-Weight EdgesProblem 2: Grandma PlannerThe ProblemAdjacency MatrixBuilding the GraphWorking Through a Weird Test CaseTask 1: Shortest PathsTask 2: Number of Shortest PathsSummaryNotes
7 BINARY SEARCH
Problem 1: Feeding AntsThe ProblemA New Flavor of Tree ProblemReading the InputTesting FeasibilitySearching for a SolutionBinary SearchRuntime of Binary SearchDetermining FeasibilitySearching a Sorted ArrayProblem 2: River JumpThe ProblemA Greedy IdeaTesting FeasibilitySearching for a SolutionReading the InputProblem 3: Living QualityThe ProblemSorting Every RectangleUsing Binary SearchTesting FeasibilityA Quicker Way to Test FeasibilityProblem 4: Cave DoorsThe ProblemSolving a SubtaskUsing Linear SearchUsing Binary SearchSummaryNotes
8 HEAPS AND SEGMENT TREES
Problem 1: Supermarket PromotionThe ProblemSolution 1: Maximum and Minimum in an ArrayMax-HeapsMin-HeapsSolution 2: HeapsHeapsTwo More ApplicationsChoosing a Data StructureProblem 2: Building TreapsThe ProblemRecursively Outputting TreapsSorting by LabelSolution 1: RecursionRange Maximum QueriesSegment TreesSolution 2: Segment TreesSegment TreesProblem 3: Two SumThe ProblemFilling the Segment TreeQuerying the Segment TreeUpdating the Segment TreeThe main FunctionSummaryNotes
9 UNION-FIND
Problem 1: Social NetworkThe ProblemModeling as a GraphSolution 1: BFSUnion-FindSolution 2: Union-FindOptimization 1: Union by SizeOptimization 2: Path CompressionUnion-FindRelationships: Three RequirementsChoosing Union-FindOptimizationsProblem 2: Friends and EnemiesThe ProblemAugmenting Union-FindThe main FunctionFind and UnionSetFriends and SetEnemiesAreFriends and AreEnemiesProblem 3: Drawer ChoreThe ProblemEquivalent DrawersThe main FunctionFind and UnionSummaryNotes
10 RANDOMIZATION
Problem 1: YōkanThe ProblemRandomly Choosing a PieceGenerating Random NumbersDetermining Number of PiecesGuessing FlavorsHow Many Attempts Do We Need?Filling the Flavor ArraysThe main FunctionRandomizationMonte Carlo AlgorithmsLas Vegas AlgorithmsDeterministic vs. Randomized AlgorithmsProblem 2: Caps and BottlesThe ProblemSolving a SubtaskSolution 1: RecursionSolution 2: Adding RandomizationQuicksortImplementing QuicksortWorst-Case and Expected RuntimeSummaryNotes
AFTERWORD
A ALGORITHM RUNTIME
The Case for Timing . . . and Something ElseBig O NotationLinear TimeConstant TimeAnother ExampleQuadratic TimeBig O in This Book
B BECAUSE I CAN’T RESIST
Unique Snowflakes: Implicit Linked ListsBurger Fervor: Reconstructing a SolutionKnight Chase: Encoding MovesDijkstra’s Algorithm: Using a HeapMice Maze: Tracing with HeapsMice Maze: Implementation with HeapsCompressing Path CompressionStep 1: No More Ternary IfStep 2: Cleaner Assignment OperatorStep 3: Understand the RecursionCaps and Bottles: In-Place Sorting
C PROBLEM CREDITS
INDEX

Content preview from Algorithmic Thinking, 2nd Edition

CONTENTS IN DETAIL

New to the Second Edition

Who This Book Is For

Our Programming Language

Anatomy of a Problem Description

Starter Problem: Food Lines

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: Login Mayhem

The Problem

Solution 1: Looking at All Passwords

Solution 2: Using a Hash Table

Problem 3: Spelling Check

The Problem

Thinking About Hash Tables

An Ad Hoc Solution ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Publisher Resources

ISBN: 9781098168766Errata Page

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Algorithmic Thinking, 2nd Edition

by Daniel Zingaro

CONTENTS IN DETAIL

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.