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

[Massimiliano Maini]

address@hidden
wrote on 09/02/2007 12:30:36:

> Hi,
> 
> As some of you may know I'm now taking an CS education. (At last).
> In an exercise in the course "Algorithm and complexity",
I was faced
> with this challenge:
> 
> Describe an algorithm that takes two ordered sets (implemented as
> arrays) S and T (no duplicates in the two sets) of size n, and k,
to
> find the k-th smallest key in the union of S and T. The running time
> should be of order O(lg n).
> 
> I've already handed in an answer, but I realize my answer is plain
> wrong. Think about this problem for a while and you will find it 
> both challenging and interesting.
> 
> BTW: I believe my lecturer won't have an answer to this problem 
> either, and I would love see one. So, if anyone can suggest a 
> working implementation, I would be really glad.
> 
> -Øystein

I'm new to python hence my code is probably horrible.

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)

Each element of F is given by a pair of indexes (i
and j) into the two
vectors S and T (respectively) such that the number
of elements encompassed
by the two indexes is exactly k.

Example :

        S    
           T
========================
        2    
           0
        3    
           1
        7    
           4
        8    
           5
        12    
           6
        14    
           9
        15    
           10

For k==7, F is {[14,0], [12,1], [8,4], [7,5], [3,6],
[2,9]}.
Imagine a line connecting the elements, you'll see
a kind of front
moving across the two vectors (like a fluid into two
connected bottles,
if you push the fluid in a bottle, the level in the
other will raise).

Notice that the last values of each array (15 and
10) are excluded
since they are somehow pathological (easy to nuderstand
why).

Cx = max(Fx) : Cx is the maximum of the two values
in Fx.

Now the k-th smallest element is G = min(Cx) = min(max(Fx))

If you start from the vector with the largest element,
you can just 
search linearly and stop as soon as Cx changes vector.
Example :

F0 = [14,0] --> Cx = 14 (in S)
F1 = [12,1] --> Cx = 12 (in S)
F2 = [ 8,4] --> Cx =  8 (in S)
F3 = [ 7,5] --> Cx =  7 (in S)
F4 = [ 3,6] --> Cx =  6 (in T ==> STOP)

The 7th smalles element is 6.

Now the idea is to search using dicothomy ... pretty
tricky to implement however.

Seems to work for me .... and it looks O(ln k)

MaX.

max-find-kth-smallest.py
Description: Binary data