Donald Knuth on Algorithms, TeX, and Open Problems

TL;DR

Donald Knuth, honored as one of Stanford Engineering's eight inaugural Heroes, ran an open Q&A rather than a formal award ceremony, continuing a tradition he learned from Richard Feynman at Caltech of answering any student question on the last day of class. He is recognized as the father of algorithm analysis, author of The Art of Computer Programming, and creator of TeX.

Transcript

this presentation is delivered by the Stanford center for professional development you good evening I'm Jim plumber the dean of the School of Engineering I'm we're delighted to have all of you here tonight uh in addition to a a packed Auditorium here on campus there are literally hundreds of alums and Friends watching over the internet live uh toni... Read More

Key Insights

• Donald Knuth is one of eight inaugural Stanford Engineering Heroes, joining Fred Terman, William Hewlett, Dave Packard, Charles Litton, William Durand, Ray Dolby, and Vint Cerf, a program that recognizes engineers who changed human social and economic progress.
• The event was structured entirely as a question-and-answer session because that is how Knuth chose to spend his day on campus, asking only that he be allowed to answer questions rather than receive a formal award ceremony.
• Knuth's open Q&A tradition came from Richard Feynman at Caltech: he reserved the last day of each quarter to answer any student question on any subject, so students would not finish a course with their questions unanswered.
• The Art of Computer Programming is Knuth's landmark series, considered by many one of the most important scientific writings of the past century, with volume two covering seminumerical algorithms.
• TeX was created because Knuth grew frustrated with electronic publishing tools while writing his books, so he wrote his own text-setting language, which became the gold standard for mathematical and scientific publications.
• Knuth demonstrated early computational skill in 8th grade by forming 4,500 words from the letters in the phrase 'Ziegler's Giant Bar', winning a national contest when judges expected only a couple thousand words.
• Knuth planned to study music in college at what is now Case Western Reserve University, but switched to mathematics after solving a difficult extra-credit problem while waiting for a bus, graduating with the highest GPA among math majors.
• Reading volume two of The Art of Computer Programming led moderator Dan Boneh into cryptography, illustrating how encountering a specific volume of Knuth's work could shape an entire research career.

Questions & Answers

Q: What is the Stanford Engineering Heroes program?

The Stanford Engineering Heroes program recognizes the achievements of Stanford engineers who have in many ways profoundly changed the course of human social and economic progress through engineering. According to Dean Jim Plummer, the heroes embody what the School of Engineering stands for: innovation, entrepreneurship, leadership, and world-class teaching and research. Donald Knuth was named one of eight inaugural heroes in this class.

Q: Who were the eight inaugural Stanford Engineering Heroes alongside Donald Knuth?

Donald Knuth joined an illustrious inaugural class of Stanford Engineering Heroes that included Fred Terman, William Hewlett, Dave Packard, Charles Litton, William Durand, Ray Dolby, and Vint Cerf. Dean Plummer described this as quite an illustrious group of people affiliated with Stanford engineering, all recognized for profoundly changing human social and economic progress through their engineering work.

Q: Why did Donald Knuth create TeX?

During the time Knuth was beginning to write The Art of Computer Programming, he became very frustrated with the capability of electronic publishing tools of the era. So he took matters into his own hands and wrote his own code, or language, for programming text setting. This tool, TeX, quickly became the gold standard for mathematical and scientific publications, solving the typesetting problems he had encountered.

Q: How did Donald Knuth become a mathematician instead of a musician?

Knuth initially planned to study music in college at what is now Case Western Reserve University, and he is an accomplished musician who plays organ, tuba, saxophone, and other instruments. One day he missed the bus on his way to band practice, and while waiting he unraveled a difficult extra-credit math problem that the professor said would earn an automatic A. Solving it turned him into a math major with the highest GPA in his class.

Q: Why does Donald Knuth answer any question on the last day of class?

Knuth kept a teaching tradition he adopted from Richard Feynman at Caltech before coming to Stanford. On the last day of each quarter, students did not have to attend, but if they came, he would answer any question they had. His reasoning was that students pay tuition and go through a whole quarter, and they should not finish without getting answers to the questions they still want answered.

Q: What is The Art of Computer Programming?

The Art of Computer Programming is Donald Knuth's landmark book series, considered by many people to be one of the most important scientific writings of the past century. Dean Plummer highlighted it as a defining contribution. Volume two covers seminumerical algorithms, dealing with computing on numbers and primes, while volumes one and three cover other topics in the field. Knuth retired from Stanford to write these books full-time.

Q: How did The Art of Computer Programming influence Dan Boneh's career?

Moderator and Stanford professor Dan Boneh described running into volume two of The Art of Computer Programming on a bookshelf while growing up. Volume two covers seminumerical algorithms, and reading it made him fall in love with computing on numbers and primes. As a result, he ended up doing cryptography, which became his main area of research. He noted that encountering volume one or three instead might have led to a completely different life.

Q: What did Donald Knuth do in 8th grade that showed his early skill?

In 8th grade, Knuth won a national contest to form as many words as possible from the letters in the phrase 'Ziegler's Giant Bar'. The judges expected the winner to generate something on the order of a couple thousand words from those letter combinations. Knuth found 4,500 words and won the competition, demonstrating his computational prowess long before his formal academic career, according to the earliest record found by the event organizers.

Summary & Key Takeaways

• Dean Jim Plummer opened the May 2011 event honoring Donald Knuth as one of Stanford engineering's eight inaugural Heroes, with a packed auditorium on campus and hundreds of alumni watching live online. The Heroes program recognizes Stanford engineers who profoundly changed human social and economic progress through innovation, entrepreneurship, leadership, teaching, and research.

• Plummer recounted Knuth's path: winning a national word contest in 8th grade, planning to study music at Case Western Reserve, switching to math after solving a bus-stop problem, earning a 1963 Caltech PhD in mathematics, joining Stanford's faculty, and later retiring to write his books full-time while still biking around campus.

• Knuth said he was uncomfortable being called a hero and preferred representing a heroic department. Professor Dan Boneh moderated, using Google Moderator so web viewers could submit and vote on questions, and opened by asking what beautiful open problem Knuth would use to excite a smart young person about algorithms.