puzzle
in [General Programming]
|
Prev: Algorithm book recommendation?
Next: TaskScheduler.dll
From: spinoza1111 on 11 Jun 2005 01:45 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. > > [snip much dissembling] > > The "trick" answer, which has already been posted, is definitely > the one the OP['s instructor] was thinking of. It's actually quite > elegant, IMHO, if not terribly useful for anything. > "Elegant?" I don't think so. The instructor apparently is sidetracking the students from discussion of algorithms (which should in no case impose a barbaric and unstated prejudice for O(n) which is a yahoo's moral judgement masquerading as science) to the properties of Boolean operators. This characterization of a discussion as "dissembling" when it showed how the theoretical classification has levels within levels explains the 80% failure rate of enterprise systems, for it clearly shows that some American "programmers" are invested in cheap tricks and cheap shots and care not for that form of dialog from which real results can be obtained.
From: Gerry Quinn on 11 Jun 2005 07:45 In article <Pine.LNX.4.60-041.0506101825130.6453 @unix49.andrew.cmu.edu>, ajo(a)nospam.andrew.cmu.edu says... > The "trick" answer, which has already been posted, is definitely > the one the OP['s instructor] was thinking of. It's actually quite > elegant, IMHO, if not terribly useful for anything. It's a pity he posted it (the 'hint' was as good as posting) as it might have stimulated a few more attempts at solving the puzzle. The 'trick' solution can be generalised into the separation of a single number that is present any odd number of times from ones that are present any even number of times. That seems to me like it just might be useful now and again. - Gerry Quinn
From: Thad Smith on 11 Jun 2005 23:00 Emlyn Corrin 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. > > hint: xor Clever! Thad
From: spinoza1111 on 11 Jun 2005 21:49 pete wrote: > spinoza1111(a)yahoo.com wrote: > > > 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. > > Whatever O(n * n / 2) could possibley mean > is what O(n * n) actually means. > Constant factors aren't part of big O notation. Of course not. But, n*n/2 != n*n for positive n: n*n/2 < n*2 for n>0. The resentment here is of ability to explain, complementary to the inability to read shown by O'Dwyer who read a claim for O(n) when I said "close to". This resentment then morphed into the usual anhedonic personal attacks by people who don't belong here, because they use this newsgroup, having been, it seems, excluded from moderated groups in particular and polite circles in general by virtue of their anger management problems, to vent their hurt. This explains the 80% failure rate of enterprise systems development because mathematics as such is undoable in such an environment. It's reduced to vulgar tricks. If n gets too-large, dividing it by 2 is too large. But in a realistic scenario this is useful. > > -- > pete
From: Randy Howard on 11 Jun 2005 19:09
In article <42AB14A3.EB6FFF83(a)yahoo.com>, cbfalconer(a)yahoo.com says... > spinoza1111(a)yahoo.com wrote: > > > ... snip ... > > > > 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. > > Showing total non-comprehension of the meaning of O notation. What were you expecting? -- Randy Howard (2reply remove FOOBAR) "I don't really care about being right you know, I just care about success." --Steve Jobs |