Faces of the Foundation: Bob Sedgewick
listed in Fellows
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.
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
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.
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
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.
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.
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.
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
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
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
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.
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.”
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.