The Art of Computer Programming (interview with Don Knuth)(bcs.org)
bcs.org
The Art of Computer Programming (interview with Don Knuth)
http://www.bcs.org/content/conWebDoc/40462
25 comments
I just upvoted your old post. :-)
I did disagree with the solution (many who see the code would get confused), but it certainly was a positive contribution to the discussion, which is always my bar for upvote/downvote.
And I love Concrete Mathematics. I wish people would say Knuth is the author of TAOCP and Concrete Mathematics. And Ronald Graham is another great computer scientist. With that said I do distinguish computer science from programming.
I did disagree with the solution (many who see the code would get confused), but it certainly was a positive contribution to the discussion, which is always my bar for upvote/downvote.
And I love Concrete Mathematics. I wish people would say Knuth is the author of TAOCP and Concrete Mathematics. And Ronald Graham is another great computer scientist. With that said I do distinguish computer science from programming.
"I just upvoted your old post. :-)"
Thank you!
"many who see the code would get confused"
I honestly don't think we should dispel confusion by dumbing things down to the point where all discrete math is squeezed out of the CS curriculum and all you have left is lame switch-cases and explicit enumeration so there is zero confusion but also zero insight into the problem. Some of the candidates we interview these days are a symptom of this very problem. Lemme give you 2 examples ( actual interviews questions we asked candidates ).
1. write a function that returns the sum of the first one thousand odd numbers.
Expected Answer:
function foo() {
The candidate's answer :
function foo() {
Now, the candidate is a LAMP expert and can do magic with linux sys-admin tools, but really, this is such an incredibly lame solution. Yes, its "correct" and very clear and nobody will get confused looking at his solution. But what's more clear is that this person has never had a single course in discrete math. Sum of n odd numbers is n^2 is taught on day 1, its so fundamental and basic and even if you forget the actual result, it takes just 5 minutes to derive it from first principles ( just write the sum forwards to backwards, then write it again backwards to forwards, then add the two expressions, hey voila there you go! ). When we show him the expected solution, he is genuinely surprised and says we've pulled a fast one on him. "Its a trick question! ". He says he's never been taught anything like this in the classroom. That's just sad.
2. Find all the integer triples that form right triangles whose smallest side is less than a million.
Candidate's answer :
for i from 1 to 1000000 {
for j from 1 to 1000000 {
for k from 1 to 2000000 {
}
}
Again, this is the "correct" solution and its eminently readable, but it is supremely inefficient and super-lame. Its like the candidate has never given any thought to the actual problem, and is just throwing loops and conditionals at it. I will refrain from giving the expected solution here, but any student of discrete math can generate pythagorean triplets in a much more efficient manner than the lame solution given above.
A little dose of Knuth's Concrete Math goes a very long way.
Thank you!
"many who see the code would get confused"
I honestly don't think we should dispel confusion by dumbing things down to the point where all discrete math is squeezed out of the CS curriculum and all you have left is lame switch-cases and explicit enumeration so there is zero confusion but also zero insight into the problem. Some of the candidates we interview these days are a symptom of this very problem. Lemme give you 2 examples ( actual interviews questions we asked candidates ).
1. write a function that returns the sum of the first one thousand odd numbers.
Expected Answer:
function foo() {
return 1000*1000;
The candidate's answer :
function foo() {
sum = 0;
count = 0;
i=0;
while(true) {
i++;
if (i%2==1) {
count++;
sum += i;
}
if( count == 1000 ) {
return sum;
}
}
Now, the candidate is a LAMP expert and can do magic with linux sys-admin tools, but really, this is such an incredibly lame solution. Yes, its "correct" and very clear and nobody will get confused looking at his solution. But what's more clear is that this person has never had a single course in discrete math. Sum of n odd numbers is n^2 is taught on day 1, its so fundamental and basic and even if you forget the actual result, it takes just 5 minutes to derive it from first principles ( just write the sum forwards to backwards, then write it again backwards to forwards, then add the two expressions, hey voila there you go! ). When we show him the expected solution, he is genuinely surprised and says we've pulled a fast one on him. "Its a trick question! ". He says he's never been taught anything like this in the classroom. That's just sad.
2. Find all the integer triples that form right triangles whose smallest side is less than a million.
Candidate's answer :
for i from 1 to 1000000 {
for j from 1 to 1000000 {
for k from 1 to 2000000 {
if i*i + j*j == k*k then print i,j,k;
}
}
Again, this is the "correct" solution and its eminently readable, but it is supremely inefficient and super-lame. Its like the candidate has never given any thought to the actual problem, and is just throwing loops and conditionals at it. I will refrain from giving the expected solution here, but any student of discrete math can generate pythagorean triplets in a much more efficient manner than the lame solution given above.
A little dose of Knuth's Concrete Math goes a very long way.
It doesn't seem to me that the candidate's response for #2 is "correct" (as you say). The most simple refutation being a 5:12:13 primitive triangle scaled 199,999x (such that the smallest side is less than, but not equal to, a million). Result: 999995:2399988:2599987, which would not be uncovered by the above solution as both j and k exceed the upper bound of the loop.
As a more general critique of your test: which method is the best use of programmer time? The functions you request return static results, thus the performance hit should be one-time and cached. If so, why do you care?
Finally, yes, I agree that we as a general population are not well-prepared enough in math. Still, I think you're putting too much weight on it. (I've had university CS graduates—supposedly—deliver 100+ lines of nested ifs that mathematically resolved to no-op, so I feel your pain. I'm just not sure that you're approaching this in the best way.)
As a more general critique of your test: which method is the best use of programmer time? The functions you request return static results, thus the performance hit should be one-time and cached. If so, why do you care?
Finally, yes, I agree that we as a general population are not well-prepared enough in math. Still, I think you're putting too much weight on it. (I've had university CS graduates—supposedly—deliver 100+ lines of nested ifs that mathematically resolved to no-op, so I feel your pain. I'm just not sure that you're approaching this in the best way.)
"Find all the integer triples that form right triangles whose smallest side is less than a million." Is this the kind of stuff that you work with on a daily basis? If it is, then sure ask away. But if you're just looking for a programmer, why are you asking discrete math questions?
Why focus on stuff that is done on a daily basis? Most places I've worked, the stuff done on a daily basis is relatively simple and could be done by most reasonably competent programmers. The hard stuff that is done once every month or two on the other hand is the stuff that really ends up mattering and the thing I'd want to optimize for if hiring.
ron graham is more of a mathematician than a computer scientist. i had him for a professor. he is very entertaining.
"Readable code" is VERY important when you have to deliver a working product to a customer. Especially when you're working in a team.
To quote Dijkstra: "The competent programmer is fully aware of the limited size of his own skull. He therefore approaches his task with full humility, and avoids clever tricks like the plague."
The longer I work in the industry as a part of a team, the more I appreciate this saying.
To quote Dijkstra: "The competent programmer is fully aware of the limited size of his own skull. He therefore approaches his task with full humility, and avoids clever tricks like the plague."
The longer I work in the industry as a part of a team, the more I appreciate this saying.
Knuckles = "o-o-o-oo-o-o-o"
...
Now, to be put into that category of one of the best books of the century, that’s a little bit embarrassing as they rank me with Einstein and Feynman - I’m not in that league really, I just didn’t have as much competition - they had to have a token person in computer science!
There might be a little truth here but, nonetheless, his devotion to those books made him a legend of our field. And to think people—well, I!—brag so much about so much less. His humility is disconcerting.
There might be a little truth here but, nonetheless, his devotion to those books made him a legend of our field. And to think people—well, I!—brag so much about so much less. His humility is disconcerting.
I think this is simply extreme modesty. Many researchers in the field often think they have discovered something new. Digging a little further, they discover that Knuth has been there already.
Andos, I don't feel his humility (expressed here and elsewhere) is at all disconcerting. I feel it's both endearing and appropriate.
Each of us who have accomplished much less, but have boasted of much more, need only keep Knuth's example in mind as a guide for our future lives.
Each of us who have accomplished much less, but have boasted of much more, need only keep Knuth's example in mind as a guide for our future lives.
One of my favorite parts...
Looking forwards, what do you perceive are the biggest issues / challenges computer science faces, now and in the near future?
The challenge of how can we go to sleep at night when there are so many things left to be done! (....) but I think so much more could be done by having better health care records and better ways of describing and visualising combinations of symptoms and combining statistical methods as well as visual methods, this would help doctors to understand things more clearly and quickly.
Not to mention the ways in which computers can help biologists to design better drugs. Everywhere you look there’s something to be done which needs a good programmer to help achieve it. There’s no shortage of challenges and little chance of ever running out of them.
It gets me a little personal validation that we still have many exiting challenges ahead.
Looking forwards, what do you perceive are the biggest issues / challenges computer science faces, now and in the near future?
The challenge of how can we go to sleep at night when there are so many things left to be done! (....) but I think so much more could be done by having better health care records and better ways of describing and visualising combinations of symptoms and combining statistical methods as well as visual methods, this would help doctors to understand things more clearly and quickly.
Not to mention the ways in which computers can help biologists to design better drugs. Everywhere you look there’s something to be done which needs a good programmer to help achieve it. There’s no shortage of challenges and little chance of ever running out of them.
It gets me a little personal validation that we still have many exiting challenges ahead.
> It gets me a little personal validation that we still have many exiting challenges ahead.
I read that one of the US Patent Office people quit at the turn of the 20th century because he was convinced there was nothing left to do.
If I have learned anything, it's that for every problem humans solve, a few more pop up that we never thought would exist.
It makes me happy.
I read that one of the US Patent Office people quit at the turn of the 20th century because he was convinced there was nothing left to do.
If I have learned anything, it's that for every problem humans solve, a few more pop up that we never thought would exist.
It makes me happy.
It appears that that story about the director of the Patent Office saying there's nothing more to invent is mostly made up, see http://en.wikipedia.org/wiki/Charles_H._Duell or http://www.quotationspage.com/quote/22779.html or the most detailed debunking: http://www.myoutbox.net/posass.htm
Even in a casual interview Knuth feeds you enough nuggets to make you think for some time, e.g. the Jevons Paradox he mentions at the end (http://en.wikipedia.org/wiki/Jevons_paradox). His faculties and rate of work does not seem to be affected by age (he's 73!), he's the Euler of CS (although I hope he lives longer than him).
The CS department at Stanford has a weekly Theory Lunch during the academic year and we're fortunate enough to get Don Knuth to speak at least once every quarter[1]. His talks, although they start off from basically very little quickly become intensely technical and mathematical. It is quite astounding to see a man of his age have the kind of passion he demonstrates. Even more so the ability to translate interesting and quirky insights into deep mathematical and algorithmic statements (which is very apparent to those who go to his talks).
[1] http://theory.stanford.edu/theory_lunch/
[1] http://theory.stanford.edu/theory_lunch/
There is also a very long and interesting interview with him at http://www.webofstories.com/play/17060
There's a much longer interview with Knuth posted originally at http://www.webofstories.com/play/17060. The transcript is probably interesting reading for anyone interested in the man; I imported it into Git and started formatting it into paragraphs at https://github.com/kragen/knuth-interview-2006, although I haven't finished.
I think it would be worthwhile for more people to (a) clone the git repository to reduce the risk that this primary historical source will be lost, and (b) reformat more of the transcript if they feel like it.
I think it would be worthwhile for more people to (a) clone the git repository to reduce the risk that this primary historical source will be lost, and (b) reformat more of the transcript if they feel like it.
I liked his answer for the question - why don’t you do email?
Someone has to not be tweeting all the time, someone has to be thinking about things which need a long attention span and trying to organise material and build up strong foundations instead of rushing off across the frontier. It takes a long time to put out something that has the right style; I have to really think about it and if I’m going to do it right I have to spend a lot of time focussed on it. And I was being treated like an oracle, lots of people from around the world were asking my opinion about whatever, so after 15 years of email I decided that was a life time’s worth.
Someone has to not be tweeting all the time, someone has to be thinking about things which need a long attention span and trying to organise material and build up strong foundations instead of rushing off across the frontier. It takes a long time to put out something that has the right style; I have to really think about it and if I’m going to do it right I have to spend a lot of time focussed on it. And I was being treated like an oracle, lots of people from around the world were asking my opinion about whatever, so after 15 years of email I decided that was a life time’s worth.
Actually, you can still email Knuth, and his secretary will print the email out. See http://www-cs-faculty.stanford.edu/~uno/email.html
I can understand why he wants to be on the bottom of things, but I don't get why encouraging people to use postal mail rather than email is supposed to help. Email is just a medium, and it's a much more sensible way to move information around. The widespread habit of checking email every 5 seconds is by no means compulsory. I wonder why Knuth says that the batch mode communication he wants to do cannot be done properly with email.
I can understand why he wants to be on the bottom of things, but I don't get why encouraging people to use postal mail rather than email is supposed to help. Email is just a medium, and it's a much more sensible way to move information around. The widespread habit of checking email every 5 seconds is by no means compulsory. I wonder why Knuth says that the batch mode communication he wants to do cannot be done properly with email.
I think it's just that he's trying to raise the barrier to entry a little higher. If you know you'll get a response in a few days or weeks on paper, instead of a day or two later in your email client, that makes you look for other, quicker ways to get the answer you're looking for, which reduces the load on Knuth (and his secretary).
The American Scientist list mentioned in the opening: http://www.americanscientist.org/bookshelf/pub/100-or-so-boo...
"I was born to be a computer scientist - I have a way of organising stuff in my head that just seems to make me a good programmer. I think everybody can learn to use computers, but only about one person in every 50 is a geek in the same way as I am. That means we can push the envelope and can resonate with the computer. The way we think helps to make it easier for us to know how to construct a machine."
One of the few people who can state it as a fact, without sounding arrogant.
One of the few people who can state it as a fact, without sounding arrogant.
"I’m jealous of astronomers, for example, because people respect astronomers for doing astronomy because it’s interesting just for its own sake. I studied computer science because it’s interesting to study computer science."
Probably my favorite part of the interview.
Probably my favorite part of the interview.
So anyways, Knuth gave an interview maybe 10 years back where he lamented the lack of dexterity in math in American undergrads. He said even Stanford has to offer "remedial courses in math" for CS undergrads, because there is an "interest vs ability" mismatch. At that time ( during the 1999-2000 tech boom ), a lot of Stanford undergrads were indicating CS as their major. So they clearly had the "interest". But upon testing them, it was clear they didn't have the "ability". Hence this interest vs ability mismatch, and a need for remedial math courses at Stanford. At the time, I was studying CS with a bunch of Russian, European, Indian & American classmates. I found that Russians & Eastern Europeans tend to favor clever 1-line math code. They themselves were trained in physics and math & looked at CS problems as essentially a laborious function-mapping exercise. Whereas the Americans invariably wanted "readable code" and ended up writing verbose switch-cases and if-elif-endif clauses ie. essentially unrolling for-loops. Knuth's Concrete Math ( http://www-cs-faculty.stanford.edu/~uno/gkp.html ) was a sort of bible in my days. You had to know generating functions and recurrences and even stuff like complex powers. Like for instance i^i ( i raised to i ) leads to an infinite set of points with real and imaginary parts, scattered all over the 2D plane. You had to know cosets and Lagrange's theorem and set partitioning using cosets. Nowadays people simply enumerate everything as there is no penalty ( in performance terms ), so CS problems have a "select 1 answer from set of possible answers" flavor, rather than "contrive a function to compute the answer" flavor.