The Algorithm Design Manual

Citation

Skiena, S. S. (2020). The Algorithm Design Manual (3rd ed.). Springer.

Chapter Summary

The book has two parts and twenty-two chapters, followed by a bibliography and an index; the numbered pages of the main text run to about 718 of the book's 793. The first part, Practical Algorithm Design (Chapters 1–13), teaches methods for designing and analysing algorithms. The second, the Hitchhiker's Guide to Algorithms (Chapters 14–22), is described by the publisher as a catalogue to browse, covering 75 problems that come up often in practice, together with pointers to implementations and literature. Skiena's own page describes the book as stressing design over analysis.

Chapters 1–2: Introduction to Algorithm Design; Algorithm Analysis

The opening chapters introduce algorithm design (Chapter 1) and algorithm analysis (Chapter 2), the latter in about forty pages. The publisher describes the book's style as "no theorem-proof", an intuitive rather than formal register, and that is the register in which analysis is presented.

Chapters 3–4: Data Structures; Sorting

Data structures and sorting have chapters of their own inside Part I, so the book does not simply assume them; the contents do not show how much earlier study these chapters expect.

Chapters 5–6: Divide and Conquer; Hashing and Randomized Algorithms

Two chapters on techniques. The publisher lists new or expanded coverage of divide and conquer, hashing and randomized algorithms in this edition, which matches the subject of these chapters.

Chapters 7–8: Graph Traversal; Weighted Graph Algorithms

Two chapters, about eighty-five pages together, move from traversal to weighted problems. Graphs recur in Part II, in separate chapters on polynomial-time and NP-hard graph problems, so that in total roughly a quarter of the numbered pages deal with graphs.

Chapters 9–10: Combinatorial Search; Dynamic Programming

Chapter 9 deals with combinatorial search; Chapter 10, the longest chapter in Part I at about forty-seven pages, deals with dynamic programming.

Chapters 11–13: NP-Completeness; Dealing with Hard Problems; How to Design Algorithms

Part I closes with a block on intractability: what NP-completeness means, then strategies for problems that are hard in that sense. The publisher lists approximation algorithms among the topics with new or expanded coverage, without saying which chapter carries them. The last chapter of the part is only six pages long and is titled "How to Design Algorithms".

Chapter 14: A Catalog of Algorithmic Problems

A two-page entrance to Part II, which begins on page 435 with the Hitchhiker's Guide. The publisher says the catalogue leads the reader towards a solution for each problem.

Chapters 15–19: Data Structures; Numerical Problems; Combinatorial Problems; Graph Problems: Polynomial Time; Graph Problems: NP-Hard

Chapters of catalogue entries organised by the kind of problem. Chapter 15 returns to data structures, now inside the catalogue, and Chapters 18 and 19 split graph problems into polynomial-time and NP-hard ones.

Chapters 20–22: Computational Geometry; Set and String Problems; Algorithmic Resources

The catalogue ends with geometry (the longest catalogue chapter at about fifty-six pages), sets and strings, and a short final chapter on algorithmic resources. The publisher says the book provides links to implementations in C, C++ and Java.

Key Concepts

Part I: Practical Algorithm Design (Chapters 1–13)

• Algorithm analysis: judging the efficiency of a design, treated as a working tool.
• Divide and conquer, hashing, randomization: techniques given their own chapters.
• Graph traversal and weighted graphs: the core of the graph material.
• Dynamic programming and combinatorial search: methods for optimisation and exhaustive problems.
• NP-completeness: the vocabulary for recognising problems that probably have no efficient exact algorithm.

Part II: The Hitchhiker's Guide to Algorithms (Chapters 14–22)

• Problem catalogue: entries organised by category of problem, so that a reader can look up the problem rather than the algorithm.
• Problem categories: data structures, numerical, combinatorial, graph (polynomial-time and NP-hard), geometric, and set and string problems, which is how the catalogue chapters are divided.

Critical Analysis

Strengths

• Organised around recognising problems. The catalogue half lets a reader start from the shape of a problem, which is a different entry point from the technique-by-technique order of most algorithms textbooks. Skiena's site also lists an Algorithm Repository and programs.
• Accessible by design. The publisher stresses the "no theorem-proof" style, highlighted take-home lessons and "war stories" from applications.
• Practice material. Exercises include job-interview problems, and the new edition adds more than a hundred problems, including problems from LeetCode and HackerRank. The author's site links a solutions wiki, lecture notes and lecture videos.
• Hard problems are met head-on. NP-completeness, strategies for hard problems, and a separate NP-hard graph chapter mean that students see what to do when no efficient algorithm is expected.

Limitations

• Proofs are minimal by design. A reader who wants careful proofs of correctness and running time will need a more formal text alongside it.
• Code is in C. The publisher says many algorithms are given as C code, so readers who work in other languages will translate, or rely on the implementation links.
• Half the book is reference. The publisher says Part II is intended for browsing and reference; read from cover to cover it is a catalogue rather than a sequence of lessons.

Where It Fits in the Course

Within this course, Skiena sits between the gentler introductions and the rigorous textbooks. Cormen's Algorithms Unlocked is a short introduction that uses limited mathematics, and Roughgarden's Algorithms Illuminated is a conversational four-part treatment with free video lectures; either can come first. Cormen and co-authors' Introduction to Algorithms is the comprehensive, pseudocode-based textbook with rigorous explanations, and is the natural companion when proofs are wanted.

For the hard-problem material in Chapters 11–12 and 19, the specialised books extend the subject: Vazirani's Approximation Algorithms and Williamson and Shmoys's The Design of Approximation Algorithms go much further into approximation, and Mitzenmacher and Upfal's Probability and Computing is the advanced route into randomized algorithms.

How to Use This Book

The book suits students who can already program and have met basic data structures, and professionals preparing for technical interviews, which the publisher names as a use. It is also useful to anyone who needs to identify what kind of problem they face.

A practical plan:

• Core (Part I): Chapters 1–4 quickly if the material is familiar; Chapters 5–10 in order, as the main stock of techniques; Chapters 11–12 for intractability; Chapter 13 as the short closing chapter on design.
• Reference (Part II): read the entrance chapter, then use the catalogue when a concrete problem appears, following its pointers to implementations and further literature rather than reading chapter after chapter.
• Practice: work the exercises, including the interview-style ones, and use the solutions wiki and lecture videos on the author's site as checks.
• Pairing: keep a rigorous text such as Introduction to Algorithms beside it for proofs, and implement a few algorithms in your own language to compare with the C code.