kflu

import unittest

def FindMajority(array, M):
    '''Find elements that occurs more than(>) N/M times in the array of size N
    
    array: the array that is to be scanned through for elements returns a
    dictionary with keys set to elements that occur more than(>) N/M times in
    the array of size N. The key's values are their number of occurrences.

    '''

kflu

'''Quicksort implementation according to CLRS'''

import unittest

def _swap(array, i, j):
    tmp = array[i]
    array[i] = array[j]
    array[j] = tmp

def _partition(array, lower, upper):

kflu

class LIS:
    def __init__(self, A):
        self.A = A
        self.N = len(A)
        self.table = self.init_table()

    def init_table(self):
        table = [[0,-1] for i in xrange(self.N)]
        table[0][0] = 1
        return table

kflu

import pytest

class MaxSumSeq:
    def __init__(self, A):
        assert A
        self.A = A
        self.n = len(A)
        self.tab = [None for i in range(self.n)]
        self.tab[0] = self.A[0]

kflu

"""Changing the bill with minimum number of coins."""

class EmptyVError(Exception): pass

class CoinChanger:
    def __init__(self, C, v):
        if not v: raise EmptyVError

        self.C = C
        self.v = v

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:

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

'''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

""" 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

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

namespace EditDistance
{
    class Program