Start free trial
Trending New Genres Authors
EnglishEnglish
EspañolSpanish
简体中文Chinese
繁體中文Chinese (Traditional)
FrançaisFrench
DeutschGerman
日本語Japanese
PortuguêsPortuguese
ItalianoItalian
한국어Korean
РусскийRussian
NederlandsDutch
العربيةArabic
PolskiPolish
हिन्दीHindi
Tiếng ViệtVietnamese
SvenskaSwedish
ΕλληνικάGreek
TürkçeTurkish
ไทยThai
ČeštinaCzech
RomânăRomanian
MagyarHungarian
УкраїнськаUkrainian
IndonesiaIndonesian
DanskDanish
SuomiFinnish
БългарскиBulgarian
עבריתHebrew
NorskNorwegian
HrvatskiCroatian
CatalàCatalan
SlovenčinaSlovak
LietuviųLithuanian
SlovenščinaSlovenian
СрпскиSerbian
EestiEstonian
LatviešuLatvian
فارسیPersian
മലയാളംMalayalam
தமிழ்Tamil
اردوUrdu
Searching...
SoBrief
Once Upon an Algorithm

Once Upon an Algorithm

How Stories Explain Computing
Learn the ideas behind algorithms, data structures, and code through stories you already know.
by Martin Erwig 2017 336 pages
3.63
265 ratings
Listen
Immersive
V2.3
Amazon Kindle Audible
Try Full Access for 3 Days
Unlock listening & more!
Continue

Key Takeaways

See computation wherever a repeatable method transforms a meaningful representation

Stories make computing visible. The book’s central move is to find computation in familiar actions and stories, not only in electronics. Hansel and Gretel’s pebbles, for instance, stand for locations along a path home. Following them changes the children’s position one step at a time, turning a dangerous situation into a safe one.

A method is not its execution. An algorithm is a finite, precise description of steps; a computation happens when a person, machine, or other capable agent follows those steps. The distinction makes computing easier to recognize: a recipe is an algorithm, while actually preparing the meal is a computation. The steps must be systematic, and their effects must mean something in the problem being solved.

Analysis

The story-based approach treats computational thinking as a way to inspect ordinary processes: What is represented, what changes, and which steps can be repeated? That resembles systems thinking in fields such as biology, where researchers trace how components and interactions produce an outcome. The framing is powerful precisely because it does not require a laptop. Its limit is equally important: describing a process algorithmically does not explain every human choice within it. Creative insight may invent a method, while computation follows one.

Separate the algorithm from its execution, then measure what each costs

Parameters make methods reusable. A parameter is a named placeholder for an input. A coffee-making method can use the number of cups as a parameter, so one description works for different quantities. This is what lets an algorithm solve a class of related problems rather than a single case.

Every execution spends resources. In Hansel and Gretel’s path, the number of pebbles roughly determines the number of algorithmic steps. Carrying enough pebbles also requires storage. Computer scientists therefore describe runtime and space as functions of input size, often focusing on the worst case. A route-finding method that checks each marker once scales differently from one that repeatedly returns home to collect another marker, whose total travel grows roughly with the square of the number of markers.

Analysis

This distinction echoes the difference between a blueprint and a building: the plan can be reused, while each construction consumes labor and materials. Measuring growth rather than seconds also prevents hardware speed from disguising a poor method. Still, asymptotic analysis is a model, not a stopwatch. Small inputs, constant costs, and user experience can make a theoretically slower method practical. Good evaluation combines growth rates with the real constraints of the task.

Choose representations carefully: the same symbols can mean different things

Symbols need interpretation. A sign has a visible form and a concept it represents. The symbol “10,” for example, means ten in decimal notation but two in binary notation. Computation manipulates representations, so its result depends on the meanings assigned to its inputs. A wrong representation can make a flawless sequence of operations produce a disastrous answer.

The cost can be literal. NASA’s Mars Climate Orbiter was lost after software supplied thrust measurements in English units while the spacecraft expected metric units. The mismatch cost $655 million. Sherlock Holmes’s investigation offers a smaller-scale reminder: a clue can be interpreted incorrectly, as Holmes initially misreads an inscription on Dr. Mortimer’s walking stick. Data must be understood in context, not merely processed.

Analysis

This point connects computing to measurement science: a number is never simply a number if its unit, scale, or reference is unclear. It also resembles legal interpretation, where the same wording can take different force in different contexts. Standardized formats reduce this risk, but standards do not eliminate assumptions or bad inputs. A reliable process therefore checks both whether data fit a format and whether that format represents the intended thing.

Match data organization to the operations you need most

A task differs from its implementation. A data type specifies what can be done with a collection, such as adding, removing, or finding an item. A data structure is the concrete arrangement used to support those operations. Sherlock Holmes can think of suspects as a set, but he could store that set in a list or an array, each with different costs.

There is no universal winner. A list can grow easily, but finding an item may require scanning every entry. An array offers direct access but may need space reserved for possibilities that never occur. A balanced binary search tree can support search in logarithmic time, while a trie organizes keys by shared prefixes. Each choice favors some operations, sizes, or kinds of data over others.

Analysis

This is a practical form of design thinking: start with what a system must do, then choose a structure that makes those actions affordable. It resembles urban planning, where a layout is judged by how well it supports travel, access, and future growth. The trade-off also warns against optimizing a single operation in isolation. Faster lookup may cost memory or make updates harder, so the right structure depends on the whole pattern of use.

Judge algorithms by how costs grow, not by today's stopwatch

Growth changes the verdict. Selection sort repeatedly searches for the next smallest item, so its runtime grows roughly quadratically. Mergesort divides a list into halves, sorts them, and merges the results; its worst-case runtime grows in proportion to the list size times its logarithm. For comparison-based sorting, the book explains that this growth rate is also a lower bound, making mergesort optimal in the general case.

Prepared work can pay off. Sorting an exam pile before returning papers may take extra effort, but it can make distribution much faster. A sorted collection also supports quicker future searches. Quicksort is usually efficient, though poor pivot choices can make its worst case quadratic. The pattern of growth, not a single benchmark, reveals which method survives larger inputs.

Analysis

Asymptotic analysis is a way of asking whether a method remains usable as demands increase. The same question appears in public infrastructure: a road that serves a village may fail when a city grows around it. Precomputation adds a second useful idea, that work can be paid for once and reused. Its value depends on repeated use, however. If the data change constantly, maintaining the prepared structure may cost more than it saves.

When exact search explodes, use approximation or turn hardness into protection

Some solvable problems are impractical. In the weighing puzzle, each object can be included or excluded, so six objects create 64 possible combinations. With many objects, the number of possibilities grows exponentially. The knapsack problem has the same shape: select items within a limit while maximizing their value. Problems whose known solutions require such growth are called intractable in practice, even if an answer exists in principle.

Good enough can be useful. An approximation algorithm aims for a useful answer without guaranteeing the exact optimum. A greedy strategy for the example weighing problem chooses the heaviest available weights that fit, reaching 39 against a target of 42. The book also shows the upside of computational difficulty: encryption can rely on the practical difficulty of factoring large numbers.

Analysis

The valuable shift is from asking only whether a perfect answer exists to asking what quality of answer the decision actually requires. Operations research makes the same distinction when scheduling routes or allocating scarce resources. Yet approximation is not automatically harmless: a near-optimal solution may be unacceptable in medicine, safety, or fairness. Likewise, security based on computational difficulty is conditional on current knowledge and technology. The acceptable error and threat model must be stated, not assumed.

Give every language structure and meaning before asking machines to follow it

Grammar defines what counts. A language is more than a list of symbols; its grammar specifies how symbols combine into valid sentences and what structure those sentences have. In the music example, a score lets a performer reproduce a melody. Bars help group notes into measures and indicate emphasis. Without them, the same sequence of notes can support more than one interpretation.

Meaning follows structure. Parsing turns a sentence into a tree that makes its organization explicit. A compositional semantics then builds the sentence’s meaning from the meanings of its parts according to that structure. This works well for a clearly defined score. Ambiguous instructions, by contrast, can yield multiple structures and meanings. That is why prescriptions, programming languages, and other instructions need precise conventions.

Analysis

