kflu

class QSort:
    def __init__(self, A):
        self.A = A
    def partition(self, L, U):
        s = U
        p = L
        while s != p:
            if self.A[p] <= self.A[s]:
                p += 1
            else:

kflu

using System;
using System.Collections.Generic;

namespace ConsoleApplication14
{
    class Program
    {
        static void Main(string[] args)
        {
            var A = new int[] { 4, 3, 5, 2 };

kflu

def C(S,k):
    '''Choose k elements from set S.'''
    assert len(S) >= k
    if k==0:
        yield set()
    S1 = S.copy()
    for s in S:
        S1.remove(s)
        if len(S1) >= k-1:
            for c in C(S1, k-1):

kflu

def strperm(S):
    if not S: yield ""
    for c in S:
        for perm in strperm(S - set([c])):
            yield c + perm

for s in strperm(set("abcd")):
    print s

kflu

class PrintParenth:
    def __init__(self, n):
        self.n = n
        self.s = [None for i in range(2*n)]

    def P(self, l, r):
        if l==self.n and r==self.n:
            yield ''.join(self.s)
        if l < self.n:
            self.s[l+r] = '('

kflu

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using SimpleTest;

namespace EditDistance
{
    class Program

kflu

""" Balanced partition

You have a set of n integers each in the range 0 ... K. Partition these
integers into two subsets such that you minimize |S1 - S2|, where S1 and S2
denote the sums of the elements in each of the two subsets.

http://people.csail.mit.edu/bdean/6.046/dp/

"""

kflu

'''Building Bridges

Building Bridges. Consider a 2-D map with a horizontal river passing through
its center. There are n cities on the southern bank with x-coordinates a(1) ...
a(n) and n cities on the northern bank with x-coordinates b(1) ... b(n). You
want to connect as many north-south pairs of cities as possible with bridges
such that no two bridges cross. When connecting cities, you can only connect
city i on the northern bank to city i on the southern bank.

http://people.csail.mit.edu/bdean/6.046/dp/

kflu

"""Box stacking with the maximum height.

Box Stacking. You are given a set of n types of rectangular 3-D boxes, where
the i^th box has height h(i), width w(i) and depth d(i) (all real numbers). You
want to create a stack of boxes which is as tall as possible, but you can only
stack a box on top of another box if the dimensions of the 2-D base of the
lower box are each strictly larger than those of the 2-D base of the higher
box. Of course, you can rotate a box so that any side functions as its base. It
is also allowable to use multiple instances of the same type of box.

kflu

"""Find the longest increasing subsequence.

Given a sequence of n real numbers A(1) ... A(n), determine a subsequence (not
necessarily contiguous) of maximum length in which the values in the
subsequence form a strictly increasing sequence.

[http://people.csail.mit.edu/bdean/6.046/dp/]

Optimal subproblem: