April 6, 2022
Fourth edition of influential introductory textbook on algorithms released
It's a rare textbook that has sold over a million copies, has a Twitter account, has been a clue on Jeopardy!, and even made a cameo appearance in a popular Chinese soap opera.
That distinction belongs to the best-selling "Introduction to Algorithms," co-authored by Dartmouth's Thomas Cormen, professor emeritus of computer science. The book's fourth edition will hit the shelves today.
Algorithms are a recipe for problem-solving. In computation, an algorithm is often defined as a procedure that takes one or more inputs and provides an output—a solution to a well-defined problem. Today, algorithms are everywhere; they run everyday appliances and make recommendations on everything from which shows to binge-watch to what routes to take to beat traffic.
Cormen's book covers a broad range of algorithms—from the basics of how to compute time taken by different computational methods, to different strategies for sorting data efficiently, and topics in the field of number theory.
"I think of Tom's famous algorithms book as the Encyclopedia Galactica of problem-solving in computer science," says Devin Balkcom, chair and professor of computer science. "Within any challenging new question, a computer scientist seeks to identify a central problem that can be formally stated, analyzed, and perhaps solved. Tom's book is a treasure of computer science: gems of algorithms that solve common problems, together with a deep analysis and understanding of the strengths and limitations of those algorithms."
Cormen was a graduate student at the Massachusetts Institute of Technology when he wrote and published the first edition with co-authors and MIT professors Charles Leiserson and Ronald L. Rivest. The core of the book came from lecture notes created by Cormen, who was a teaching assistant for Leiserson's undergraduate algorithms class. Clifford Stein of Columbia University was added as a fourth author in the second edition.
Popularly known by the abbreviation CLRS (referring to the authors' last names), the book has been widely regarded as an important reference text for over 30 years.
"My current algorithms students are always impressed to hear that I learned the topic myself from the "C' in CLRS," says Calvin Newport '04, who took Cormen's introductory computer science course in the fall of 2000 and is now an associate professor of computer science at Georgetown University.
"My approach to teaching algorithms is heavily influenced by the textbook," adds Newport, who assigns it to his students and uses the same general trajectory, and many of the same specific examples, that the book deploys.
The new edition comes 13 years after the previous one—the longest gap between editions so far. Cormen said counting translations, more than 1 million copies of the textbook have been sold over the years.
"With time, we find there's material that people are not teaching from the previous editions," says Cormen. "So those are good candidates for removing so that we have space to add new material that we think people will want to either teach or learn."
The authors also seek to freshen the problems and exercises and improve the exposition. "Over time, we think about how to write better and how to make concepts clearer," he says.
There are three new chapters: one on a concept in graph theory called bipartite matching, another on online algorithms, where not all the data is available when the problem-solving proces begins. The third new chapter is on algorithms for machine learning, a subset of artificial intelligence. According to Cormen, this chapter "is the one people are going to be pretty excited about."
Revisions are not limited to the technical content. Cormen credits his four-year stint as the first director of the Institute for Writing and Rhetoric for a shift away from a more formal style after the second edition. In the fourth edition, the writing is a little more personal, he says.
The authors have also removed gendered language this time around. A well-known problem historically called the "traveling salesman problem" is now the "traveling salesperson problem."
"Computing is a sufficiently new field that it evolves much more rapidly than, say, calculus," says Doug McIlroy, adjunct professor of computer science. Reflecting that rapid evolution, the newer editions of Cormen's book are "not the same book that it was a generation ago," he says. McIlroy has a particular fondness for the book's compelling diagrams. "Even though I've been in the field before it formally became computer science, I have learned things from this book," he says.
Great co-authors who bring different strengths to the table, and an excellent copy editor—in this case Julie Sussman—are some ingredients of the secret sauce that have made the book a success, says Cormen, who retired on Jan. 1 and taught his final course in the fall of 2019.
He cautions against embarking on a book project during a Ph.D., however. "I was lucky because this book turned out to be very successful," he says.
The impact of the book on the field of computer science—and more broadly on the computing industry—cannot be understated, says Provost David Kotz '86, the Pat and John Rosenwald Professor in Computer Science.
"Generations of students have learned the fundamentals from this book," he says. "People who work in industry (and not just Dartmouth alums) tell me they keep this book handy on their shelves while they code the next generation of computing systems we all will use and enjoy."