It doesn't really leave us anywhere, I think. By the way -- I cannot prove, as of yet, that there is no solution as specified (O(n) time, O(1)) asymptotically, I am just saying that: 1. yours is not appropriate, and 2. that the known algorithmic bounds on similar problems do not make me optimistic.
I do not think that the character of the problem was to induce some solution by enforcing an artificial size constraint on it like it has to be coded on a 32 bit machine. The only comment I have left, really, is that -- theoretical exercises, speaking in terms of our solutions working while the inputs grow without bound is not without application. It is an invaluable way to characterize the performance of our Algorithms... not all applications of theory have to do with implementation -- you seem to think they do. More often than not, the best application of theory furthers the theory itself. This is how theory has developed and it helps us establish bounds on problems (like the low bound of sorting in the comparision model, or the element-uniqueness problem mentioned earlier). Dijkstra's words are not just a "fancy phrase" -- he is trying to warn us against thinking only about the current technologies and machines we work on. If we stopped developing abstract theory and worked only in the context of n-bit computing -- our knowledge of the field would slow down to a stop... And what of future developments, like Quantum computing? That said -- I have nothing more to say... Thanks for the discussion. On Aug 25, 2:53 pm, L7 <[EMAIL PROTECTED]> wrote: > On Aug 25, 2:00 pm, wbspresslyjr <[EMAIL PROTECTED]> wrote: > > > You are mixing up implementation with theory here. The study of > > I would argue that neither of us are mixing up anything. I agree, that > in the infinite sense, an O(n) solution is absurd. However, the reason > I pointed to the trail of messages is that I clarified on what my > solution is based. > > > Algorithms is a rigorous and abstract field. Note the use of the word > > abstract... This means that we are not talking about computers (32bit, > > 64bit)... we are talking about the nature of mathematics and problem > > solving... > > I agree. However, knowledge is useless unless it can be applied to > something. > > > ever, on any machine theoretical or otherwise... Does your solution > > have this character? No. The size of your hash table changes. It is > > not constant. > > It is constant for a given problem. I've already explained the context > of my answer more than is necessary. > > > > > Perhaps you should heed the words of Dijkstra: "Computer science is no > > more about computers than astronomy is about telescopes." > > Look, fancy phrases and quotes are great; they tend toward > inspiration. However, like I mentioned earlier, there is no use for > knowledge without application. > > This is a redundant argument. Yes, you can prove that there is no > answer in the infinite scope. Yes, I can prove that there is in the > finite scope. Is either one of us right? It depends on the setting. I > can implement a solution the problem as it would exist in a real-world > scenario, you can prove that I cant do that. > Where does that leave us? --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
