A number of important ideas have informed my 50+ years of teaching and research in computer science, at universities, research laboratories, conferences, and workshops around the world. This page consist of essays that describe and trace the evolution of several of these ideas:

  • The emergence of online learning as an effective and efficient means to vastly expand access to education.
  • The development of computer science as an academic discipline that is relevant to every educated person in the 21st century.
  • Discovering and learning fundamental practical algorithms and effectively applying that knowledge through algorithm science.
  • Visualization as a tool to understand algorithms and data structures.
  • A calculus for learning properties of discrete structures known as analytic combinatorics, developed with my late friend Philippe Flajolet.

Remarkably, many of these topics have remained relevant for decades, and are likely to remain relevant in the future.

Online Learning

One of the main reasons one enters academia is to play a role in disseminating knowledge. My career as an academic coincided with revolutionary developments in technology culminating in the development (with my colleague Kevin Wayne) of a new model for disseminating knowledge. We have created an extensive amount of content (see the COURSES page here for access to it) and have been using it to reach millions of people worldwide.


Textbooks. A central focus of my career since 1975 has been creating textbooks. People in my generation had the unique challenge of teaching without the benefit of the time-tested textbooks that our peers in other fields throughout the university were depending on. This turned into a unique opportunity—many of us were able to define the field by writing textbooks.
     My books have sold over one million copies. On the basis of the experience of creating them, I know that a good textbook has the following features:

  • Serves as guiding force and “ground truth” for students learning a core subject.
  • Distills a lifetime of faculty experience for future generations.
  • Provides a reference point for courses later in the curriculum.

These features still have substantial value, and textbooks are here to stay. Some people might prefer electronic versions, but a substantial number prefer physical textbooks (or both). One possible reason: Printed books enjoy the benefit of 500 years of development since Gutenberg while online content has only been around for several decades.

Booksites. Still, online content can vastly leverage printed material in at least the following ways:

  • Provide readily accessible presence on the web.
  • Allow for regular updates and extensions.
  • Provide content types not feasible in print, such as production code, test data, and animations.

These features have substantial value–online content is here to stay.
     Why not just put the book online, as an e-book? Because it was not designed to be read online! For decades, I have been learning how to present the content on the printed page in the best possible light and how to create detailed figures that supplement the text (see the Visualization tab here). Yes, appealing presentation of content is also important for the booksite, but its main purpose is to facilitate searching, following links and scrolling on a variety of devices and to provide access to content types not possible on the printed page. Development of best practices for online content is still a work in progress (and a few centuries behind developments for the printed page).
     Not long after he arrived at Princeton in 1998, Kevin Wayne conceived of the idea of organizing and developing the content for our introductory computer science course online, for immediate use by our students, but also in anticipation of using it for a book someday. The booksites that Kevin and I have developed over the next two decades now consist of tens of thousands of files and have attracted tens of millions of page views. They are unique and valuable resources. A good way to understand what they can contribute is to spend some time browsing through them.

Computer Science: An interdisciplinary approach
Algorithms (4th edition)
Analysis of Algorithms
Analytic Combinatorics

Lecture Videos. Even more ubiquitous than a textbook is the idea of a lecture. Faculty and students regularly gather together, often in a large lecture hall, for the lecturer to present material to the students so that they may learn it. This model has been an essential part of education for a very long time because it

  • Allows instructors to communicate directly with students.
  • Stimulates the development of a “community of scholars”.
  • Encourages great teachers to inspire large groups of students.

These features have substantial value, and lectures are here to stay.
     But it is not necessary for everyone to gather at the same place and time. It has long been recognized that large live lectures have substantial drawbacks because they

  • Require significant time and effort for preparation, which is largely duplicated by instructors around the world.
  • Place students in a passive role, just listening to the lecture (and maybe taking notes).
  • Move at one fixed pace, which cannot be the right one for all students. Most students in a large live lecture are absent, lost, or bored.

Despite these obvious and well-researched drawbacks, large live lectures are the overwhelmingly predominant method of instruction in US universities and many other educational institutions.
     By contrast, making well-produced videos of lectures available to students encourages them to

  • Actively choose the time and place they learn. No one is absent.
  • Actively choose their own pace. Students can speed up the video if bored or slow it down if lost.
  • Review the lecture at any time. Students can review material until they understand it, and refer back to it for exams.

Once one has experienced the ability to consume lectures when and where one wants, going back to having to be at a particular time and place to hear a lecture seems antiquated. It’s like the difference between having to watch Seinfeld at 9PM on Thursday nights and binge-watching episodes on a whim.
     It is true that lectures have to be well produced. I spent 50-100 hours of preparation for each lecture and needed skill in using Unix, emacs, OS X, Dropbox, Illustrator, Keynote, TeX, HTML, MathJax, Mathematica, PostScript, and a dozen other tools I can’t even name. But it was less time-consuming than writing a book.
     The most important development for the future, which is just starting to take hold, is that faculty will adopt online lectures prepared elsewhere instead of preparing and delivering their own, freeing up time for them to decide what material they want their students to learn, to appropriately assess their progress, and to help them succeed.

Online services. In recent years, there has been explosion of research and development in educational technology. I have only been peripherally involved, but it is appropriate to mention here some of the tools that we have been using:

  • Websites built with HTML that provide all course information for students.
  • Tigerfile for managing programming assignment submissions.
  • codePost for grading programming assignments.
  • Zoom for class and precept meetings and office hours.
  • Gradescope for online exams.
  • CUbits to curate, serve, and monetize lectures.
  • Quizzera for online quizzes.
  • Coursera for free online MOOCs.
  • Safari for access to content in a corporate setting.
  • Ed for student Q&A and peer discussion.
  • E-mail for authoritative communication from faculty to students.

Taken together, such tools comprise a fourth component of our model as they have allowed us to effectively scale our offerings to reach large numbers of students. The suite of available tools is constantly evolving and remains an exciting area of research and development. Their true potential is yet to be realized.


I could write a book on this topic, but I’ve written enough books, and it’s not really my area of research expertise. Instead, my intent is to provide context that can help explain the evolution of my thinking on these matters. Much of my thinking stems from a series of invited talks that I gave around the world in the years before the pandemic.

Origins. For more than a century, faculty at colleges and universities would disseminate knowledge by writing papers and books, delivering large live lectures, and leading small groups of students in discussion or problem-solving sessions. In the 1970s, things began to change.