The music analogy reveals why syntax is not cosmetic. Structure guides interpretation, much as punctuation can change who is being addressed or what an instruction requires. This connects to human-computer interaction, where an interface can prevent errors by making available choices explicit. Formal precision has limits, though: human language carries idioms, shared context, and implied meaning that resist neat rules. A well-designed technical language narrows ambiguity for a purpose, rather than pretending ambiguity can be erased everywhere.

Treat termination as a question algorithms cannot always answer

Loops depend on changing state. A loop repeats a body of steps until a condition is met. In Groundhog Day, Phil Connors relives the same day until he becomes a better person. In an algorithm, the condition must be affected by the loop’s actions if it is ever to change. A fixed-count loop is predictably finite; a condition-based loop may continue forever.

There is no universal detector. The halting problem asks whether an algorithm will stop for a given input. Alan Turing showed that no algorithm can correctly answer this question for every possible algorithm and input. Particular cases can still be analyzed. The result is a boundary on automatic prediction, not a claim that programmers can never reason about termination.

Analysis

The result has practical force because it distinguishes uncertainty from mere lack of effort: some questions resist a universal decision procedure. This is related to limits in formal verification, where proving a system safe can require restricting what the system is allowed to do. In practice, engineers use bounded analysis, tests, and carefully designed languages. Those tools can offer strong guarantees within a scope, but a guarantee should never be confused with a solution to every possible case.

Use recursion for self-similar problems, but make every path reach a base case

A definition can call itself. Recursion is self-reference in a method or structure. To count items in a list, count the tail and add one; an empty list supplies the base case, where the answer is zero. The same pattern defines trees and supports divide-and-conquer methods such as mergesort, which solves smaller versions of a problem and combines their results.

The return matters. A recursive call must make progress toward a base case, or the process may never finish. The book uses time travel in Back to the Future to picture a call reaching into an earlier computation for a result needed now. This is an analogy, not a literal mechanism. An interpreter tracks nested calls and their return points with a stack.

Analysis

Recursion is easier to understand when viewed as a compact description of repeated structure, rather than as a mysterious trick. The same pattern appears in family trees, linguistic phrases, and natural branching forms. The essential safeguard is a decreasing measure: each call should handle a smaller input or move toward a clear stopping case. Some recursive processes intentionally generate endless streams, but their usefulness depends on consuming only the finite portion actually needed.

Let types catch category errors, and abstraction decide which details matter

Types encode useful expectations. A type groups values by the operations that make sense for them. A sorting method can accept a list of comparable items, but applying it to a time value is a category mistake. Typing rules state which combinations are valid, and type checkers can flag violations. Static checking examines an algorithm before execution; dynamic checking tests values as the algorithm runs. Neither proves the algorithm computes the intended answer.

Abstraction is selective. It gives a name to a reusable pattern while hiding details not needed for the task. Calling Harry Potter a wizard foregrounds his ability to perform magic, not his other traits. Algorithms, data types, and models of computers all abstract from some particulars. The challenge is choosing what to ignore without discarding information the task depends on.

Analysis

Types function like safety rails in engineering: they prevent some incompatible components from being connected, while leaving the larger design problem untouched. Abstraction is similarly productive and risky. A map is useful because it omits detail, but the omitted detail matters if the map is used for the wrong purpose. The best abstractions are therefore purpose-relative, and strong type systems can make assumptions visible without guaranteeing that those assumptions are true in the world.

Analysis

The book’s distinctive achievement is to treat stories as working models of computation. Hansel’s markers, Holmes’s clues, Indiana Jones’s searches, Phil Connors’s loop, and Harry Potter’s rules each give a reader an intuitive handle on a technical idea before formal vocabulary arrives. This is more than a collection of clever metaphors: the sequence builds a coherent account of computation as the execution of methods over representations, with languages, data structures, complexity, recursion, and types supplying the machinery.

The approach also makes computer science unusually legible to non-specialists. It relocates the discipline from the image of solitary code writing to systematic problem solving in everyday life. That broad framing is persuasive when a task is repeatable and its steps can be specified. It becomes less precise when applied to human behavior, where goals, interpretation, and invention may change during the process. The book partly guards against this by distinguishing creative, ad hoc problem solving from algorithmic method. That distinction should remain visible: computational description illuminates a process, but does not exhaust its human meaning.

