The Internet and digital technologies hadn’t permeated our lives when the first edition of Introduction to Algorithms (MIT Press) was published in 1990. Personal computers were novel, big data didn’t exist, and algorithms weren’t as widespread as they are today.
“Our relationship with information has changed. Now people know what algorithms are. Algorithms are everywhere,” said Clifford Stein, one of the textbook’s co-authors and interim director of the Data Science Institute at Columbia University.
Now in its fourth edition, Introduction to Algorithms is the leading algorithms textbook in the world with over one million copies sold, and it has been translated into more than a dozen languages.
The co-authors, including Stein, Thomas Cormen (Dartmouth College), Charles Leiserson (MIT), and Ronald Rivest (MIT), start with the basics and progress to advanced algorithmic techniques. Each chapter is relatively self-contained and presents an algorithm, a design technique, an application area, or a related topic.
“Many of the basic algorithms themselves are the same, but because of the way the world has changed, some of the applications are different,” said Stein, who is also Wai T. Chang Professor of Industrial Engineering and Operations Research and a professor of computer science at Columbia.
For example, fundamental algorithms for shortest paths date back to the 1950s. Today, we have Google Maps and other routing software. String processing has also been around for years, but now it has applications for human genome projects and computational biology.
New algorithms are being discovered all the time, and today’s algorithms are highly data dependent, according Stein, whose current research involves how to incorporate varying predictions into an algorithm. “For instance, scheduling package deliveries, even when some of the delivery data changes, you’d still like to schedule delivery as well as possible. How do you formalize that? How do you design algorithms that are robust against errors in predictions? This kind of decision-making is happening all the time, adjusting to data that is arriving in real time.”
To highlight the importance of big data applications and machine learning as an active field of research, the fourth edition of Introduction to Algorithms has a chapter called “Machine-Learning Algorithms” in which the authors cover clustering, gradient descent, and multiplicative weights algorithms. There are also new chapters on online algorithms and matching, 140 new exercises, and 22 new and revised problems.
Teaching is fundamental to the design and content of the textbook, which initially evolved from course notes. All the authors have teaching experience and consider the chapters as topics they would cover during lectures.
“That’s part of the success, I think,” Stein said regarding the textbook’s reception over the years. “With each new edition, there’s an active discussion among all the co-authors on what to add, what to remove. It’s determined by what’s important, what fits in the structure of the book, what we can cover in a high-quality way, what we have the expertise and experience to present, and what has good educational value.”
— Karina Alexanyan, Ph.D.