Desktop publishing. My thesis was written out by hand and typed by a secretary, as were my early papers. The process could take over a year. In the span of a decade (the 1970s, roughly) the infrastructure that we enjoy today emerged, where dissemination can be achieved in an instant. I was fortunate to have the opportunity to play a role in this revolution, first at Xerox PARC and later at Adobe. It is hard to overstate the impact of experiencing these changes as an academic. We could write detailed class notes and assignments instead of writing problems on the board in class, and the time between finishing a paper or a book and publishing it shrank from a year or more to a month or less. More important for me was the fact that the entire creative process was in my hands, not left to a secretary or a printer. This aspect of desktop publishing was controversial to some. Didn’t faculty have more important things to do than to worry about fonts and the like? Maybe, but a surprising number of talented computer scientists, from Knuth and Kernighan to Simonyi and Warnock, dedicated themselves to advancing this art, and we are all in their debt. Personally, I spent much of the 1980s and 1990s using state-of-the-art digital publishing tools to create my Algorithms books.

A dream realized. By the turn of the century, it was clear that the internet and the personal computer were going to play a dominant role in the dissemination of knowledge. But the idea had been envisioned half a century earlier, by Vannevar Bush. In 1997, I delivered a speech to Princeton’s first-year class telling that story. This speech is still remarkably relevant today. When Google revolutionized the internet a year later, the last piece of Bush’s vision was realized. We could imagine having access to the world’s knowledge on a personal device, we could disseminate knowledge just by posting it, and anyone could have access to it.

But how, exactly? In the early years, everyone was burned by the experience of advancing technology rendering content obsolete, even lost. A new version of a text editor, or a new editor, or a new company might mean that my online contribution to knowledge would disappear. That did not happen with paper. I can still find my mother’s PhD thesis, written nearly a century ago, at the Brown library. Whatever editor or typesetting system or markup language you are using, are you sure what you are writing now will be readily available in a century? I’m not, and I consider this problem to still be open. In late 1997, I wrote a short letter to the New Yorker making this very point. Not much has changed since, really.

Booksites. As the internet came into daily use in the 1990s, first thing that faculty did was to post assignments, deadlines, exam dates and the like on course websites, a much more convenient way to handle such information than writing it on the blackboard or preparing paper handouts. Naturally, people started putting more and more content on these sites, too. But much of this content seemed specific to the course and ephemeral, when some of it was destined for a textbook.
     When Kevin Wayne began working with me in 1998, he started putting significant amounts of content on a webpage, separate from any course offering. For nearly a decade, we used this page as a development laboratory for our new textbook. Everything went on the web, but we could cherrypick the information there while creating the coherent story needed for a textbook. Once the book was published, the page became a valuable resource for readers, providing all kinds of content that unsuitable for a book. Thus was born the concept of a booksite. It was so successful that we created another one for Algorithms, which significantly increased the appeal of that book, even though it was already a bestseller. Then I did the same for Analysis of Algorithms and Analytic Combinatorics, making them much more accessible to many more people than the books alone could be.
     Our booksites now have tens of thousands of pages that draw millions of unique visitors each year and tens of millions of pageviews.

MOOCs. Should we include videos of some sort in our booksites? It is a natural idea, but it just never seemed worth the effort. Things changed in 2012 when Daphne Kollar and Andrew Ng formed Coursera and encouraged educational institutions to vastly expand their reach by putting lecture videos online. Having just revamped our lecture slides for the fifth or sixth time, Kevin and I realized immediately that they would be perfectly suited to doing this, and we produced Algorithms for the Coursera platform. It was immediately successful and has already reached over 1 million people.
     Over the next several years, I recorded over a hundred hours of videos that are the basis for six Coursera courses. For me, the appeal of these courses is that they make the content accessible to a huge number of people whoo otherwise would not have access to them. I’ve always been uneasy about the model of issuing certificates or otherwise trying to compete with existing educational institutions. My preference is to develop materials that can enable any of the millions of teachers around the world do their job more effectively and efficiently. That is what the “21st century model” is all about. Our experience is that many faculty are reluctant to have their students take a MOOC, but we are often able to convince people that watching videos in conjunction with the booksite and textbook can free time for them to work on curating the material, developing assessments, and helping their students succeed.

Moving my Princeton courses online. After recording the last lecture in our introductory course Computer Science in the early summer of 2015, I was exhausted and thought to myself that it would be very difficult for me to deliver that lecture again in the classroom. I had spent many, many hours preparing the slides for that lecture (and all the others). One of the most important aspects of the lectures was that the lecture slides were very detailed, but the information on a lecture slide would appear gradually, controlled by a remote in my hand. Creating and checking these “builds” was very time-consuming but also excellent preparation for the lecture. I didn’t need any rehearsal, as I knew what was going to appear on the screen each time I advanced the remote, and just talked about it. One of the last slides in the last lecture was a simulation of a CPU circuit, with over a hundred builds. To deliver that lecture again in a year, I would need to revisit all the decisions I made in sequencing those builds—I knew that would be a difficult and time-consuming job. And why do it? I couldn’t do as good a job as just captured in the video. And if I couldn’t do it, no one else could either.
     I knew then that the days of me or someone else reading my slides to their students in a large lecture hall were over. In September 2015, I delivered a “last live lecture” where I explained the change to the students, and haven’t looked back.

The pandemic. The full story remains to be written, but having moved my lectures online, the spring of 2019 went relatively smoothly in my courses. I promised the students that we would provide them with an experience comparable to that experienced by the thousands of students who have taken it in the past. I think that having the lectures online provided our course staff with the stability and breathing room needed to develop new ways of interacting with students and we were able to approach that ideal, despite the circumstances. My teaching ratings were among the highest I have ever earned. Moreover, plenty of students and faculty at other institutions were able to take advantage of our materials to help with their transition of online teaching.


I am often asked how the pandemic has affected my teaching. The answer is that the most important effect has been that no one hassles me about not having in-person meetings with students! My opinion is that the new ways of teaching that embrace technology are so much more effective and efficient than the old ones that do not.
     Sure, there are plenty of situations where in-person instruction is valuable. Most teachers are drawn to the profession by the pleasure of the experience of kindling the light of understanding in a student or a group of students. But insisting that all instruction be done this way and only this way is counterproductive.
     Rather than mapping out strategies to get back to old ineffective and inefficient teaching methods, we should be brainstorming ways in which we reach out to more students than ever before and taking them farther than ever before. To conclude, I’ll offer some comments on the way I do things now, in an attempt to illustrate what is possible.

Lectures. Personally, I cannot conceive of building a course based on large live lectures again. Many people have created quality video content during the pandemic and are seeing the benefits of using it. Yes, good online lectures are difficult to produce, but the investment produces a much better experience for students and is certainly worthwhile when amortized over future and expanded usage.

E-mail. This old-school technology is effective for synchronizing a course. I send an e-mail to all officially registered students each week describing their responsibilities for the week. In my experience, students take such e-mails seriously.

