Algorithms Unlocked

Citation

Cormen, T. H. (2013). Algorithms Unlocked. MIT Press.

Chapter Summary

Algorithms Unlocked is a short book (about 236 pages, xiii + 222 in the library record) in ten chapters, followed by a bibliography and index. The publisher presents it as a guide for non-experts that explains, "with limited mathematics", how algorithms let computers solve problems, written by a co-author of Introduction to Algorithms. Algorithms are given in pseudocode, and the chapters move from searching and sorting through graphs, strings, cryptography and compression to problems that no one knows how to solve efficiently.

Chapter 1: What Are Algorithms and Why Should You Care?

An opening chapter on what computer algorithms are and why a reader should care about them. Mike James's review in I Programmer notes that it starts in plain English but that algebra, such as a square root of n, appears within the first few pages.

Chapter 2: How to Describe and Evaluate Computer Algorithms

How to write algorithms in pseudocode (arrays, loops, recursion) and how to analyse their running time, including big-O-style notation. The same review notes that loop invariants and recursion are introduced here, which marks the level of the book.

Chapter 3: Algorithms for Sorting and Searching

From linear and binary search to the standard comparison sorts. The term list on the book's Google Books record includes selection sort, insertion sort, merge sort and quicksort; James describes the chapter as what every programmer should know about the theory of searching and sorting.

Chapter 4: A Lower Bound for Sorting and How to Beat It

Why sorting by comparisons cannot beat a certain lower bound, and how sorts that do not compare keys, such as counting sort, get around it.

Chapter 5: Directed Acyclic Graphs

Graphs as models of dependencies among tasks and of networks, starting with directed acyclic graphs; the publisher mentions road networks, task dependencies and financial relationships as examples of what graphs model.

Chapter 6: Shortest Paths

Shortest-path algorithms: according to James, Dijkstra's algorithm, Bellman-Ford and Floyd-Warshall, in a chapter he describes as mathematical, with matrices and longer programs. Terms such as negative-weight cycle and priority queue in the Google Books term list point to the same material.

Chapter 7: Algorithms on Strings

String problems motivated by DNA, including the longest common subsequence and transforming one string into another.

Chapter 8: Foundations of Cryptography

The basic principles behind cryptography: the review mentions RSA and random number generation, and the Google Books term list includes plaintext, ciphertext and prime numbers.

Chapter 9: Data Compression

Fundamentals of compression, which the review says begin with Huffman coding and work up to LZW, the basis of common compression tools.

Chapter 10: Hard? Problems

The travelling salesman problem, P versus NP, NP-completeness, NP-hardness and undecidability, with polynomial-time reductions among problems such as 3-CNF satisfiability, Hamiltonian cycle and k-clique. The reviewer calls it the most theoretical chapter.

Key Concepts

Chapters 1–4: Describing, analysing and sorting

• Algorithm: a precise procedure that takes an input and produces a correct output, judged by correctness and running time.
• Pseudocode and loop invariants: a language-neutral way to state algorithms and a tool for arguing they are correct.
• Running-time analysis: how the number of operations grows with input size.
• Sorting lower bound: the limit on comparison sorting, and sorts such as counting sort that avoid comparisons.

Chapters 5–7: Graphs and strings

• Directed acyclic graph: a graph without cycles, modelling dependencies among tasks.
• Shortest paths: Dijkstra's algorithm, Bellman-Ford and Floyd-Warshall for routes in weighted graphs.
• Longest common subsequence: a string problem solved by building up answers to subproblems.

Chapters 8–10: Secrets, compression and hardness

• Public-key cryptography: encryption, such as RSA, built on number theory.
• Huffman coding and LZW: compression by variable-length codes and by dictionaries of repeated strings.
• NP-completeness and reductions: why some problems seem to have no efficient algorithm, and how to show a problem is as hard as another.

Critical Analysis

Strengths

• Broad tour in a small book. In ten short chapters it covers the core of an algorithms course (sorting, graph algorithms, NP-completeness) and adds chapters on string processing, cryptography and data compression, so a reader sees how algorithms reach well beyond sorting.
• Written by an expert for newcomers. The book is by a co-author of Introduction to Algorithms, and the endorsements quoted by the publisher describe it as easy to read without sacrificing depth.
• Real algorithms, not just stories. James found that the book gives actual algorithms in pseudocode with running-time analysis, so it teaches more than a popular science account would, and he called it "a really good read" for readers able to follow the details.

Limitations

• Mixed level. James's main criticism is that the prose is pitched at complete beginners while the pages carry a lot of algebra, pseudocode, loop invariants and analysis; readers who need the gentlest explanations may find the mathematics a barrier, and those who can handle the mathematics may find the tone over-simplified.
• Not a workbook. Neither the publisher's description nor the review mentions exercises, and the contents list shows none; readers who learn by solving problems will need a second book.
• Pseudocode only. The review notes that the book sticks to pseudocode, so readers must translate algorithms into a real language themselves.

Where It Fits in the Course

This is the gentlest book in the course, a preview before a full textbook. Roughgarden's Algorithms Illuminated is the natural next step: a full textbook based on the author's online courses, with videos, quizzes, problems and programming exercises, covering the same ground in much greater depth. Skiena's The Algorithm Design Manual suits readers who want practical guidance on choosing algorithms for real problems.

Cormen, Leiserson, Rivest and Stein's Introduction to Algorithms is the comprehensive textbook by the same author and his colleagues; James calls Algorithms Unlocked an entry to the author's "more grown up book". The approximation and randomized algorithms books in the course (Vazirani; Williamson and Shmoys; Mitzenmacher and Upfal) belong much later, after a full algorithms course.

How to Use This Book

The book suits prospective or first-year computer science students, programmers without formal training who want to know what lies behind standard algorithms, and readers from other fields who are comfortable with algebra. James suggests the ideal reader is a first-year or prospective computer science student or a programmer wanting an accessible overview. Some programming experience makes the pseudocode much easier to follow.

A practical plan:

• Core: Chapters 1–3 and 5–6, which give the vocabulary (pseudocode, running time), the sorting and searching algorithms, and the graph and shortest-path algorithms that every later course assumes.
• Next priority: Chapters 4 and 10; the lower bound and NP-completeness chapters introduce ideas that a full course will prove more formally.
• By interest: Chapters 7–9 on strings, cryptography and compression can be read in any order after Chapter 2.

Read with a pencil: trace each pseudocode procedure on a small input, and implement two or three of the algorithms (binary search, merge sort, Dijkstra's algorithm) in a language you know. Then move on to a textbook with problem sets for practice.