[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[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).
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
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[0]:
return S[-1]
elif T[-1] < S[0]:
return T[-1]
# We need a base case when the size is of the arrays are 2
if len(S) == 2:
return max(S[0], T[0])
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)
- [Bug-gnubg] OT: An algorithm problem,
Øystein Johansen <=