Personal interaction. When I was teaching in a lecture hall with 400+ students, I certainly had little personal interaction with students. Now, when I walk across campus or attend a large conference, I am often approached by a student who seems to know me. Watching lectures regularly in a private setting gives each student a sense of a personal relationship with me.

Grading. Anyone not using online tools for grading needs to rethink what they are doing. In our first-year classes, we grade hundreds of student programs in a matter of hours each week, with high standards for personal feedback and fairness. In my advanced class, I grade dozens of advanced mathematical derivations in well under an hour—speaking of personal interaction, I get to know those students relatively well. And in both classes, I can do assessments that are auto-graded. Zero time spent grading is tough to beat. And these experiences only scratch the surface, with sea-assessments and crowdsourcing already proven to be effective.

Discussion forums. Online discussion forums have replaced office hours, having proven extremely effective and efficient in helping us answer student questions. It took some experience for us to guide students in using this resource effectively, but it is now indispensible.

AND THIS is all from the perspective of decades of clinging to old ways and having to be convinced to adopt new approaches. As ever, the next generation, unburdened, will take us places we cannot even imagine today.

Professors Behind the MOOC Hype (Chronicle of Higher Education)
A 21st Century Model for Disseminating Knowledge (RS invited lecture)
A 21st Century Model for Disseminating Knowledge (video of MIT lecture)

Computer Science for All

To most people, this exhortation means “everyone should learn how to code.” I completely agree that everyone should know how to code, but I also think that most if not all college students should know fundamental concepts in computer science, which are among the most important and impactful intellectual achievements of the last century.

What is Computer Science?

One can spend a day or a week or a month studying this question. People have been debating it for many decades. I prefer to think about the definition along the following lines:

computer science

The quest for knowledge about phenomena surrounding computation, and the application of that knowledge for the betterment of humankind.

OK, “for the betterment of humankind” is unnecessary, but I’m leaving it in. When people use computation no good purpose or for evil, they can call it something else.
     Much of my career has involved grappling with the question a different way. As founding chair of the department of computer science at Princeton, I was soon faced with the need to develop a new introductory course. I strongly feel that computer science belongs in every college curriculum, like mathematics, economics, physics, biology, and other core disciplines. So I asked myself “What should every college student know about computer science?” After 25 years of work, our book (with Kevin Wayne) Computer Science: An Interdisciplinary Approach, answers this question by demonstrating that computer science is about:

  • Learning to write programs in a modern programming language.
  • Realizing that know one programming language makes learning another one relatively easy.
  • Understanding concepts like type checking, modularity, recursion, and data abstraction, which make modern languages effective.
  • Studying classic data structures and algorithms and their application in practical situations.
  • Knowing how to estimate how much time and memory programs use.
  • Appreciating fundamental concepts in the theory of computation: universality, computability, and intractability.
  • Gaining insight into how modern computer processors are built, including complete design of a simple processor.
  • Gaining insight into the strong relationships between the programs we write, the theory of computation, the computers we use, and the natural world.
  • Learning the contributions of Turing, von Neumann, Boole, Shannon, and other giants.

In my view, a person who has studied these has the foundation needed to use computers effectively. Conversely, a person lacking this basic knowledge will struggle to compete in today’s world.
     Many years ago, people debated whether CS is a science at all, and whether it deserves any place at all in the college curriculum. An acquaintance once told me that one of his colleagues made this argument on the floor of his faculty senate:

“A computer is a useful man-made artifact, like a refrigerator. We don’t have a department of refrigerators, so why should we have a department of computer science?”

Sure, CS is useful and interesting, the argument would go, but what does it tell us about the universe? Fortunately, amazing progress across the board has left such arguments by the wayside. Now, there’s little question that computation is not just useful but also underlies many natural processes, and that understanding computer science is the key to progress in many other fields of science.

One Course
Even in the 1960s, scientists realized that computers were going to be indispensable in their work, so courses would spring up in every department to teach students what they needed to know for later courses. But these courses often suffered from a “department of refrigerators” attitude and essentially were replacing labs that used slide rules and calculators with labs that used computers. And they were doing it far too slowly. For example, I was horrified to realize that my son, a potential physics major at Princeton, spent an afternoon in the lab computing the mean and standard deviation of a bunch of numbers on a calculator, in 1994 (!).
     The attitude that the computer is nothing more than a tool persists to this day in many circles. As a result, many universities, offer several courses in computing, one or more per department, each serving potential majors in that department. This approach is flawed because:

  • The courses teach programming in a specific language, not computer science.
  • They are not taught by professors of computer science, while introductory courses in other disciplines are taught by professors in that discipline.
  • They do not prepare students for later courses in computer science. This is the most important flaw.

I was determined to change this at Princeton and to try to develop an existence proof for others. Little did I know that it would take over 25 years to do so.
     Computer scientists can be often part of the problem, too. All around the world, many people have been orienting their introductory course towards future cubicle dwellers and ignoring the needs of others. Indeed, at many prominent institutions, enrollment in computer science courses is strictly limited, leaving most students wholly unprepared with respect to computing. I consider this to be responsible and bordering on the immoral.
     Up until the 1980s, Stanford did not offer an undergraduate CS degree and would counsel students to study something else as an undergraduate and take CS as a graduate student. While not a “department of refrigerators” attitude, I can attest to the fact that it certainly made building new departments at Brown and Princeton more challenging.
     From the beginning, I was determined to build a single CS course at Princeton for first-year students that was open and accessible to everyone, like introductory courses in other disciplines. We would teach fundamental concepts in the discipline and develop skill in exploiting the power of the computer. Our examples and assignments would all address interesting practical problems, ideally in some other discipline, while at the same time teaching some fundamental CS concept. To get this going, I asked students majoring in other subjects to bring back to us problems in their disciplines where computing should play a central role. They brought back many exciting examples, thus illustrating the broad reach of computing, even to the cubicle dwellers.
     One immediate roadblock was the lack of a suitable textbook that could command the respect accorded classic texts in other fields. From the beginning, development of the textbook has gone hand-in-hand with development of the course. Indeed, the effort went far beyond just a textbook, once Kevin Wayne joined the effort. During the 2000s, we developed extensive online content for the course, and during the 2010s, we put the lectures online, which are now available for use around the world. Finally, in 2016, our textbook Computer Science: An Interdisciplinary Approach was published.

Progress Report

I was optimistic from the start, but success has been at a scale I could not imagine. In the 20th century, students would say that taking a course in computing is bad for your social life. Now, at Princeton it is the case that not taking a course in computing is bad for your social life. For many years, it has been the highest-enrolled course at Princeton.
     Beyond the success of the course itself, the downstream impact has been way beyond expectations:

  • Our second course (Algorithms) is also consistently among the top five highest-enrolled courses at Princeton.
  • CS is the highest-enrolled major at Princeton.
  • Thanks to our 21st century model for disseminating knowledge, other institutions around the world are able to adopt this approach.

