4 ms·

Coincidentally, I was thinking of what Knuth said just last week, when one of my comments was downvoted into obscurity for promoting a supposedly obscure/contri

by dxbydt 15y ago

Coincidentally, I was thinking of what Knuth said just last week, when one of my comments was downvoted into obscurity for promoting a supposedly obscure/contrived math formula over a lame switch-case :) http://news.ycombinator.com/item?id=2817716 http://news.ycombinator.com/item?id=2817716 In reality, that formula is neither obscure nor contrived. I actually learnt it in high school ie. it was formally taught and we worked through how to come up with such functions given a set of inputs and outputs ie. essentially a bounded set mapping problem { 1->31, 3->31, 4->30,5->31, 6->30,7->31....} 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 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.

kenjackson 15y ago
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.
- dxbydt 15y ago
  "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() { 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.
  - alttag 15y ago
    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.)
shasta 15y ago
Knuckles = "o-o-o-oo-o-o-o" ...
zvrba 15y ago
"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.

by dxbydt 15y ago

kenjackson 15y ago

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.

dxbydt 15y ago
"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() { 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.
- alttag 15y ago
  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.)

shasta 15y ago

Knuckles = "o-o-o-oo-o-o-o" ...

zvrba 15y ago

"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.