puzzle
in [General Programming]
|
Prev: Algorithm book recommendation?
Next: TaskScheduler.dll
From: Peter Ammon on 13 Jun 2005 13:18 spinoza1111(a)yahoo.com wrote: > > They also produce bad feeling in a classroom because of necessity they make only one student look "smart". > irony...too big...crushing....
From: spinoza1111 on 13 Jun 2005 21:58 Peter Ammon wrote: > spinoza1111(a)yahoo.com wrote: > > > > They also produce bad feeling in a classroom because of necessity they make only one student look "smart". > > > > irony...too big...crushing.... Why is this ironic? You think I'm trying to look smart? If so I'd need my head examined, for I have known for a long time that in programming, people have an almost peasant-like suspicion of the complete sentence with wurdz speled gude and conclude from it that they are being taken for a ride, which they are in some global sense, being part of the disposable lower middle class, whence the suspicion. A puzzle generates one answer, along with resentment.
From: Christopher Barber on 13 Jun 2005 23:15 spinoza1111(a)yahoo.com wrote: > > Christopher Barber wrote: > >>spinoza1111(a)yahoo.com wrote: >> >> >>>>>For, I used the phrase "close to" as regards O(n). >>>>> >>>>>O(n*n) == O(n*n/2), of course. But it's also the case for practical >>>>>applications that n*n/2 < n*n. >>>> >>>>Sure, given the choice between an algorithm that costs n*n steps and one that >>>>costs n*n/2 steps of the same size, the latter is a better choice in terms of >>>>cost, but I don't known anyone other than you that would call such an >>>>algorithm "close to" O(n). When there are linear and O(n log n) algorithms >>>>that are also simpler to implement, what is the practical use case for your >>>>algorithm? >>> >>>Read the literature on O(x), for Chrissake. See for example Skiena, The >>>Algorithm Design Manual >>>(http://www.amazon.com/exec/obidos/tg/detail/-/0387948600/qid=1118630635/sr=8-3/ref=pd_csp_3/103-4992382-6347852?v=glance&s=books&n=507846). >>> >>>You don't UNDERSTAND O(x) UNTIL you know when to use O(n^2) in the >>>pragmatic sense where n is small and known to be small for practical >>>applications. >> >>You are right that it can be ok to use a suboptimal algorithm for when you >>know for a fact that the data size will be small, but generally you would only >>do so because the faster algorithm is more complex or more work to implement. >>This is not the case with your algorithm. > > How do you know that for a specific instance? In a specific instance, > the preconditions may indeed be that n is bounded and delete is fast. > In a specific instance, you have to know how to work with (write about: > speak of) algorithms without snap moral judgements based on > ill-understood complexity theory. First, if delete has constant cost then your algorithm is O(n^2). If delete is O(n), then your algorithm is O(n^3), so the cost of delete doesn't really matter. Second, the "trick" solution is simple to implement (provided you are using a non-crappy programming languge) and is O(n), but even without XOR you can code an O(n) solution using hash tables or a large bit array. Third, assuming you have a system-supplied sort function, the sort and search solution is O(n log n) and still easier to implement. Finally, your algorithm isn't even the simplest O(n^2) algorithm! for (i=0; i<max; ++i) { for (j=0; j<max; ++j) { if (i !=j && a[i] == a[j]) break; } if (j == max) return a[i]; } >>You appear to have "misread" me. I just meant that it was not obvious >>from what you posted *previously* that you understood the O() notation. > > Sorry you got that impression. But in a collegial setting, you'd assume > that discussants understood the material and you wouldn't have to waste > time establishing their bonafides. I would not assume that someone understood if they said something that made it seem otherwise. That was the case here. When you suggested your O(n^2) was "close to" O(n), you used language that I and others have never heard used when speaking of the O() notation, so the assumption of prior knowledge was dropped. >>You seem to take everything personally. It is your algorithm that was being >>criticized, not you. In the professional software world, it is really >>important to be able to recognize when a particular algorithm is bad, drop >>it and go on to another one. If you insist on wrapping everything up into >>your own sense of ego, then it is much harder to reach your technical >>goals. > > This makes the issues "my" problem and norms what in fact is deviant > conduct on the part of workgroups and corporations, I don't think there is anything "deviant" about criticizing a poor algorithm. What is your problem is how you choose to react to such criticism. You can blame the critics all you want, but it is unlikely to bring you much satisfaction. > Furthermore, my point was that the algorithm shouldn't be criticized > because order() is not a moral category. If anything, the programmer is > precisely the one who should be criticised or praised. You are the one bringing morals into this. Choosing an algorithm is not a moral decision, and arguing about the relative merits of different algorithms is not a moral argument. There is nothing morally wrong with your algorithm, it simply is technically inferior to other available algorithms. - Christopher
From: Gerry Quinn on 14 Jun 2005 05:42 In article <1118670149.685715.160970(a)o13g2000cwo.googlegroups.com>, spinoza1111(a)yahoo.com says... > Gerry Quinn wrote: > > Puzzles are fun and educational. Good teaching IMO. The fun element > > means the student understands the problem domain concretely before he > > tries to plug in textbook solutions. (It worked on you, surely - I > > should think/hope you now know more about algorithmic complexity than > > you did before this thread. And you've learned a new XOR trick as > > well!) > > You talking to me? I didn't learn jack from this exchange, and that's > the problem. I already knew about algorithm complexity and had my time > wasted by people who don't know it, because I had to again produce an > explanation of their bizarre and offensive behavior. Nobody who can claim: "As long as DELETE is an atomic and fast operation this algorithm is close to O(n) because the array gets smaller by two entries in the worst case through its major loop, and in the worst case for the inner loop (where the inner loop must search the entire array in both directions) the algorithm is finished by definition." ...can also claim to be well versed in asymptotic algorithm complexity order, since this algorithm is trivially O(n^2). - Gerry Quinn
From: Gerry Quinn on 14 Jun 2005 05:45
In article <1118669918.137639.276740(a)g44g2000cwa.googlegroups.com>, spinoza1111(a)yahoo.com says... > Gerry Quinn wrote: > In the solution where delete is not allowed the average time is n^2/2 > times THE SAME K as the purely O(n^2) solution. The assumption was that > delete would be equivalent to setting a link "past" the deleted item, > and I rejected the idea of a brute force array delete, in which entries > are moved, for obviously this makes the execution much slower. How can you say "the same K" when the code will be different? K is dependent on the precise details of how the code is arranged, how it suits the machine hardware, etc. That's precisely why it is discounted in big-O analysis. - Gerry Quinn |