Yes, enrollments are up everywhere, and there are some universities that have matched this level of success, but nationwide totals show that a large majority of institutions are not coming close to adequately serving their students with appropriate CS instruction.
     To reiterate, my position is that “CS for All” has to begin with an introductory college course suitable for all students, based on a textbook that covers the fundamentals, to prepare student for success in a lifetime of engaging with computation, whatever their chosen pursuit. I set out to prove this concept in 1992 and am now declaring victory.

The Discipline that is Transforming Higher Ed (Chronicle of Higher Education)
Computer Science for All, Really (Princeton CS Department)

Algorithm Science


This terminology might seem a bit odd to many people at first blush, but when I tried it out on a some colleagues, they agreed that it perfectly describes the main thrust of the field of research introduced by Don Knuth and his books The Art of Computer Programming (to which I have devoted my career). His name for the field is “analysis of algorithms.” With respect, I now feel that “algorithm science” is much more descriptive and appealing.
     I wish I had thought of this decades ago. My book Introduction to the Analysis of Algorithms with Flajolet might be named Mathematical Methods for Algorithm Science, as would our international AofA and ANALCO meetings. And the chapters in Algorithms and Computer Science that cover the basics might be titled Algorithm Science.
     I am writing about this here because I think that this field of research deserves more attention as it has been foundational in the development of our vast computational infrastructure.

The problem. Everyone using a computer has often wondered how much time a given program will need to finish its job. In many cases, such as adding a column of numbers in a spreadsheet, the computer is so fast that the time taken is negligible, but in many other cases, such as a guidance system in an airplane, it is critically important to be able to guarantee that the computation will finish on time. It is about as easy to write a slow program as a fast one. Is there a systematic way to be able to tell the difference?

Algorithms. Large software systems can be very complex, but it is often the case that studying performance reduces to the study of particular core computational problems that have been the subject of decades of research, the kind of material covered in my Algorithms books. The idea of an algorithm separates a computation from a particular device. An algorithm is a step by step description of a computation that a developer can use to implement a program on any given computer. The time needed by the program certainly depends on the system and the computer, but properties of the algorithm are also relevant. By studying such properties, we can gain insight and understanding about the algorithm, and, by extension, any implementation. It is typically easy to identify important properties. How many comparisons does a sorting algorithm use? How many edges are examined by a graph-processing algorithm?

Algorithm engineering. The process of implementing an algorithm on an actual computer is quite simply called programming. In mission-critical applications, the process is a bit more sophisticated and often called algorithm engineering. Loosely speaking, algorithm engineering is the process of choosing and implementing an algorithm to address a particular application on a particular machine, with careful attention to performance. Most serious program development involves algorithm engineering, and most programmers love to do it. Typically, the process ends with an “optimization” phase, where a programmer finds a way to improve performance by matching match some property of the algorithm to a capability of the machine.
     Unquestionably, people who build computer systems pay attention to performance. No one would buy a cellphone that takes a minute to wake up if a similar one takes just a second. So system builders test performance extensively by running experiments to see how much time is needed to complete tasks that their customers care about. This approach is successful and widely deployed. Nowadays, people rely on standardized benchmarks run by trusted third parties to decide whether a new computer is sufficiently faster than an old one to be worth the expense.
     One drawback is that people may be drawn to “designing to the benchmarks”. One extreme example of this is “Timsort”, which was hailed for a time as being novel and faster than any other sorting algorithm because of its performance on benchmarks. Closer examination showed that it adopted a well-known approach that performed exceedingly well on a few of the benchmarks, and that it actually was not even correct. It uncovered a shortcoming in the benchmarks, not a new algorithm.
     A better approach is to take advantage of understanding both the algorithm and the machine instead of relying completely on benchmarks. While useful, benchmarks, on their own, generally do not provide much insight or understanding about what is actually happening.

Theory of algorithms. A widely-accepted theory classifies algorithms by developing bounds on their worst-case performance. This approach provides an appealing framework based on simple mathematical tools and has supported a Golden Age of Algorithm Design. The drawback is that it does not provide enough information to be able to predict performance in practice or to compare algorithms. The constant factors matter, and, worse, the input is typically not the worst case. The most important reason for practitioners to be skeptical of results in this literature is that many, many authors ignore or are unaware of these facts.
     Typically, algorithms developed in this community have but one purpose: to enable the proof of a theorem. As such, they can become exceedingly complicated and arcane—no one should consider implementing them. As my late friend Philippe Flajolet once put it:

A large fraction of the theoretical computer science research community reverted to worst-case analysis based on simple tools from computational complexity. In all too many cases, this has resulted in an excess of its own, with works culminating in teratological constructions both devoid of mathematical simplicity and elegance and bearing little relevance to the practice of computing.

To save you the trouble of looking up the definition of “teratological”, here it is:


  1. abnormal in growth or structure.
  2. of or relating to teratology.


  1. The scientific study of congenital abnormalities and abnormal formations.
  2. Mythology relating to fantastic creatures and monsters.

Philippe told me that he was proud of this word choice as it leaves ambiguous whether one considers this type of algorithm to be abnormal or just a fantastic creature. Certainly his point is that such algorithms have little to do with the real world.


In algorithm science, we take a middle road between pure benchmarking and pure theory. A problem with the theory of algorithms is that it pays too little attention to the real world; a problem with benchmarks studies is that they pay too much attention to the real world. The middle road, the goal of research in algorithm science, is to learn properties of algorithms that can support algorithm engineering and experimental studies in practical situations, independent of any particular machine. More formally, I propose this definition:

algorithm science

The application of the scientific method for the design and analysis of algorithms—developing mathematical models for characteristics of algorithms and their inputs, formulating hypotheses relevant to the study of performance on specific classes of computers and systems, running experiments to validate the hypotheses, and iterating as appropriate with the goal of improving performance.

The scientific method. Since the enlightenment, our understanding of the world in which we live has expanded dramatically because of universally accepted principles about how to learn things and gain confidence that they are true. Applied to the study of computer programs, these principles lead to the following intuitive approach.

  • Create a mathematical model.
  • Develop a hypothesis about real-world performance.
  • Run experiments to validate the hypothesis.
  • Iterate on the basis of facts learned.

Each of these steps presents significant challenges in any scientific endeavor. The irony is that they can be easier in algorithm science than in many other sciences.

