tag:blogger.com,1999:blog-8890204.post2847175130030211333..comments2024-03-10T05:26:42.148-04:00Comments on My Biased Coin: BugsMichael Mitzenmacherhttp://www.blogger.com/profile/06738274256402616703noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-8890204.post-57643977050087525422008-11-04T17:41:00.000-05:002008-11-04T17:41:00.000-05:00I think the last anonymous commenter brought up an...I think the last anonymous commenter brought up an important point: culture shock. There are (at least) two cultures when it comes to theoretical algorithms research. One comes from the pure mathematical side, where the algorithm is really just exemplifying that some mathematical structure has some particularly nice properties (that happen to be algorithmically exploitable). The other culture comes from the practical side. I think fundamentally the issue you're coming up against is the clash between these two cultures.<BR/><BR/>It's easy to conflate these two cultures by thinking that there is a single culture of algorithms. But that would be missing the main issue, I think.<BR/><BR/>By way of anecdotes: I am a theorist. But it was only by implementing an algorithm in someone else's paper that I realized that I could do it better, which rapidly led to my first publication.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-81120874505138613692008-11-03T22:01:00.000-05:002008-11-03T22:01:00.000-05:00We had a somewhat similar experience. Proof checki...We had a somewhat similar experience. Proof checking is a human endeavor and as such equally open to error. In a particular paper we could present a lengthy, straightforward and unenlightening calculation which would give the reader no confidence of the result (due to its length), or we could leave this as an exercise and present orthogonal experimental evidence which for this specific problem was quite decisive. <BR/><BR/>We argued that providing the experimental evidence was the best way to go, considering that the calculation was likely to be nixed for space reasons anyway.<BR/><BR/>The referees would have none of it. Too much of a cultural shock I guess.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-34765239433252409802008-11-03T16:53:00.000-05:002008-11-03T16:53:00.000-05:00All commenters:Good comments.I agree, sometimes im...All commenters:<BR/><BR/>Good comments.<BR/><BR/>I agree, sometimes implementations are hard, and one must take care to match to the level of the student. The question of whether one needs to verify a student implementation is correct depends on what it's used for -- here, I'm using it for experiments/bug-finding, so it's less of a concern. But really, correctness is a concern for any program, no matter who implements it! (I don't think these arguments excuse not implementing it.)<BR/><BR/>BTW, I think an argument to have students implement is not that theoreticians can't code (although I'm sure some can't), but that it's not the best use of a theory professor's time. A student might take 40 hours to code up something I could code in 2. But they aren't going to prove the theorem I proved in those two hours in any amount of time... in many cases, the best use of my time is to have a student code. (If it will take me more time to explain it to them than to code it up, then I'll do it myself. :) )Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-59350738328058201322008-11-03T14:33:00.000-05:002008-11-03T14:33:00.000-05:00I agree wholeheartedly with the value of implement...I agree wholeheartedly with the value of implementation. But just to play devil's advocate, how do you know the implementation was error-free? Or that you run on a sufficiently large input size so that the timings accurately reflect the algorithm rather than the overhead?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-4522264771581188052008-11-03T13:23:00.000-05:002008-11-03T13:23:00.000-05:00It may not be epistemologically sound to claim to ...It may not be epistemologically sound to claim to be checking a proof by implementing, but there are many good reasons to do so.<BR/><BR/>1) In reality, proofs of correctness can have errors, and implementing an algorithm often finds them quickly.<BR/><BR/>2) Algorithm analysis uses abstract models of resource consumption. Often an implementation will show that, for example, cache behaviour makes the running time behave quite differently from the model. Or the average case behaviour may be quite different from the proved upper bounds.<BR/><BR/>3) If we really want to have more connection between theory and practice (and I don't know anyone who doesn't), we need to have more confidence that theoretical results have some use. Many published algorithms are very complex, and more practical souls can dismiss them for that reason. But surely it is unreasonable to assume that only really easy-looking algorithms are of practical value!<BR/><BR/>If it's good enough for Don Knuth to implement his own algorithms, why can't we do it? Leaving it to a student might be OK but can lead to problems, and as Daniel says the details can be really hard. A proper implementation of a serious algorithm for an important problem should count as a publication. Maybe then more people would implement their own algorithms. Or can some algorithm theorists not program?Mark Wilsonhttps://www.blogger.com/profile/16382201587698895101noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-61509222672089084242008-11-03T13:01:00.000-05:002008-11-03T13:01:00.000-05:00The way you write things down, one would believe t...The way you write things down, one would believe that "designing the algorithm is the hard part" and "implementing it is the easy part".<BR/><BR/>When it is the case, then often, the implementation is really easy. If it requires 20 lines in a high level language to implement the algo., why wouldn't the prof. implement it? Ok, getting a student to earn some experience is a good thing, I guess. We have to find ways to keep them busy... but why not implement it yourself, and then also ask a student to do it, just to confirm your results?<BR/><BR/><BR/>Of course, quite often, implementation is a lot harder than design. In fact, I can point to several algorithms or systems that I am sure nobody ever implemented... and nobody will ever implement them for good reasons!!! Sometimes, one person implemented something very messy that closely match what appears in the paper... but could not be scrutinized by others...<BR/><BR/>Anyhow, in such cases, asking a student to do it is dangerous: (1) the student could waste a lot of time and get no result, partly through inexperience (2) even if the student claims to have implemented the algorithm, how can you be sure he did?Anonymousnoreply@blogger.com