Re: [Bug-gnubg] OT: An algorithm problem

[Jim Segrave]

On Wed 14 Feb 2007 (16:53 +0100), Øystein Johansen wrote:
> >Here's my idea :
> >Let's name S and T the two vectors.
> >F = {Fx = [S[i],T[j]] such that i+j+2=k}
> >(the +2 coming from python indexing starting at 0)
> 
> Yes, this was also one of my first ideas. (Keeping two index i, j  in each 
> array and having the sum of i and j fixed). I even suggested this solution to 
> the lecturer, who didn't have a clue at that moment, and he claimed that this 
> would work. He says he has implemented a MATLAB code that does this.
> 
> [snip]
> 
> Your code seems to work, however Joseph, found an even simpler way
> by using the i+j>k constrain as the end of iteration indicator. Really clever 
> and simple to implement.
> 
> I will take a look at Jims implementation as well. It really looks rigid
> but I'm not sure which method it uses. At first sight it looks like his idea 
> is 
> the same as Josephs, just more code.

I think it's different - it tries to remove elements from S or T which
are known to be smaller than the element sought. One advantage, such
as it is, is that it copes with degenerate inputs where n is any
value, including 0. The constraint terminating iteration is that
enough items have been removed. I think that Massimiliano's requires
that n >= k (although I've not checked that and I could well be wrong).

If you take out the comments, asserts and debugging prints, it's
probably not much longer than the others, but perhaps not as elegant. 
The debugging and asserts are there because the first couple of
versions which were almost the same idea worked 95% of the time, then
suddenly failed, so I got paranoid whether or not it was 100% correct/


I'm sorry to hear that the course is so unsatisfactory, because the
subject is an interesting one. I can't give any comparisions, because
when I was in university, the attitude there (Caltech) at the time
was that there was no reason to teach anything about computing,
computers were simply tools and you'd hardly offer a university course
on screwdrivers and hammers.

I'm sure that's changed by now.

-- 
Jim Segrave           address@hidden