Mathematical models. The starting point is to identify properties of the algorithm to be studied. Knuth does this by assigning variable names to the frequency of execution of each instruction in the program. Then the mathematical model is simply a linear combination of these variables: the sum over all instructions of the product of the frequency of execution and the cost.
     Understanding costs require understanding of a particular computer system. This is the worthy and important goal of algorithm engineering, where researchers seek to leverage that understanding to develop improved implementations. Importantly, it is not always necessary to know much about the variables to improve performance, because reducing the total cost by reducing costs for the most frequently executed instructions is often effective. But this approach has limitations (for example, when there are tradeoffs between different groups of instructions with similar costs) that can be addressed with the help of algorithm science.
     The values of the variables are dependent on the inputs to the algorithm. The model must take properties of the inputs into account, as must any experiments. By just developing bounds on the worst case, the theory of algorithms avoids this problem. In algorithm science and engineering, learning properties of the inputs to be expected in practice is an essential first step. Often, we are able to assume that the inputs are random in some sense, or to add randomization to the algorithm, so that our analysis becomes probabilistic. Of course, any such assumptions need to be checked by experiments on “real” inputs of the type that might be expected in practice (benchmarks).
     Frequency-of-execution variables are the focus of algorithm science. We build mathematical models describing their values given certain assumptions about the inputs and then run experiments to test those assumptions and refine the models. Knuth has taught us that such models can lead to fascinating intellectual challenges.

Experiments. We can simply implement the algorithm, instrument it to determine the values of the variables, and collect results. Many systems provide profiling capabilities to automate this task. Experiments are relatively cheap. Unlike some other scientists, we don’t have to kill animals or send equipment to space or anything of the sort. We can actually run millions or billions of experiments with ease. For this reason, it is typical in algorithm science to run the experiments first and use the results to help develop an appropriate mathematical model.
     Importantly, one reason that many, many algorithms developed in the theoretical computer science community are not susceptible to algorithm science is that no one has implemented them (or would want to, or even could). In algorithm science we take the point of view that we want to study algorithms that have the potential to be useful in practice. To paraphrase Knuth: “If I can’t run it on my computer, I’m not interested in studying it.” His books are testimony to the fact that there are many, many algorithms in this category.
     In the scientific method, the hypothesis is not useful unless it is falsifiable. That is, it must be possible to conceive of an experimental observation that disproves the idea in question. This is a key distinction between algorithm science and the theory of algorithms. Falsifiable hypotheses are hard to come by in the theory of algorithms; they are central to algorithm science.

Approximations. At the beginning of my career, I was very excited to see that we could develop exact models that can predict results with full precision. It was particularly exciting to capture oscillatory behavior.
     In many, many practical situations, analyzing the leading term is enough, and provides much more insight than running experiments alone. A better focus on useful approximations early on would have been helpful in expanding the use of algorithm science. Unfortunately, much of the research community in theoretical computer science settled on approximations that are not particularly useful in studying performance in practice.

O-notation considered harmful. For many years, I included a slide with this title in my lectures and talks describing this encounter with a superstar researcher at a conference on the theory of algorithms:

SS: Algorithm A is bad. Google and Facebook should be interested in my new Algorithm B.
RS: What’s the matter with Algorithm A?
SS: It is not optimal. It has an extra O(log log N) factor.
RS: But Algorithm B is so complicated as to be unimplementable, lg lg N is less than 6 in this universe, and that is just an upper bound. Algorithm A is certainly going to run 100 times or more faster in any conceivable real-world situation. Why should Google and Facebook care about Algorithm B?
SS: Well, I like it. I don’t care about Google and Facebook.

And I can testify that the audience seemed to be on his side, not mine. Just to be clear: I thought the paper was an insightful mathematical contribution. But I felt strongly enough that it is very misleading to claim relevance to practical computing that I was willing to confront a superstar.
     In this case, the hypothesis that Algorithm A is faster than Algorithm B is falsifiable. One could conceive of implementing them and learning that B is 100 times faster, but would that be a worthwhile endeavor when the outcome is so patently obvious?
     Worse, use of O-notation very often leads to hypotheses that are not correct and also not falsifiable in practice.
An alternative to O-notation. Suppose that AN is a variable that represents the running time of a program with N inputs and that we can prove that AN / N2 approaches a constant as N grows. Here are two ways to express that fact mathematically:

theory of algorithms     AN = O(N2)
algorithm science         AN = cN2 for some constant C.

We use the more precise notation of algorithm science because it enables us to develop machine-independent falsifiable hypotheses.
     The simplest such hypothesis is the doubling hypothesis. In this case, the hypothesis would be “If you double the size of the input, the increase in the running time will approach a factor of 4.” This hypothesis is machine-independent and falsifiable.
     And it goes both ways. If your program takes four times as long to finish when you double the size of the input, a reasonable hypothesis is that its running time is quadratic.
     I wish I had thought of this years earlier than I did, but at least it has made it into my Computer Science and Algorithms books as a very simple way for any programmer to gain some understanding of running time.

Advice for practitioners. My purpose is not to be critical of anyone but to help practitioners navigate a huge literature filled with misleading claims, actual and implied.
     If you’re looking for a solution to a practical problem and run across a paper that claims an algorithm to be practical based on a O- analysis but exhibits no evidence of anyone ever having implemented it, I’d ignore it. Do you really want to be the very first person to ever implement an unproven algorithm? Believe me, I have done it many times and cannot recommend the experience.
     It is unwise to ignore performance during development. Typically, software systems need to be scalable, and you should know if you’re heading down the path towards unacceptably bad performance. Using the doubling hypothesis is not very difficult and can help avoid surprises later on.

THE prototypical example. Anyone dubious or confused about these ideas would do well to read C.A.R. Hoare’s 1960 paper Quicksort, where he introduced the algorithm that remains today the sorting method of choice and provided an analysis that exemplifies algorithm science.
     After describing the algorithm, he introduced the idea of randomization and then provided a mathematical analysis showing that the expected number of compares for random keys is ~ 2N ln N and the expected number of exchanges is one-sixth the number of compares, so that the running time is ~ cN ln N for some machine-dependent constant. With doubling, we can pose this machine-independent hypothesis:

If you double the number of the inputs, the running time of Quicksort will increase by a factor of about 2 + (2\ln2)/ln N.

While he didn’t explicitly state this hypothesis, Hoare’s paper implicitly describes a doubling test, as he gives running times Tn for files with N random keys that double from 500 to 2000. It is amusing to calculate that these values validate the hypothesis.

     If you want to validate the machine-independence of the hypothesis, you can download Quicksort from our booksite and test it on your own computer for thousands or millions of times as many inputs. Hoare’s paper is the prototypical example of algorithm science because it is just as useful in predicting performance on todays computers as it was on the particular computer he was using in 1960 (and all those developed in between, not to mention those developed in the future).
     Note that the assumption that the keys are random may not hold in some situations. Rest assured that variants of the algorithm have been studied and tested that handle such situations. The most prominent such case is when large numbers of equal keys have are present—see the RESEARCH page here.

