bug-gnubg
[Top][All Lists]

[Bug-gnubg] OT: An algorithm problem

 From: Øystein Johansen Subject: [Bug-gnubg] OT: An algorithm problem Date: Fri, 09 Feb 2007 12:30:36 +0100

```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).

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

-Øystein

PS: Here's some python code that doesn't work.

import random

def os_union_find( S, T, k ):
""" Find the k'th smallest element in the union of S and T """

print S, T

if S[-1] < T:
return S[-1]
elif T[-1] < S:
return T[-1]

# We need a base case when the size is of the arrays are 2
if len(S) == 2:
return max(S, T)

mid = len(S)/2

if S[mid] > T[mid]:
return os_union_find( S[:mid], T[mid:], k/2)
else:
return os_union_find( S[mid:], T[:mid], k/2)

def max(a, b):
if a > b:
return a
else: return b

if __name__ == "__main__":
size = 32
L = range(size)
random.shuffle(L)
S = L[:size/2]
T = L[size/2:]
S.sort()
T.sort()
# print S, "\n", T
print os_union_find( T, S, size/2)

```