Its treatment of limits is especially valuable. Runtime analysis separates problems that merely need a faster machine from those whose known methods scale disastrously; the halting problem shows that some prediction cannot be automated in full generality. These are different kinds of limitation and should not be collapsed. Intractability concerns the resources known methods demand, while undecidability concerns the nonexistence of a universal decision procedure.

A contemporary reader should also treat the encryption example as historically contingent rather than a timeless guarantee. Factoring-based systems depend on assumptions about available algorithms and machines, and advances in computation can change the security landscape. That caveat reinforces the book’s deeper lesson: computer science is not magic. It is a disciplined study of what representations and procedures can accomplish, what they cost, and where their guarantees end.

Summary in 30 Seconds
An algorithm is a precise method, while computation is its execution; runtime and storage costs depend on input size. Data structures favor different operations, and algorithm costs become clearer as inputs grow: mergesort scales better than selection sort. Some searches grow impractical, making approximation useful, while factoring difficulty can support encryption. Grammar and types clarify valid instructions, but no general procedure can determine whether every algorithm will stop.
Contains spoilers

Last updated:

Report Issue

Review Summary

3.63 out of 5
Average of 265 ratings from Goodreads and Amazon.

Once Upon an Algorithm receives mixed reviews. Readers appreciate its creative approach of using stories to explain computing concepts, but some find the execution uneven. The academic writing style and stretched analogies can make it challenging for beginners. However, many praise its clever examples and thorough explanations of computer science fundamentals. Some reviewers note it works better as a textbook supplement than a standalone introduction. Overall, it's seen as an ambitious attempt to make algorithms accessible, though not always successful in achieving this goal.

Your rating:
4.21
166 ratings
Want to read the full book?

Glossary

algorithm

Reusable problem-solving method

A finite, precise description of steps for solving a problem or class of related problems. An algorithm can be executed on particular inputs by a capable person, machine, or other agent. Its quality depends not only on whether it produces the intended result, but also on whether it terminates and uses acceptable time and space.

representation

Sign standing for something

A form that stands for information or a concept relevant to a problem. Computation transforms representations, and the meaning of the result depends on how the input representation is interpreted. A single representation may have different meanings in different contexts, while the same information may be represented in multiple ways.

data type

Required collection operations

A description of a collection in terms of the operations it supports and the access pattern it follows. A set, for example, supports adding, removing, and finding elements without prescribing how they are stored. A data type is an abstract specification that must be implemented by a concrete data structure.

data structure

Concrete data arrangement

A concrete way of organizing data so that an algorithm can access and manipulate it. Lists, arrays, and trees are examples. Each supports operations with different time and space costs, so the best choice depends on the tasks, input size, and storage limits involved.

trie

Prefix-organized search tree

A tree structure for storing keys that can be divided into sequences, such as words. Rather than storing each complete key in a separate node, a trie represents keys through paths and can share common prefixes. This can make searching strings efficient, though its usefulness depends on the keys and application.

divide-and-conquer

Split, solve, recombine

A problem-solving pattern that breaks a problem into smaller subproblems, solves those subproblems, and combines their results. Mergesort and quicksort use this approach. It is especially useful when smaller instances are easier to solve and their solutions can be assembled into a solution for the original problem.

intractable problem

Practical cost grows prohibitively

A problem for which the known algorithms require resources that become impractical as inputs grow, often because runtime increases exponentially. Intractability is a statement about practical feasibility, not about whether a solution exists. A faster algorithm may remain undiscovered, and approximation methods can sometimes provide useful results.

NP-complete

Interconnected hard problems

A class of problems whose proposed solutions can be checked efficiently and whose problems are linked through efficient reductions. If an efficient general solution were found for one NP-complete problem, efficient solutions would follow for all of them. Whether such a solution exists is unknown, making these problems central to the P versus NP question.

compositionality

Meaning built from parts

A property of a semantics in which the meaning of a whole sentence is determined systematically by the meanings of its components and their structure. A grammar makes that structure explicit, often with a syntax tree. Idioms and other exceptional constructions can resist this straightforward, part-by-part interpretation.