Bottom line. Algorithm science has played a critical role in the development of our computational infrastructure, and continues to do so. From Google to genomics, the progress we have seen over the past several decades would not have been possible without algorithm science. Admittedly, no one has been calling their work algorithm science, but if it walks like a duck… Certainly, the most successful endeavors have been based on extensive mathematical modeling and experimentation, often exploiting knowledge about foundational classical algorithms.
     I would say that algorithm science is in its infancy, but I was there when it actually was in its infancy—-when professional programmers coded in assembly language while binary search and linked structures were the province of pointy-headed intellectuals. Let’s say that algorithm science is in its teenage years. There are many, many, great algorithms waiting to be discovered and studied.

Further reading. The possibility of algorithm science was firmly established by Knuth. One cannot read The Art of Computer Programming without coming away with a full appreciation for the idea. Yes, the books do lack implementations in a mainstream programming language, but there is no question that there is sufficient detail to develop and study implementations with a proper scientific attitude.
     You can find a thorough introduction to algorithm science in the context of a particular example in Chapter 1 of my book with Flajolet An Introduction to the Analysis of Algorithms. Our intent in writing this book was to provide for students the mathematical background necessary to appreciate Knuth’s work (and to be able to properly study algorithm performance).
     To see the importance of algorithm science laid bare in the context of an industrial-strength system, read about LEDA, by Mehlhorn and his collaborators.
     The third and fourth editions of my Algorithms books are filled with examples. Pick your programming languge: C, C++,or Java. As I realized that more and more people were using my code when building systems, I thought it irresponsible to be recommending particular algorithms and implementations without using the scientific method to build confidence in the recommendations I was making. More details on this story are on the RESEARCH page here.
     Other outstanding examples of algorithm science are found in Bentley’s Programming Pearls books and Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox by Sanders, Mehlhorn, Deitzfelbinger, and Dementiev.


What is the computer doing? How do we know? I have always found that questions like these are often best answered through visual imagery.
     Following is a review of examples that I have developed throughout my career that I feel have been particularly successful. Together, the images comprise a personal story, illustrating in chronological order some of the ways in which I was able to exploit computer graphics and desktop publishing as they developed.

1975. Quicksort

My Ph.D thesis was typed by Phyllis Winkler, who also typed Knuth’s books. there was little opportunity for graphics. Coding was one-run-a-day with punched cards and a line printer, but I was able to create these patterns.

The best case of Quicksort for M = 2, 3, and 4.

1978–79. Xerox PARC

Just three years later, I visited Xerox PARC and leaped into the future. Using Smalltalk on an Alto (arguably a better programming environment than many we use today), I created animations like this, comparing MST algorithms. Diagrams based on these images are now found throughout my algorithms books, and these animations are now a staple in our algorithms MOOCs.

Kruskal’s algorithm (left) and Prim’s algorithm (right)

Also, Leo Guibas and I, studying balanced trees (see RESEARCH) and were able to use an experimental color laser printer to make color images like this one. It would be decades before images like this could appear in the research literature.

A red-black search tree

1979–83. Algorithms, first edition

Back in the real world, good illustrations were a priority for my new book Algorithms. My students helped me produce frontispiece drawings and this cover image using equipment from Andy van Dam’s research lab:

Inside the book, most figures needed to be drawn by hand, using pen-and-ink with Letraset rub-off type. It’s hard to imagine doing that kind of work today, and the job would have been impossible without the help of my wife Linda, who did many of the drawings.
On sabbatical in Paris, we ran out of G’s and E’s and had to scour the bookstores in the Left Bank to find substitutes.

Heap insertion (pen-and-ink)

1983-85. BALSA

After finishing the book and returning from sabbatical, I was eager to use animations like those I developed at Xerox to teach algorithms to undergraduates. With several colleagues at Brown, I embarked on a project to do just that. My student Marc Brown oversaw the development of BALSA, a system with many advanced features that supported creating and using the animations in lectures. From sorting to simplex, we animated nearly all of the algorithms in the book. Those visualizations formed the basis for what was to come.


Search trees

2D tree with history

2D tree

Breadth-first and depth-first graph search


Random number generation

Stable marriage

1986–88. Algorithms, 2nd edition

For the second edition of Algorithms, the “desktop publishing” revolution was well underway. The mainstream was pushing towards compromises like Microsoft Word, but I was much more interested in complete control over every spot on the page that was provided by TeX and PostScript. Creative control over the process of producing beautiful books was intoxicating. After having done many long papers, TeX was easy. But what to do about illustrating algorithms and data structures? Our BALSA animations showed the way, but there was no easy path to get them onto the printed page.
     After much experimentation, I dove into building a system for producing the illustrations and integrating it into the text and the code. The goal was to make it so that “this example illustrates the operation of this program” literally true. I annotated my program code with “interesting events” as we did in BALSA and the book text with references to the figures and programs. Then, I convinced Dave Hanson to write a shell script called loom that would drop the program code into the text (with appropriate TeX commands to format it) an also run the code to produce PostScript code that would draw the figures and drop that into the text, as well.
     The figure-drawing engine was a PostScript data-structure drawing library dsdraw that I created as I wrote the book. When I needed a new visual representation, I would design a text representation to be produced by the program, then give that as input to PostScript functions that would create the drawing. Developing these functions was an exercise in algorithmics that was fun and stimulating.
     The result was a book filled with high-quality visuals that would have been difficult and expensive to produce any other way. Not all were successful, but I am proud of the result. The figures are certainly a long, long way from pen-and-ink drawings by hand. And applications like Adobe Illustrator were only just coming into existence.
     The idea was certainly ahead of its time. Not many CS books, even today, have visuals of this variety and quality. The following examples were all created with dsdraw.

Insertion sort (labeled bars view)

Insertion sort (dots view)

Shellsort (bars view)

LSD radix sort

Building a heap

Building a 2-3-4 tree

Building a red-black tree

Union-find forests

Computing the convex hull

Subdivisions induced by a 2D tree finding the closest pair

Sweep line to find intersections

Voronoi diagrams

DFS in a digraph

Breadth-first search

Breadth-first search in a larger graph

Network flow

1990–2003. Algorithms, third edition

