First things first: the story about Gauss and the schoolteacher was in my high school math textbook, so I'm inclined to believe it. On a nifty note, while he recieved it at age 10, I recieved it on a Math entrance exam in grade 8 at age 13 - and came up with the same algorithm. Of course, I also confirmed it with my calculator afterwards (I thought I was smart, but I also didn't trust myself). A couple of years later I read the story of him coming up with it (and getting whacked because the teacher didn't believe he'd summed them), and I've been unneccesarily proud since.
On a more on-topic note, there's a sig I see quite often that says "algorithm, algorithm, algorithm." I fully agree; this is not a "how do you approach it" question, but a "how well do you approach it" question. Analysing the problem and finding the best solution is part of writing good code, whether you call yourself a coder, a programmer, or a computer scientist.
As for mathematicians with lovely O(N) solutions - a bigger problem is not size of N but size of constants. As an example, primality testing can now be done in polynomial time - a huge breakthrough for mathematicians - but in practice number sieves that give ~99.999% accuracy in constant time are used. There are great (in terms of O())solutions for lots of problems that have constants in over ten digits, but worse solutions with constants under a hundred that are used almost exclusively in practice. (It's been a while since I took an algorithms course, but I remember there were a couple of really good examples, even if I can't remember what they were.)
I think Thompson's "when in doubt, use brute force" quote is fine - when making the first iteration of something. After all, it'll work. If anyone's tried using MS's Indexed Search and had it fail with a false negative, this is familiar - better traditional but correct than convoluted and fancy and purportedly better, especially when building small 'blocks,' since then when the blocks are weaved/welded together to make a complex whole, the interesting behaviour is where it should be - in the weaving/welding code, not in the basic blocks.
As for mathematicians and their ilk being poor programmers - sure, quite often, but at the same time it's normally fixable. Eg, they'll have something written inefficiently, but it'll be something like not freeing memory when they're done with it, or recursing but not tail recursing, or the like. Easily fixable. They rarely make fundamental mistakes - writing code that does it, but does it in a way that no matter what cannot be efficient.
And - known facts? If told, using basic integer math, to find all divisors of a number N, what would you do? Loop through 1 to N, finding the remainder, and whenever it's 0 saving the result? No, you'd save the result at 0 and then divide by that number to get a second divisor, and stop at sqrt(N). It's reasonably obvious. Now, if he was asking for something truly from another field, for instance the surface area to volume ratio of a strange solid, then sure. But we, as programmers, don't get that every day. We do, quite frequently, get "from i to n, do X" - even if X is a simple sum - and we should be able to handle slightly offbeat questions along those lines without any difficulty. | [reply] |
As an example, primality testing can now be done in polynomial time - a huge breakthrough for mathematicians - but in practice number sieves that give ~99.999% accuracy in constant time are used.
This reminds me of a recent post on http://lambda-the-ultimate.org where (twards the end) the author makes a comment on "Physics vs. Mathematics" (the thread it's attached to is a rather interesting debate on modern type systems). Math majors would rather have their toenails chewed off by chipmunks than use a theorum that wasn't completely true for every little edge case. But a Physics major (and Engineering majors, too) almost have to in order to get work done.
Orbits of planetary bodies comes to mind. Newton presented some simple equations that almost, but not quite, fit the data (he passed this off as God fiddling with the universe). Einstein gave a much more complex equation that perfectly fit the data. However, Newton's equation is still prefered by Physicists because it's easier to work with, and the minor differences in the outcome usually don't matter.
As programming is more or less an Engineering discipline, we can often get away with things that aren't mathmatically pure. I suspect that good programers know their math, but also know when to throw it away.
"There is no shame in being self-taught, only in not trying to learn in the first place." -- Atrus, Myst: The Book of D'ni.
| [reply] |
Hmmmm...
I like what you say in general, but I have to complain about your treatment of women in your anecdote. I'm not sure if you realize the condescending treatment of "George's girlfriend".
- She is only known by her relationship to George. She could have been referred to as a team member with a name, say Anna. You might as well have called her "the missus", or "the little lady."
- She "knew enough" to code and debug the programs. Like once you have written the algorithm the code practically writes itself. Only if you are a brilliant programmer, perhaps. There are lots of issues after the design stage - what language to implement the algorithm it, getting it to actually work, etc.
- Why did you have to explain her credentials at all? You didn't mention that George was a senior Math major and that is why he was a brilliant algorithmist.
I'm pretty sure you didn't mean any harm, of course, but I thought I should point this out nevertheless. | [reply] |
The comment meant to say that she was a freshman who knew the mechanics of using a computer to enter and manipulate code, but did not have the experience to solve complicated problems and develop new algorithms on the fly. The story as I heard it had a girl in the typist's role, so that is how I retold it. It would have been just as meaningful if I replaced "George's girlfriend" with "George's freshman typist". It most definitely would have been less insulting, and I'll retell it as such, in the future. The reason for describing her credentials was to cast her in the role of the "codeslinger" and to cast 'George' in the role of the "algorithm master", as per the OP.
A similar story happened with me as the main character. My last semester at college also had the ACM contest occurring within it. This year, we only had four students interested in "wasting" a Saturday afternoon on programming tasks. There was me, the resolute (dissolute?) super-senior and three other students, who had less combined semesters in college than I did by myself. (I was on my 9th in 5-and-a-half years, if you're wondering.) So, we divided the teams up as so - I was team A and they were team B. Out of some 54 teams in our division, I came in 9th, solving 5 problems and having a solution for the 6th. I would've solved six and come in 4th had I realized that int on Windows was 2 bytes long, not the four I was used to from Unix. Tracking that down lost me 30 minutes and about 70 points. The other team solved 2 problems and had solutions for 2 more.
The only difference between me and the members of team B was exposure to over a hundred algorithms and techniques they had never seen. That's the same difference that 'George' had over his teammates, including his girlfriend / typist. (She later went on to be a valued member of subsequent ACM contest teams from my school, graduated with a 3.7 GPA in computer science, and was a close friend of mine.)
------
We are the carpenters and bricklayers of the Information Age.
Then there are Damian modules.... *sigh* ... that's not about being less-lazy -- that's about being on some really good drugs -- you know, there is no spoon. - flyingmoose
I shouldn't have to say this, but any code, unless otherwise stated, is untested
| [reply] |
Since the contest some things have changed...
Most importantly George has had a series of transgender procedures and his girlfriend (GF) was the recipient of the removed appendage(s). Because of this gender swap she (GF->BF) now takes the lead in all intellectual contests while George (Georgia) does the grunt work of coding.
| [reply] |