halting problem

Universal termination decision

The problem of deciding, for any given algorithm and input, whether execution will eventually stop. Turing proved that no algorithm can correctly decide this in every case. The result does not prevent analysis of particular programs; it rules out a single complete procedure for all possible programs and inputs.

recursion

Self-reference in a definition

A way to define a method or structure partly in terms of itself. Recursive algorithms commonly handle a smaller input and combine that result with other work. A base case provides a nonrecursive stopping case, but termination also requires recursive calls to reach it.

typing rule

Rule for valid operations

A rule that describes which operations are valid for particular kinds of values and what kind of result they produce. A type checker can use such rules to identify some errors before or during execution. Type correctness prevents certain invalid combinations, but it does not prove that an algorithm achieves its intended goal.

abstraction

Purposeful omission of detail

A process and result of describing a pattern while omitting details that are not needed for a particular purpose. An abstraction typically has a name and parameters that allow it to be reused in different cases. Its usefulness depends on balancing generality and simplicity against the information a task requires.

FAQ

What's Once Upon an Algorithm about?

  • Explains computing through stories: The book uses popular narratives to illustrate fundamental concepts in computer science, particularly computation and algorithms.
  • Focus on problem-solving: It emphasizes systematic problem-solving, showing the relevance of computation in everyday life through various stories.
  • Two main parts: The book is divided into sections on algorithms and languages, exploring how they function and are structured.

Why should I read Once Upon an Algorithm?

  • Accessible to all readers: Martin Erwig presents computer science concepts in an engaging and understandable way for non-specialists.
  • Encourages computational thinking: The book aims to spark interest in computer science, enhancing problem-solving skills in various fields.
  • Unique perspective: By linking computing principles to well-known stories, it offers a fresh perspective on both literature and technology.

What are the key takeaways of Once Upon an Algorithm?

  • Understanding computation: Computation is a systematic way of problem-solving found in everyday activities, not limited to computers.
  • Importance of algorithms: Algorithms are central to computer science, reusable for solving similar problems efficiently.
  • Role of representation: Effective representation of information is crucial for successful problem-solving and computation.

How does Once Upon an Algorithm relate stories to computing concepts?

  • Illustrative examples: Familiar stories are used to explain complex computing concepts, making them more relatable.
  • Connecting narratives to algorithms: The book demonstrates how problem-solving techniques are found in literature and everyday life.
  • Encouraging engagement: Stories engage readers, fostering a deeper understanding of algorithms and representations.

What stories are used in Once Upon an Algorithm?

  • Hansel and Gretel: Used to explain computation and algorithms, highlighting systematic problem-solving.
  • Sherlock Holmes: Discusses representation and data structures, showcasing logical reasoning and deduction.
  • Indiana Jones: Illustrates the limitations of problem-solving and the importance of organization and strategy.

How does Once Upon an Algorithm define an algorithm?

  • Precise description of computation: An algorithm is a systematic method for solving problems, consisting of executable steps.
  • Reusability: Good algorithms can be reused across different contexts, distinguishing them from ad hoc solutions.
  • Execution and resources: Execution requires resources and time, important for evaluating algorithm efficiency.

What is computational thinking as described in Once Upon an Algorithm?

  • Systematic problem-solving: Approaching problems by breaking them down into smaller, manageable parts.
  • Application beyond computers: Computational thinking is applicable in various fields and everyday situations.
  • Enhancing decision-making: It improves the ability to make informed decisions and tackle complex challenges.

What is the significance of types in Once Upon an Algorithm?

  • Organizes knowledge effectively: Types categorize objects and actions, aiding efficient reasoning about algorithms.
  • Prevents type errors: Typing rules help avoid mistakes, ensuring algorithms operate correctly.
  • Supports abstraction: Types enable abstractions, simplifying complex systems for easier understanding.

How does Once Upon an Algorithm explain recursion?

  • Descriptive vs. unfolded recursion: Distinguishes between self-referential definitions and their execution.
  • Time travel analogy: Uses time travel as a metaphor for recursive calls influencing the present.
  • Fixed points: Discusses stable solutions in recursion that avoid paradoxes.

