A delightful story about the famous Prof. Knuth

Knuth may well be the smartest man in the world

I took the multi quarter sequence from Professor Donald Knuth in the 1970s. It was a mind blowing experience.

I still see him at Zott's every now and then on a warm day. He remains as friendly, funny, gracious and, dare I say goofy looking (tall and Scandinavian), as ever.

Taking the class was surreal. Many of us were undergrads who were struggling to keep up. This class was hard. Some in the class were PhD Students. A really diverse mix. Knuth was awesome. He would give us undergrads something to chew on. Then he would say he was going off on a deep tangent for the PhDs in the audience and for the rest of us not to worry. Rather than scary, we all found that inspiring.

Some funny stories (forgive me if the details are hazy - it was almost 40 years ago):

Occasionally Knuth would bring in a PhD thesis from another university. He would tell us there was a math error in it. Extra credit if you could find the error. We left those for the PhDs in our cohort.

If you know Knuth's books, then you know that he's got some really hard problems at the end of the sections. It was not unusual for him to turn to the undergrads and say, "If you find this area interesting and you'd like to solve this problem, come see me - there might be a PhD thesis in there somewhere." His door was always open. I don't think he was kidding about the thesis thing.

One of my proudest memories of Stanford University was when I won one of Knuth's weekly contests. Often the homework/contest was a program to be written in MIX.

One week the assigment was to read in an input deck that described a Crossword Puzzle and then to print out the puzzle. The challenge was to do it in the fewest instructions possible. I stayed up all night working on it.

I vividly remember that day. He would announce the winners at the end of class.

"This week was rather unusual", he started out. "Third place goes to John Smith whose program was fifty instructions. Second place goes to Jane Doe with forty five." John and Jane were PhD candidates - the winners invariably were.

I was excited! I knew mine was shorter than that. Had an undergrad finally 'scored one for the team'?

Knuth continued. "I am reluctant to award first place." He looked up and smiled. He sighed. "The winning program was half the length of the nearest runner up."

So what's the problem?

"When I first ran the program it seemed to be stuck in an infinite loop. The mainframe aborted the job after the default 1 second of CPU time. So I ran it again but gave it 3 seconds. It failed to complete. I looked at the code. I couldn't make heads or tails of it. But this student has always turned in his work on time. So I took a chance on him and set the CPU time to 30 seconds."

Oh God! I'd run it with a small input deck because CPU time was ridiculously expensive and we all had miniscule budgets to use. Had that test deck failed to unearth an infinite loop bug?

No. Wait. Knuth had said first place. What's up?

He sighed again. "It took over 20 seconds of CPU time, Mr. Lanza, more than $100 worth. Please don't do that again. But it did work and it was the shortest program so Mr. Lanza wins this week. But never again, ok?"

I was mortified. It was as if he was telling me I had cheated. Everyone certainly was looking at me that way. I slumped deep into my seat.

We met up after class. I was terrified. Hell, petrified. Here was one of the smartest men in the world and a guy I really looked up to.

But Knuth's a nice guy. He laughed. "You took this assignment a little too literally. That program should've executed in linear time. Yours was exponential. Did you know that?"

"To be honest, Professor, you said the fewest instructions. I didn't stop to think about run time."

"Fair enough I suppose. But never again, ok? I couldn't make heads or tails out of your code. How did your algorithm work?"

"Well, Professor, I took McCarthy's Lisp class last quarter. To be honest, I had a heck of a time with recursion. At about 2am, though, it struck me to treat this crossword problem like a homework assignment I'd had from McCarthy. It just starts by the first square of the crossword puzzle asking its neighbor squares if they know what to do. Then each neighbor square does the same thing recursively. Eventually the boundary squares figure out that they're on the edge and they report that back."

His eyes opened wide. He laughed and laughed. "But that meant you had to read in the entire deck that described the crossword puzzle for each and every one of those recursions looking for the boundary conditions. No wonder it took so long."

"Well, Professor, it seemed to me that the best way to get to the fewest instructions was just to have all of the boxes in the crossword puzzle talk to each other and let them sort it out. That's what the Lisp problem we had to solve was all about."

He looked at me in a fatherly way. "I'll mention this to John [McCarthy] the next time I see him. I'm sure he'll get a laugh. By the way, what grade did you get in his Lisp class?"

"A C-. I never did get recursion."

Knuth smiled at me and said, "Oh, I wouldn't say that." He walked away chuckling to himself.

http://www.quora.com/Stanford-University/What-is-it-like-to-be-in-a-class-taught-by-Donald-Knuth