Inspired by the work of Tufte and empowered by my experience in producing the first two editions, I set out to rewrite Algorithms completely for the third time. The main focus was to fully embrace algorithm science, but another was to develop an innovative book design that could exploit the available technology. I spent several years thinking about the design.
     One early decision was to put the visualizations on sidebars with standalone commentary. Another was to be sure that their information content was commensurate with the space they occupied. Another was to be sure that they definitely were informative and definitely were not deceptive. These are all bedrock principles of Tufte’s teaching. Since my figures were being produced by my code, I was confident that I could achieve these goals.
     I realized early on that the code itself was going to have to be industrial strength (at least good enough to support the extensive experiments called for in algorithm science) so that instrumenting them to produce visuals would be cumbersome. Fortunately, it was easy to implement the algorithms themselves in PostScript, which opened up new avenues for design.


Shellsort (five different input models)

Finding the median

Batcher’s networks

Node splitting in a red-black tree

Clustering in hash tables

Ternary search trees

B-tree construction

B-tree page occupancy

Breadth-first search

Shortest-paths trees

1988–2005. Analysis of Algorithms

Working on our book Introduction to the Analysis of Algorithms with Philippe Flajolet provided an opportunity to exploit my skills in PostScript programming to provide novel and informative images depicting mathematical functions, such as the ones that follow. Remarkably, these images each are produced by only a few lines of PostScript code, typically less than a dozen.

Quicksort distribution

Oscillations in merge sort

Binomial converging to normal

Root rank distribution for random binary trees

Root rank distribution for random AVL trees

2005–2011. Algorithms, fourth edition

The goal for the fourth edition of Algorithms was to emphasize its utility as a textbook as opposed to a reference book, drawing the best and most important fo the material from the previous editions. Kevin Wayne joined me in this effort.
     From a production point of view, the most important change from earlier editions was that I switched to working in WYSIWYG with InDesign. One the one hand, this switch was very painful, as my existing code and text base was dependent keeping programs and figures in independent files and using scripts and other tools to integrate them, and applications like InDesign do not embrace this approach (and still do not do so, which I find frustrating to this day). On the other hand, leaving batch processing behind was liberating and opened up new avenues of design.
     Another important development was that I could use Illustrator as an alternative to programming in PostScript. Many of the successful visualizations from early editions play a central role, of course, but Illustrator made it easy to annotate them. Indeed, we were able to describe many things with small expressive annotations that were covered with long figure captions before.
     My bargain with my longtime editor Peter Gordon was that I would only do this fourth edition if it could have color. After nearly thirty years, I could finally show red-black trees as they were originally conceived.
     Again inspired by Tufte, we were able to depict the results of experiments with visuals instead of tables of numbers, using one dot per experiment overlaid with Tufte plots.

2000–2016. CS textbook

From the beginning, a primary goal for the intro CS course I was creating was to have visualization as a primary component. Since Papert’s turtle graphics, it has been known that writing programs to draw pictures is a very effective way for beginners to gain experience.
     One of the first assignments I developed, with the help of a summer student, was N-body simulation. With a high-school physics equations nestled inside two for loops, it was an ideal assignment that appealed to students immediately and remains in the course to this day. It is a data-driven program that also provides an outlet for student creativity, as they can create their own solar systems and watch what happens.
     We also worked with bitmap graphics and had students create visualizations of the Mandelbrot set, starting with asterisks in TTY output like my Quicksort drawings. Taking students through Mandlebrot’s experience of uncovering the wonders of the set as computers and graphics resolution improved is another component of the course that remains to this day. They hardly notice that they are learning about 2D arrays.
     As the class grew, assignments with animations became difficult to grade, so we needed printed output. That was a challenge for a time—we actually had students write C programs that produced PostScript programs as output.
     Another component that was present in the course from the beginning was the CPU circuit. I needed to have a full computer where every switch was visible. I was confident, but took me at least ten years to meet this challenge. I finally got it done as an experienced Illustrator user, though I came very close to building a circuit simulator with integrated layout that also could be used to animate the circuit in action.
     As Kevin Wayne and I developed the presentation slides and the printed book for the course, I became adept at creating the content in InDesign and Illustrator and was able to fully populate the book with illustrations supporting the key concepts.
     The examples that follow are a small fraction of the visual material in the slides and the book.

Invited talks and MOOCS

Since 2000, I’ve been creating slides for invited talks and MOOCs, primarily using Keynote. These slides are very visual and can mostly speak for themselves on the COURSES and TALKS pages here.

The sudden opportunity to develop MOOCs came with the realization that the lecture slides that Kevin and Wayne and I had developed for the CS and Algorithms courses were going to be perfectly suited to the task. Before long, the realization that these slides were going to be viewed by hundreds of thousand of people, (not just hundreds) set off a decade-long effort to produce slides of the best quality possible. I would spend 50–100 hours per hour of recorded material creating these slides. Many of them highlight images already shown here, so I’ll avoid rehashing them.

The analytic combinatorics course is different. It presented me with an opportunity to create all-new visuals for Analytic Combinatorics. The experience I had gained from twenty books and four MOOCs certainly shows in some of these compelling new images.

Analytic Combinatorics

In 1977, on the first day of my first FOCS conference, a stranger called my name from across the room, came over to me and said “I think we have a formula in common”. It was Philippe Flajolet—of course, he was right. Studying two completely different problems, we ended up with expressions involving the Gamma and generalized zeta functions that were virtually identical. Actually, not so surprising, since we both learned the method from Knuth, but, still, we both wondered if there was some more general mechanism at work.
     That was the beginning of a decades-long working relationship, culminating in the publication of our book Analytic Combinatorics in 2009. Philippe and I met on numerous occasions at Brown, Xerox PARC, INRIA, Princeton, and at workshops and conferences all over the world as joint research papers turned into a book, then two books, then a life’s work. Tragically, Philippe died suddenly in 2011 after a brief illness. This is my opportunity to pay tribute to Philippe by explaining the genesis of his accomplishments to as broad an audience as possible. Some of the text is drawn from tributes I have written in the past.


It may be a while before this term makes it to Webster’s or the OED, but when it does, the definition will look something like this:

analytic combinatorics

A calculus that aims to enable precise quantitative predictions of the properties of large combinatorial structures. The theory has emerged as essential both for the analysis of algorithms and for the study of scientific models in other disciplines, including statistical physics, computational biology, and information theory.

The theory is built on two main components, with the generating function as the central object of study. First, the symbolic method is used to transfer specifications of combinatorial structures to equations involving generating functions. Typically coefficients of the generating functions are counting sequences. Second, the generating function is treated as a function in the complex plane, and complex analysis is used to extract the information of interest (asymptotic estimates of the coefficients, in the simplest case). The essence of analytic combinatorics is the development of theorems of sweeping generality that can greatly simplify the process for a host of practical applications.

