puzzle
in [General Programming]
|
Prev: Algorithm book recommendation?
Next: TaskScheduler.dll
From: Christopher Barber on 11 Jun 2005 14:18 spinoza1111(a)yahoo.com wrote: > > Arthur J. O'Dwyer wrote: > >>On Fri, 10 Jun 2005 spinoza1111(a)yahoo.com wrote: >> >>>Darius wrote: >>> >>>>ok here is a puzzle. >>>>there is an integer array whose length is odd, and all the numbers in >>>>the array appear exactly two times except one. Find the number in O(n) >>>>time. Try to do it without using any other data structure. >>> >>[...] >> >>>Do while arraySize >= 2 >>> i = floor(arraySize/2) >>> j = i-1, k = i+1 >>> Do while j >= 0 or k < arraySize >>> if j>=0 and a[i]=a[j] { L = j, exit do } >>> if k<arraySize and a[i]=a[k] { L = k, exit do } >>> decrement j, increment k >>> End do >>> If j < 0 and k > arraySize return i >>> delete(i), delete(L) // Changes arraySize >>>End Do >>> >>>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. >> >> I think the above paragraph could be cleaned up to yield one of >>those clever "...and thus I am the Pope" arguments, but as it stands, >>it's too obviously confused to be convincing. Nilges' algorithm is >>O(n^2): we're doing O(n) linear searches of a linearly shrinking array. >>And yes, that's assuming DELETE is O(1), which it normally isn't. > > > The hell with the Pope, and King Billy too. I said "close to" because I > knew that it wasn't O(n) but practical and efficient for reasonable n. > > You're doing O(n) searches, times a linearly shrinking array, only in > the worst case. N/2 the time on average it finds U. This doesn't > transform order n^2 because it divides by a constant and not N but it > is none the less a significant reduction. No, you are wrong. This is O(n^2) at best. Furthermore, you can get O(n log n) simply by sorting the array and scanning the array for the unique element, so why bother with the DELETE nonsense?
From: Christopher Barber on 15 Jun 2005 11:18 spinoza1111(a)yahoo.com wrote: > Christopher Barber wrote: >>Why bother with optimizing a bad algorithm? The only time you would use >>such an algorithm is when n is very small so there is no need to perform >>any other optimizing tricks. When n is large you had better be using >>an O(n) algorithm. > > This is what optimizing compilers do, mate. Uh, no they don't. No optimizing compiler I know of would optimize your bad algorithm, but if you know of one, please speak up. > And in software maintenance > you need to know how to make low-risk code improvements to "bad", > Commie, terrorist, child molestor algorithms. Sure, and you also know when not to. > There are no "bad" algorithms just as there are no bad dogs. There are bad algorithms (though not in the moral sense) and there are bad dogs too (and I am a dog owner). >>>I agree that an O(log n) algorithm is in some nonmoral sense better >>>than O(n), which is better than O(n^y)! But in real programming there's >>>much more to know. >> >>Like what? >> >>Your algorithm doesn't appear to have any practical use and you have yet >>to suggest one. > What IS of practical use to me is the ability to discourse wittingly > and in an amusing fashion about the actual properties of real software. Then what's the problem? Haven't we been doing that? >>>The problem is that you seem more concerned with biography than >>>anything else. OK, the terminology is unfamiliar. >> >>It is not the terminology that is unfamiliar, it is your non-standard use of >>it. I have never heard anyone speak of an O(n^2) algorithm as being "close >>to" an O(n) one in performance. I have no idea what you mean by "biography". > > Then you are unread, for when n<10e1 the O(n) and O(n^2) algorithms are > "close" in significant cases. > > By "biography" I mean wasting time in code reviews and here with an > attack on the speaker's or poster's professional biography. I have made no mention of your professional biography in this thread and know nothing about you other than what you have posted about yourself. Perhaps you are referring to someone else. > Basically, human dignity and economic good sense should require that > no-one on a job of work should be either permitted or required to > establish his right to be a part of a dialog. The "biographical" > approach wastes time in attacks on competence and knowledge. No one said that you should be excluded from the dialogue. Those that feel that way have probably already put you in their kill file. But being admitted to the dialogue does not mean that you can say anything you want without fear of being contradicted. >>>But one reason for the 80% failure rate of enterprise >>>systems is the unwillingness to speak of code without snap judgements >>>and one-upmanship in a field that has been RUINED by laissez faire >>>"competition". >> >>I don't think anyone here made a "snap judgement". I also don't see >>how suggesting improvements to algorithms or program designs is going >>to lead to failures in enterprise systems. > > Not in itself. But failure to review because everybody's pulling their > pud does cause failures. No kidding, but that is what you yourself are doing. >>>And even if it makes no sense to speak of the execution time of a >>>program approaching a limit, becoming "close to O(n)", approaching an >>>infinitesimal but nonzero value for larger N, note that there's a whole >>>field of code improvement within compiler optimization in which the >>>improvements are beneath the radar screen of complexity theory. >> >>There is no such thing as an infintesimal integer value. It is also not > > No, but there are small integer values. Then why did you use the word "infinitesimal"? >>interesting to claim that algorithms tend to converge in performance as the >>sample size goes down because all algorithms are going to perform just about >>the same for n == 0. By this argument, an O(n^n) algorithm is "close to" >>O(n)! > > You're not interested in trivial, degenerate, null cases because as a > non-mathematician, as at best a techie, you view those cases as members > of a bogus moral category. > > A REAL mathematician, such as Nash, remains I think until the end of > his life interested in the fact that when you multiply by 0, you get 0: > that when you multiply n times 1, you get n. Well, I was a math major in college, and even study my old books from time to time but indeed would not call myself a "mathematician". But I think you are mistaken that "real" mathematicians are especially interested in the trivial cases. > My own experience is that a program that fails for either zero or one > input is a bad program insofar as its text fails thereby to be a > recursive proof of the program's correctness. Sure, but we were not talking about correctness but about execution speed. >>I don't really know what you are talking about w/ regard to compiler >>optimization, but based on this discussion I wouldn't want you optimizing our >>compiler. > > Note how you reduce everything to the lower-middle class anxiety of who > has a job. Who said anything about who has a job? I assume that you have one. I just wouldn't want you working on our compiler (our product is a software platform and programming language) based on what you have said in this ng. > And note that given your responses, I am not interested in > working with you. I am not suprised. I am sure that you would much rather work with people who never disagree with you. >>>But I also like to fight with people who deal with their own >>>feelings of incompetence by transferring them onto innocent bystanders. >> >>I don't know who you are taking about, but it isn't me. > > Excuse me, you've been harassing me in this thread since day one. I have been contradicting you. I know that for you that counts as harassment, but I don't think that anyone else thinks so. I know perfectly well that I have no "feelings of incompetence" in this particular domain, and your suggesting that this characterizes me is a rude, personal attack, pure and simple. - Christopher
From: Arthur J. O'Dwyer on 15 Jun 2005 13:46 On Tue, 14 Jun 2005, Peter Ammon wrote: > > spinoza1111(a)yahoo.com wrote: >> 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? > [...] >> A puzzle generates one answer, along with resentment. > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ > What you wrote above is exactly what happened in this thread - > and that's the irony. Oh, I thought the irony was that this puzzle has produced multiple solutions (albeit only one of them O(n)), and, completely /un/necessarily, has made only one participant look stupid --- Nilges himself! (And generated "bad feeling" in only one person's direction.) BTW, at lunch yesterday one of my fellow interns revealed, without knowing anything about this thread, that he had actually been asked the same puzzle in a Microsoft interview! (For Nilges' benefit: The Microsoft interviewer rarely cares about what you'd call the corporate, child-molesting, running-dog imperialist right answer. Interviewers normally ask "puzzle" questions in order to see how the interviewee thinks about problems. We can safely assume that there's a correlation between a person's programming experiences (favorite language, coding style) and that person's likelihood of picking "qsort plus linear search" versus "brute-force O(n^2)" versus "recursive algorithm involving deletions from a linked list".) -Arthur
From: pete on 15 Jun 2005 21:45 spinoza1111(a)yahoo.com wrote: > I still don't see the actual XOR solution. /* BEGIN new.c */ #include <stdio.h> int main(void) { unsigned index; unsigned answer; unsigned array[] = {1,2,3,4,5,6,7,6,5,4,3,2,1}; answer = 0; for (index = 0; index != sizeof array / sizeof *array; ++index) { answer ^= array[index]; } printf("The unique value is %u.\n", answer); return 0; } /* END new.c */ -- pete
From: pete on 15 Jun 2005 21:51
spinoza1111(a)yahoo.com wrote: > I still don't see the actual XOR solution. Can you evaluate this expression at a glance? (10 ^ 9 ^ 123 ^ 9 ^ 10) -- pete |