Faces of the Foundation: Bob Sedgewick

Bob Sedgewick has built his career around understanding how things work at scale. During his Hertz Fellowship under the luminary algorithms analyst Donald Knuth, Sedgewick completed landmark studies of quicksort, the algorithm of choice for sorting many different types of lists, showing how various decisions in implementing the algorithm affect the time and space used as the number of elements to be sorted increase in size. But scale isn’t just a computational phenomenon. When Sedgewick became the founding chair of Princeton’s computer science department, he knew he would have to find an efficient way to scale teaching of computer science, a topic soon to be in high demand at Princeton and elsewhere.

Now, Sedgewick’s courses reach over two-thirds of Princeton undergraduates, and hundreds of thousands of students around the world. Through textbooks written for a broad audience, the use of massively open online courses (or “MOOCs”), and a series of online resources that make it easy for anyone with a computer science degree to teach the basics of CS, Sedgewick hopes to close the gap between the number of students who want to learn CS and the number of teachers who are able to reach them. He may just revolutionize the lecture model in the process.

Sedgewick didn’t set out to change how computer science was taught. He entered graduate school at Stanford unsure of how he’d pay for it, on the promise only of a one-year teaching fellowship.

That first year, two things changed his course for the better. First, he took a class on Analysis of Algorithms with Knuth, author of a still-in-progress expansive set of volumes titled The Art of Computer Programming. Sedgewick enjoyed and excelled in Knuth’s class, and resolved to work under him for his PhD. But Knuth wasn’t accepting students.

The second thing that changed was this: Sedgewick was awarded a Hertz Fellowship in the spring of his first year. “The Hertz Fellowship made all the difference,” Sedgewick recalls. With the funding and flexibility afforded by the fellowship, Sedgewick was able to devote all his energies to studying Knuth’s work, and Knuth was more than happy to take on the star student, so that Sedgewick began analyzing algorithms under the man who defined the field.

It was during this collaboration that Sedgewick turned his attention to quicksort, a sorting algorithm that had been known for decades, but with numerous variants and design decisions that needed further study. “I found a way to improve quicksort that made [Knuth] tear out eight pages of the book,” Sedgewick recalls. His thesis laid out mathematical models for known variants of quicksort under a broad variety of situations, backed up by scientific studies validating the models, and set a standard in the analysis of algorithms. It is still referenced by modern researchers who are adapting quicksort to modern architectures.

Sedgewick continued studying the performance of various and sundry algorithms and data structures after his PhD, securing a faculty position at Brown University and inventing (with Leo Guibas) a data structure called red-black trees used for efficient information retrieval at Xerox’s Palo Alto Research Center (PARC). Your cellphone and billions of other devices use red-black trees.

In 1985, an opportunity at another Ivy League came knocking. Princeton University was establishing a computer science department, and asked Sedgewick to become the founding chair of the department. Sedgewick relished the challenge of hiring the right faculty to advance the department’s teaching and research and found that he had the resources to succeed. “Princeton doesn’t like to fail,” he says.

Where his resources were more limited was in the design of a course to introduce computer science to as many Princeton students as possible. “At the time, there was no interest or ability to get involved in computer science” outside of a select group of mathematicians and applied scientists, he recalls, but it was becoming clear to Sedgewick that computational problem solving would be a useful skill for everyone.

To meet the demand he knew would grow, Sedgewick set about designing a course to introduce students to computer science (COS 126) and to the analysis of algorithms (COS 226), full of projects and online resources which would allow as many students as possible to take and succeed in the course.

By introducing students early on to the limits of computation – that there are some problems you can’t solve, and some that take too long unless you think deeply about the performance of your algorithms – Sedgewick said he aims to instill computational thinking into as many students as possible.

“After being through a full-year curriculum at a college level, like ours, there’s an awful lot they can do with it afterwards,” says Sedgewick. “Students see computational challenge as something that’s to be relished, not avoided.”

By making the course materials and problems available online, Sedgewick says he hopes to help other, often larger schools, which may not have the resources to teach a solid introduction to computer science to such a high proportion of their students. His textbooks have sold over a million copies, and 200 thousand people take his online algorithms course every year.

Sedgewick continues his research as well in analyzing algorithms, pioneering with Phillipe Flajolet the field of “Analytic combinatorics,” an approach for modeling algorithms and data structures as particular mathematical objects whose performance and behavior can then be analyzed and optimized. The technique applies in statistical physics, genomics, and other scientific disciplines, as well. “If you can specify it, you can analyze it” is the Flajolet-Sedgewick mantra. Sedgewick’s MOOC based on the topic, Analytic Combinatorics, draws 9000 students each year.

This broad reach, and those of his other courses, makes deep introductions to computer science accessible to a large and growing number of students, both in and outside of traditional universities. “Our model does scale – that’s the one thing we’ve proven,” says Sedgewick.