Donald Knuth and Robert Tarjan chat during the virtual HLF
On day two of the Virtual Heidelberg Laureate Forum (HLF) 2020, Robert Endre Tarjan and Donald Ervin Knuth engaged in a freewheeling conversation about mathematics, computer science, and art.
Donald Knuth was the 1974 ACM A.M. Turing Award winner for “for his major contributions to the analysis of algorithms and the design of programming languages, and in particular for his contributions to the ‘art of computer programming’ through his well-known books in a continuous series by this title.” Robert Tarjan won the Nevanlinna Prize in 1982 “for devising near-optimal algorithms for many graph-theoretic and geometric problems for the development and exploitation of data structures supporting efficient algorithms, and for contributing several algorithmic analyses of striking profundity and elegance” and the Turing Award in 1986 (with John E. Hopcroft) “for fundamental achievements in the design and analysis of algorithms and data structures.”
Tarjan was a student of Knuth’s at Stanford, and their history together was on display in their dynamic banter. The conversation produced a number of entertaining anecdotes, such as Knuth’s concern for Tarjan’s health when he was an assistant professor. Knuth said of Tarjan, “as I sort of remember…I was very worried about you because you were proving theorems in your head as you were driving the freeways and I was afraid you would get into a wreck.” Remember kids, don’t do math and drive.
Knuth also discussed his time as the manager of the Case Institute of Technology basketball team while he was an undergraduate. During his junior year he created a process to keep better statistics on each basketball player during practices and games. Then, using punch cards, he fed this data into an IBM 650 to generate strategic recommendations for the coach of the team. This system seems to have been a success — Case won more games the year they began to use Knuth’s system than they did the year before. IBM even recorded a short film about Knuth’s system called The Electronic Coach, which you can watch on Youtube here.
Knuth was ahead of his time — modern NBA teams rely on detailed data analytics to better understand their players and the competition; in fact during the 2013-2014 season the NBA installed SportVu motion tracking cameras in every NBA stadium. These SportVu cameras monitor the movements of every player and the basketball at 25 frames per second, generating data about everything that happens in every basketball game. NBA teams, most famously the Houston Rockets, have used these analytics to redefine how the game is played. While three point shots are the toughest shot to make, they have a higher expected value than a long two point shot (because the difference in shooting percentage between the two is marginal), increase the spacing between players (which makes it harder to play defense), and increases the likelihood of getting an offensive rebound (because missed three point shots tend to bounce further away from the basket). Realizing this, NBA teams consistently shoot more and more threes every season. In the 1979-1980 season, the first year the three point line was introduced to the NBA, the San Diego Clippers led the league with 6.6 three point attempts (3PA) per game. Last year the Houston Rockets smashed that number, attempting the most threes in NBA history with 45.4 attempts per game.
This is all to say that Knuth was really onto something when he had the novel idea of using a computer to better understand a basketball game. (You can learn more about the work of a NBA modern data scientist in this video from Bloomberg that profiles Ivana Seric, a senior researcher with the Philadelphia 76ers.)
Typeset score from Chapter 1 of Fantasia Apocalyptica
Knuth’s application of math and computer science to other fields doesn’t stop there. Knuth is also an accomplished pipe organ player and a few years ago he composed, Fantasia Apocalyptica, a multimedia work for pipe organ. In Apocalyptica Knuth used a few mathematical and algorithmic methods to generate melodies. On his webpage Knuth says:
“At one point I thought I might have time to understand music theory well enough that I could try to teach that theory to a computer. But eventually I concluded that it would be better to create this piece almost entirely by hand, using my desktop machine only to help organize the work. Thus it’s definitely not “computer music”, although I do profess to be a computer scientist.
On the other hand, I did apply some algorithms manually in a few places. For example, a haunting melody, taken from one of the earliest surviving instances of ancient Greek music, occurs ten times. I harmonized it differently each time, using the algorithm of David Kraehenbuehl that’s described in Chapter 22 of Selected Papers on Fun & Games. (See “Randomness in Music”.)
Mathematical methods were also used to generate the changeringing patterns that appear briefly, as well as certain melodies used for the twelve tribes of Israel and for the twelve precious jewels below the “pearly gates” of the New Jerusalem. If those methods hadn’t been successful, I would have changed the results by hand. Fortunately, I didn’t have to do that; the algorithmic approach did give a pleasing result in those cases.”
Knuth’s diverse interests led Tarjan to ask a compelling question: “It’s been said that any field that has science in its name is not a science, so I might ask you is computer science a science, a branch of engineering, a branch of mathematics, an art — but let me ask it in a more personal way….do you see yourself as an artist, a scientist, a mathematician, an engineer, a philosopher, some combination?”
Knuth replied that he realized art stands not only for fine art but also for things that are artificial or made by human beings (as opposed to nature). He defined science as “what we understand well enough to explain to a computer” while “art is everything else.” He went on to say that as we learn more science about something our brains “keep a few jumps ahead, and that’s the art.”
Finally, Knuth was asked if he had advice for students. Knuth’s response was to echo the advice of Leslie Lamport from earlier in HLF, which was to write often. However, Knuth cautioned to not be “too influenced by trendy stuff. Don’t write a paper because you have to write a paper or because you think you have to impress people about something that you aren’t personally really interested in…that’s the worst reason to write a paper.”
Tarjan added to this and said, “You have to figure out what your own path is and follow it. The best students I’ve had came in with or ended up with their own idea that they developed.” Clearly both men have had success finding and following their own path. Watch the full conversation between Tarjan and Knuth on Youtube here.
