[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


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 

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 

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.


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)
        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)
    S = L[:size/2]
    T = L[size/2:]
    # print S, "\n", T
    print os_union_find( T, S, size/2)

reply via email to

[Prev in Thread] Current Thread [Next in Thread]