My silicon valley experience

Yesterday I had to implement an approximation algorithm for the subset sum problem for a class at university. Since this algorithm contains a lot of list operations I decided to use Python for this since it’s a great language for this kind of stuff and I wanted to be done fast. This turned out to be a great choice since I had really a lot of fun using Python for a project again. I sometimes use Pythons IDLE as a better calculator but that’s it for the last year. It was just beautiful how well Python works out for list operations! Adding a number to every element in a list and being able to filter these elements in the same step is nothing but elegant. I wanted to have a look at the Google App Engine soon which uses Python and now I am even more looking forward to that.

Here is the little program I wrote. It’s based on the approximation algorithm give in
Introduction to Algorithms

def approxSubsetSum(S, t, epsilon):
    L=[[0]]
    print "L_%s: %s"%(0,L[0])
    for i in range(1,len(S)+1):
        #MERGE
        L.append(L[i-1]+[x +S[i-1]for x in L[i-1]])
        L[i] = dict.fromkeys(L[i]).keys()
        L[i].sort()
        #TRIM
        L[i] = trim(L[i],epsilon/(2*len(S)))
        #Cut off too large elements
        L[i] = [x for x in L[i] if x<= t]
        print "L_%s: %s" %(i,L[i])
    return L[-1][-1]

def trim(L, sigma):
    m = len(L)
    L2 = [L[0]]
    last = L[0]
    for l in L[1:]:
        if l > last*(1+sigma):
            L2.append(l)
            last=l
    return L2