tag:blogger.com,1999:blog-786333285568106173.post169473018907806124..comments2024-01-25T01:05:59.968-05:00Comments on WebDiarios de Motocicleta: Love thy predecessor (II): The comparison modelMihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-786333285568106173.post-62569359378852852172008-07-11T12:22:00.000-04:002008-07-11T12:22:00.000-04:00Mihai, you say "predecessor search is the most exe...Mihai, you say "predecessor search is the most executed problem on the planet" because of IP lookup. I see how trie-based data structures give you IP lookup (longest common prefix) for free, but the longest common prefix need not be a predecessor or successor. What's the simplest reduction from longest common prefix to predecessor search? <BR/><BR/>Thanks for any clarification you can provide.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-80297300693204469442007-09-03T17:39:00.000-04:002007-09-03T17:39:00.000-04:001) I have spent the first 10 years of my computer ...1) I have spent the first 10 years of my computer scientist career doing Olympiads (where you only get points if you code up your idea correctly in a few hours). By virtue of this, I am much more aware of the simple-is-practical paradigm than your average theorist. So trust me, I am not fogetting that.<BR/><BR/>2) Can you name a few non-<I>super-dooper important</I> problems? For any data structure with running time about lg n, and for any algorithm with running time above nlg n, there is no distinction between comparison and non-comparison algorithms. (Let's not talk just yet about the algebraic models with arithmetic operations plus comparisons).<BR/><BR/>3) Yes, my real argument is practical efficiency. If a particular problem is a bottleneck in some application, it is not our job as theorists to tell people: "No, I can't really help you solve it faster, but here, I have a very simple algorithm that I really like".Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-14325494925974604472007-09-02T17:32:00.000-04:002007-09-02T17:32:00.000-04:00actual computers store values with finite precisio...<I>actual computers store values with finite precision</I>...<BR/><BR/>People normally don't write programs in assembly for actual computers but this is almost what it takes to make many of the algorithms you're talking about sufficiently fast. (Is real world speed your real argument?) With the exception of a couple super-dooper important problem (like predecessor search or hashing) Karger is totally right. The fastest algorithm usually works in the comparison model (and usually requires fewer lines of code.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-36880790122274239662007-08-31T12:33:00.000-04:002007-08-31T12:33:00.000-04:00Appologies for the broken "recent comments" sectio...Appologies for the broken "recent comments" section. It is Blogger's problem, and they are slow in fixing it: http://groups.google.com/group/blogger-help-troubleshoot/browse_thread/thread/d9579af18dde9033/191dcdb544a11d8d?q=comment+feed&rnum=2#191dcdb544a11d8dMihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.com