Origins. One key to understanding the development of our approach towards computer science and mathematics is to consider the dramatic changes in the world during the period when Philippe and I came of age as we made the transition from students to teachers and researchers. During this period, computation changed the world. In the 1960s, when we entered school, every bit in a computer was implemented with a physical device, so computers only had thousands of bits; we communicated with our computers via punched cards; our papers were typed by secretaries; we learned mathematics as undergraduates; and little or no computer science was taught to undergraduates. By the 1970s, when we started in research and teaching, computer memories were implemented with integrated circuits, so computers had millions of bits; we communicated with our computers via CRT terminals, with no apparent physical restriction; we used word processing and typed our own papers; and we were expected to teach computer science, not mathematics. On reflection, this change was more profound than the emergence of the personal computer or the internet. During this transition, everyone in our generation experienced the excitement of being able to not just experience, but work to influence the profound changes that were upon us. Most exciting were the research opportunities, in every direction. A full description of this period could fill volumes.

For Philippe and I, and many others in our generation, one particular realization was immediate: Passing knowledge on to the next generation was going to be a significant challenge. We were going to have to develop the courses in computer science that we wanted our students to take, essentially from scratch. On reflection, this challenge was also a once-in-a-generation opportunity and a tremendous responsibility. The best of the textbooks that were developed in those years are still in use today. I believe that Philippe took this responsibility seriously and that it was a guiding force in much of his work.

Analysis of algorithms. In the 1970s, the whole idea of “computer science” was in question. In what sense is the study of computation a science? Philippe and I were fortunate to be grounded in the rich and voluminous work of Knuth, which argued convincingly for the development of a science where we could build mathematical models for performance characteristics of computer programs that we could validate through experimentation. Inspired by Knuth, our early careers were an exciting mosaic of mathematics, programming, and applications at universities and research labs, as the computational infrastructure that we enjoy today took shape, with efficient algorithms whose performance we understood playing a significant role. As Knuth said in his Foreword to our 1996 book An Introduction to the Analysis of Algorithms:

“People who analyze algorithms have double happiness. First of all they experience the sheer beauty of elegant mathematical patterns that surround elegant computational procedures. Then they receive a practical payoff when their theories make it possible to get other jobs done more quickly and more economically.”

Despite this appeal, research in the analysis of algorithms in the theoretical computer science community drifted in the 1980s from the basis established by Knuth to a theoretical journey where algorithms are classified by asymptotic growth of their worst case performance. This approach unleashed an “Age of Design” that has attracted the attention of a generation of theoretical computer scientists, but has dubious relevance to the practice of computing, because the preponderance of the analyses in this literature give no way to predict performance or to compare algorithms on the basis of performance in the real world. My Algorithm Science essay here gives more details on this story.

Underlying philosophy. Philippe was a brilliant mathematician, but he was also a computer scientist extraordinaire. While he was fascinated by the tendency of mathematics to take us into an abstract world that leads to wondrous discoveries, he was also, like many classical mathematicians, quite well-grounded in reality, always using his mathematics to formulate hypotheses that could be validated in the real world. Of course, the easiest way to do so nowadays is to write a program. Far too few people both prove theorems and write programs these days; Philippe found the opportunity irresistible. If there is one personal trait that I would be happy to see emulated by readers of this note, it is this one. Every one of his mathematical results would lead to the questions: “What might this imply about the real world?”and “What program could I write to validate and learn more about this phenomenon?”.

Analytic combinatorics. Which brings us to Philippe’s central accomplishment: the field of analytic combinatorics. Philippe had the basic outline of the research program he would follow quite early on, as is evident in courses he taught in the 1980s. Because of the research challenges and opportunities that intervened, it took nearly 30 years for Philippe (and his many coauthors) to systematize related research, develop the theory needed to fill in the significant gaps, and implement automated tools to apply and validate the theory.

The key idea driving all the work was this: By taking us automatically from a precise specification of a discrete structure to asymptotic results that quantify properties, analytic combinatorics holds the promise of supporting the scientific approach espoused by Turing and Knuth, but in a way that uses classical mathematics to uncover essential truths, avoid excessive detail, and support automating the whole process.

While he was an eternal optimist, I believe that Philippe was stunned by the extent to which his research program was able to realize this dream.

Two books. In the meantime, we were devoted to our original idea of writing a book that could be used to teach future generations. In the 1980s and 1990s Phillipe visited Brown and Princeton and I visited Rocquencourt many times—-“the book” was a central topic. Our original conceit was to develop a monograph like the Whittaker and Watson classic An Introduction to Modern Analysis. For many years we used a format that mimicked that book (some vestiges remain, like the use of Roman numerals to number chapters). After about a decade, it became very clear that what we had to say would not fit in a single book.
     The first book was mostly done, and it was easy to make the decision that I would be the lead author on that one and Philippe the lead author on the second. That put me into high gear, eager to finish that first book. It took much longer than I expected because Philippe would return detailed feedback in marked-up manuscripts. It sometimes seemed that there was a comment on every word, but each comment was insightful and needed to be addressed.
     What should the title of the second book be? Inspired by the title of Apostol’s book Analytic Number Theory, the perfect title came to us: Analytic Combinatorics. That decision put Philippe into high gear. Among other things, I wanted to add more visual images to the book, but Philippe was moving too fast. It was all I could do to keep up and try to provide the kind of detailed feedback on draft manuscripts that he provided for me, but I managed to do so, and the collaboration was productive and fulfilling.
     After Philippe died, I did a second edition of the first book, to incorporate analytic combinatorics, thus introducing it to a wider audience. After that, I developed online lectures and MOOCs on our work, which have reached tens of thousands of people. I finally did get to incorporate a substantial amount of visual material. I was at the height of my skill and am very proud of those lecture slides and the role of visual images in telling the story.

Aftermath. Analytic Combinatorics has been extremely well received. It marked the emergence of a new subfield of mathematics that offers a wealth of opportunities for research in the future. Beyond applications in the analysis of algorithms, probability, and combinatorics, it provides insight into discrete structures that are studied in all fields of science, and it presents a foundation that researchers of the future can extend in many directions. Already, several other books (and hundreds of research papers) have been published that build upon our work. Many of these authors have told that me that they hope their work lives up to Philippe’s high standards (as do I). In most cases, it does, and I know that Philippe would be delighted.

Not long ago, my wife encouraged me to read a biography of Honore de Balzac by Stephan Zweig. While I do not mean to suggest a direct comparison between two unique and disparate personalities, I was struck by the opening words of this book, which I think provide a perfect description of Philippe Flajolet:

“A man of … genius, endowed with an exuberance of imagination which puts it in his power to establish and populate a universe of his own creation.”

To have a conversation with Philippe was to learn something; to work with him on numerous occasions across decades was an adventure; to lose him so early was a terrible tragedy; and to work to solidify his legacy is a special privilege.