Q&A

Dean Thomas L. Magnanti The Progress of Engineering Education

Associate Professor Erik Demaine Algorithms and the Adventure of Teaching

Forrest Liau '06 Nanotechnology and Entrepreneurship

Clarence Lee '06 Technology Fair Co-Founder

Janice Voss EE '77 Opportunities in Space

Mitch Tyson '75 From Politics to Entrepreneurship

Erik Demaine Photo: Donna Coveney/MIT

MacArthur Fellow Investigates Algorithms, Captivates Students
Erik Demaine

Erik Demaine is an associate professor in the Department of Electrical Engineering and Computer Science (EECS). He is a member of the Algorithms and Theoretical Computer Science groups in the MIT Computer Science and Artificial Intelligence Laboratory (CSAIL). Demaine received his bachelor's degree in computer science from Dalhousie University in 1995, and his PhD in computer science from University of Waterloo in 2001, and joined the MIT faculty that same year, when he was only 20. His research interests range throughout algorithms, from data structures for improving web searches to understanding how proteins fold. He has published more than 150 papers with over 150 collaborators. In 2003, Professor Demaine received a MacArthur Fellowship as a "computational geometer tackling and solving difficult problems related to folding and bending—moving readily between the theoretical and the playful, with a keen eye to revealing the former in the latter."

At right: Erik Demaine solved the decades-old "carpenter's rule problem" for his doctoral thesis, proving that it is always possible to fold a set of rigid bars connected by hinges lying flat on a table from one configuration into any other configuration without any of the bars crossing one another.

What are some of the most exciting applications for algorithms today?

Two applications of particular interest to me are the Internet and protein folding.

The Internet (and networking in general) is the source for many great algorithmic problems on graphs and on data. Google is the best-known example of a data structure: storing the entire web in such a way that you can perform keyword searches extremely quickly. An example of a graph problem is this: given estimates of cell phone traffic, where would it be best to put cell towers?

Protein folding is a major challenge in biochemistry. Proteins are the fundamental building block of life, and if we could understand how DNA encodes their intricate folded geometries, we might be able to cure diseases caused by protein misfolding or be able to design custom drugs to combat viruses. We have been exploring how geometric folding algorithms can help model and elucidate the protein folding process.

How does art influence you and your work?

Algorithms are all about creativity, just like art. So there is some intrinsic interplay, and this aspect is what attracts me to both art and algorithms. I have also enjoyed mixing the two, exploring how algorithms can be used to create art, such as paper sculpture and sand drawings. This work is joint with several researchers including my dad, Martin Demaine, who is an artist-in-residence in EECS at MIT. He has been my inspiration in many ways, in particular on the artistic side.

What makes you an award-winning teacher?

My dad taught me that learning is fun, and I try to communicate that. Learning a new subject is an adventure, and I love leading students through that adventure, exploring the main track as well as any interesting side lines that we bump into by accident. My favorite lecture was when a student asked a question in the middle of class about a shortest-paths algorithm, which I had been wondering too, but for which I did not know the answer, and the class and I spent the rest of the lecture figuring out the answer. This was a great example of improvisation. I actually studied improv theater/comedy at ImprovBoston in Inman Square for two years, together with my dad.