What is the halting problem as explained in Once Upon an Algorithm?

  • Undecidability concept: Illustrates the impossibility of determining if an arbitrary algorithm will terminate.
  • Implications for algorithms: Affects the design and analysis of algorithms, highlighting computation limitations.
  • Real-world examples: Uses relatable scenarios to make the concept more accessible.

What role does ambiguity play in programming languages according to Once Upon an Algorithm?

  • Source of confusion: Ambiguity can lead to multiple interpretations, complicating algorithm understanding.
  • Importance of clarity: Clear syntax and semantics are needed to avoid misunderstandings.
  • Comparison with natural languages: Draws parallels between ambiguities in natural and programming languages.

What are the best quotes from Once Upon an Algorithm and what do they mean?

  • “Computer science is the study of systematic problem solving.”: Emphasizes finding structured solutions to problems.
  • “No computation without representation.”: Highlights the importance of meaningful data representation.
  • “A problem well put is half solved.”: Stresses the significance of clearly defining problems for effective solutions.

About the Author

Martin Erwig is a Professor of Computer Science at Oregon State University. He has authored multiple books on computer science, with "Once Upon an Algorithm" being his third. Erwig's expertise lies in programming languages, functional programming, and visual languages. His unique approach to teaching computer science concepts through storytelling and pop culture references demonstrates his commitment to making complex topics more accessible to a wider audience. Erwig's academic background and passion for innovative teaching methods are evident in his work, which aims to bridge the gap between theoretical computer science and everyday experiences.

Download PDF

To save this Once Upon an Algorithm summary for later, download the free PDF. You can print it out, or read offline at your convenience.
Download PDF
File size: 0.40 MB     Pages: 21

Download EPUB

To read this Once Upon an Algorithm summary on your e-reader device or app, download the free EPUB. The .epub digital book format is ideal for reading ebooks on phones, tablets, and e-readers.
Download EPUB
File size: 1.38 MB     Pages: 24
Want to read the full book?
Follow
Listen11 mins
Home
Swipe
Library
Get App
Try Full Access for 3 Days
Listen, bookmark, and more
Compare Features Free Pro
📖 Read Summaries
Read unlimited summaries. Free users get 3 per month
🎧 Listen to Summaries
Listen to unlimited summaries in 40 languages
—
❤️ Unlimited Bookmarks
Free users are limited to 4
—
📜 Unlimited History
Free users are limited to 4
—
📥 Unlimited Downloads
Free users are limited to 1
—
Risk-Free Timeline
Today: Get Instant Access
Listen to full summaries of 26,000+ books. That's 12,000+ hours of audio!
Day 2: Trial Reminder
We'll send you a notification that your trial is ending soon.
Day 3: Your subscription begins
You'll be charged on Nov 24,
cancel anytime before.
Consume 2.8× More Books
2.8× more books Listening Reading
Our users love us
1M+ readers
Trustpilot Rating
TrustPilot
4.6 Excellent
This site is a total game-changer. I've been flying through book summaries like never before. Highly, highly recommend.
— Dave G
Worth my money and time, and really well made. I've never seen this quality of summaries on other websites. Very helpful!
— Em
Highly recommended!! Fantastic service. Perfect for those that want a little more than a teaser but not all the intricate details of a full audio book.
— Greg M
Save 62%
Yearly
$119.88 $44.99/year/yr
$3.75/mo
Monthly
$9.99/mo
Start a 3-Day Free Trial
3 days free, then $44.99/year. Cancel anytime.
Unlock a world of fiction & nonfiction books
26,000+ books for the price of 2 books
Read any book in 10 minutes
Discover new books like Tinder
Request any book if it's not summarized
Read more books than anyone you know
#1 app for book lovers
Lifelike & immersive summaries
30-day money-back guarantee
Download summaries in EPUBs or PDFs
Cancel anytime in a few clicks

Why one summary?

Scanner
Find a barcode to scan

⭐
⭐
⭐
We have a special gift for you
Open
38% off
DISCOUNT FOR YOU
⭐
⭐
⭐
$79.99
$49.99/year
Only $4.16 per month
Continue
2 taps to start, super easy to cancel
Settings
General
Widget
Loading...