Subj : Re: puzzle
To   : comp.programming
From : Ben Bacarisse
Date : Tue Jun 28 2005 04:46 pm

On Tue, 28 Jun 2005 01:01:08 -0700, spinoza1111 wrote:

> Given enough of anything, anything will work. The point being that the
> problem is O(n^2) and not O(n) because you have to introduce a
> conversion magical from the standpoint of theory to make it O(n)

It is not usual to ascribe complexities to problems.  It can be done, but
it is very hard (problems are usualy assigned to broader categories like
P, NP, NP-Hard and so on).  For the *problem* to be O(n^2) you would have
to show that *any* algorithm that solves it required *at least* O(n^2)
time (or whaterv the measure was).

Two algoroithms have been outlined that are O(n) if the size of the
numbers is bounded: not one, two.  One uses XOR, the other partitions the
array about (ideally) its median element.  How on earth can the problem be
O(n^2) then?

If you exclude XOR, for bouned numbers, the same solution can be written
using a *constant* number of divisions and odd/even tests (mod 2
operations) in place of each XOR.  The result is an O(n) algorithm that
does not use XOR.  If you insist on sticking with your O(n^2) claim you
must at least falsify the arguments that these two algorithms are O(n).

This would a shame because I *agree* with a lot of what you have said.  I
used to lecture in CS and despite teaching a number of courses, the one I
consistently enjoyed developing was the introductory programming course.

I found, as you have, that puzzles make bad pedagogic tools.  There is no
reliable route to the "aha!" moment and you get students smugly guarding
their "gems" rather than contributing to a lively debate about lines of
attack and possible solutions.

In the end, I found I got the best "buzz" in the lab from very open ended
problems.  You'd have to ask the students if it actually worked, but it
was fun to teach that way.

It is none the less useful to know a number of neat solutions to
interesting problems.  This puzzle and others like it shed light on coding
systems, redundancy and information representation, but the best place for
them is as "interesting asides" and "further reading".

I strongly reccommended Bently's "Programming Pearls" (and still
do) because it illustrates how clear algorithmic thinking can "crack"
hard nuts.  But it never goads the less intuitive students with that
"haven't you got it yet?" feeling. 

-- 
Ben.

.