The Art of Computer Programming (interview with Don Knuth)
bcs.org
bcs.org
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.
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.
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.
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.)
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.
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.
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.
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.
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 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.
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.
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.
One of the few people who can state it as a fact, without sounding arrogant.
Probably my favorite part of the interview.