The Department of Electrical Engineering and Computer Science (EECS) recently learned that “Introduction to Algorithms,” a textbook coauthored by department professors Charles Leiserson and Ronald Rivest, alongside Dartmouth College’s Tom Cormen SM ’86, PhD ’93 and Columbia University’s Cliff Stein SM ’89, PhD ’92, has now officially sold over 1 million copies worldwide. Lauded for its clarity, the book is premised on a “start from fundamentals” approach that welcomes students of many backgrounds and learning styles, regardless of their familiarity with advanced mathematics. We conducted interviews over Zoom with Charles Leiserson, and by email with co-author Tom Corman, about “Introduction to Algorithms” — its origins, its runaway success, and its impact over the years.
Q: Congratulations on the 1 millionth sale of “Introduction to Algorithms.” Tell us about the moment when you found out — your thoughts and emotions.
Leiserson: It’s quite remarkable to me that we’re in this position; for a textbook, this is an extraordinarily long life. Most textbooks don’t publish a second edition, and we’re currently working on our fourth, the edition which we thought might sell the millionth copy. So, it was a surprise when Elizabeth Swayze (senior acquisitions editor at the MIT Press), emailed us saying they had just discovered we’d gone over the 1 million mark.
Q: You co-authored “Introduction to Algorithms” over 30 years ago, in 1990, when the field obviously looked very different. What is the process of revision like within a quickly changing and developing field?
Leiserson: In some ways it’s been more complicated than when we wrote the first edition, although that was the most amount of work. When we were writing the first edition, there were three of us and we were all at MIT; Ron Rivest’s office was next to mine, Tom Cormen was my graduate student, and we were all able to work side-by-side. For the last edition, we did have some meetings, but it was only two or three meetings in person before Covid hit, and after that we worked independently and relied a lot more heavily on Zoom for meetings. I can’t imagine where I got the time to do the first edition, because this last one has been a real struggle, and yet it’s not as much time (by a long shot) as what we put in years ago. I’ve simply got more on my plate!
Cormen: One change that is quite apparent to us, the authors, is the technology we use to produce the book. When we started writing the first edition, we were just producing PostScript, not PDF, and even before we had written the entire book, producing the PostScript file was an overnight run — unless we ran it on Ron’s machine, when it took about an hour. On our laptops now, it takes about 20 seconds to produce the PostScript file, and a few more seconds to produce the PDF.
For the first edition, the illustrations were produced at a separate site from the text, and they were pasted in. Starting with the second edition, we can lay in illustrations directly. We have also augmented our set of LaTeX macros over the years, most notably the clrscode, clrscode3e, and clrscode4e packages, which allow everyone to typeset pseudocode the way we do.
One other change related to keeping up with the times is that for the fourth edition, we are making available a complete set of Python implementations of the algorithms in the book. (Because the algorithms in the new chapter on machine learning are so abstract, we omitted them.) The Python code was written by my former student, Linda Xiao, and me.
Regarding how the content of the book has changed over the years, as much as we would have liked to only add material and not remove any, there are physical (and contractual) limitations to how big the book can get. So we’ve had to decide not only what material to add, but what material to cut. Left to our own devices, the book would end up being a cube!
Q: Whose idea was it to try to write a definitive introduction to algorithms? How did you first pitch the book?
Leiserson: When I got to MIT, I wanted to teach the algorithms class 6.046, and it wasn’t available for the first couple of years — other faculty with seniority were signed up to teach it. I had to wait a few years and teach many other classes before I got the opportunity to teach 6.046. I inherited great notes from the people who had taught it before (including Ron Rivest, among others). At the time, there were textbooks covering some topics in algorithms — I think the dominant one was by Aho, Hopcroft, and Ullman, “Design and Analysis of Computer Algorithms.” Donald Knuth, a Turing Award winner, had another one, a three-volume series called “The Art of Computer Programming.” And there were also books that were dealing with algorithms but didn’t cover all the same topics, such as Eugene Lawler’s “Combinatorial Optimization.” These books all inspired and influenced me.
But these and other textbooks sometimes invoked higher math, and often I found those explanations baffling. What we found as we were writing our own book was that in fact some of the theorems at the time had proofs that were actually wrong; they were hand waves, they relied on circular or incomplete logic, that kind of thing. These were serious problems! In response to that discovery, I wanted to write a book which reasoned from fundamentals, a book which a student could use to learn about algorithms with little assumed background in higher math — algebra, but no calculus.
We began with a chapter that outlined the math axioms, the basic principles, which you needed to ground your understanding. The nucleus of this work was the set of lecture notes taken down by my amazing TA [teaching assistant], Tom Cormen, who not only took notes for all my lectures, but took the time to rewrite them into truly useful documents which we could carry forward into subsequent iterations of every class. While talking with Tom, I said, “You know, I think we could assemble a textbook out of what we’ve got here, if we put the effort in.”
Since Ron had the most involvement in 6.046 before me, we asked Ron if he was interested in collaborating on a textbook, and he was, so we got started. I thought we could do it in two years — it took us three-and-a-half!
Q: Tell me about the co-authorship process; how did it change the way you approached writing and work? Did you have a specialization, or a favorite part of the writing process?
Cormen: Each chapter has a primary author, but we each have a hand in every chapter. In some cases, I developed a new way to approach existing material, such as changing the treatment of binary search trees between the second and third editions, or explaining the intuition behind the potential function for table doubling and halving in the fourth edition. In other cases, I had to learn the material in order to write the chapter from scratch, such the chapter on bipartite matching and the section on suffix arrays in the fourth edition.
My favorite part of the writing process is the feeling I get when I know I got a sentence, or a paragraph, just right. And then I hope that I don’t get knocked down later when Julie Sussman, the best copy editor ever, shows me an even better way to say it!
Leiserson: Within theoretical computer science, you list authors alphabetically, so we don’t typically have first authors. One of the nice things that that convention promotes is the notion that everybody owns the work, 100 percent. Everybody gets full credit for the work, and if there’s a problem anywhere, everyone takes the blame. Everyone is responsible, and everyone gets to benefit. And that’s a form of collaboration that appeals to me. This principle led us to a process where we all wrote all of the chapters in the first edition. One of us would draft a version; the other would edit and reorganize it; then the chapter would go to the third person; then back to the first. Each chapter would bounce around.
It was one of the best collaborations I have ever had with other people, because we complemented each other. Ron is a Turing Award winner and is enormously technically capable. He pulled some massive bugs out of my work — I was able to return the favor only maybe once or twice, but he really pointed out some doozies in my own stuff. And Tom was a fabulous writer. And I was maybe in the middle on those things, in that I was strong technically (though not as strong as Ron) and I was an excellent writer (though not as strong as Tom).
The partnership showed its strength in many ways; for example, at the time we wrote the book, there was really no good indexing software — but Ron automated our two-level index, so we could put it right into our books. Additionally, in those days, technical works were usually typeset by the publisher, and then you would have to go through and correct all the math and technical stuff that they got wrong. But we produced a machine version of our book, so we were one of the first books that MIT Press produced where the authors controlled the typesetting. Our copy editor, Larry Cohen, would mark up our print and then we would go through and implement the changes, and that way we ensured that math errors wouldn’t have a tendency to creep in.
Q: You must feel a certain amount of responsibility for the direction of the field of computer science, having authored such an influential textbook; published numerous research contributions in algorithms, parallel computing, design automation, computer architecture, and performance engineering; developed several new undergraduate classes; created many of the original modules for the UPOP [Undergraduate Practice Opportunities Program] program; led the computer science program for Singapore-MIT Alliance [for Research and Technology]; and created and developed a highly touted workshop on leadership skills for engineering and science faculty.
Leiserson: One of the things that has mattered most to me was the values that MIT, my department, and my laboratory all shared and embodied. My department places an equal emphasis on research and teaching; that notion, that each informs the other, matters to me. I’ve attended research presentations and thought, “Gosh, this is exactly the teaching example I’ve needed!” It goes the other way round, too. For example, my feeling is that the earlier in the curriculum you can teach a research result, the more important it is. So, if I can teach it to freshman, that is a more important result than being able to teach it only to grad students or peers. That was one measure, though it’s not the only measure of significance.
One of the good things about a university is that there are many paths to success, and one of the things you do is figure out which path is yours. There’s a lot of room for individual people to contribute to academia in different ways. Some people are great catalogers and scholars, others are incredible problem-solvers. Some people like textbooks. MIT supports that range of quirkiness among its faculty.
It’s like OpenCourseWare — one of the brilliant innovations at MIT with respect to teaching, which I’m proud to have had a stake in. I once sat next to a businessman on a flight between Europe and India who, as we were talking, showed no recognition of MIT, but he’d heard that an American university was putting all of its courses online for free. That was a good example of how our work was contributing to MIT’s mission and reputation. That’s how you attain excellence — by having people who contribute their reputations to the institution, rather than the other way around. MIT is great because of the people who are here. And I’m glad that “Introduction to Algorithms” contributes to MIT’s reputation.