Algorithmic Designs | 2009-01-04

Portfolio » Application Programming

Brute Force

#!/usr/bin/python

# Written by [email protected]

#  Given an array of n integers a_0,a_1,...,a_{n-1} positive
#  and negative, such as [-1, 3, 2, -7, 4, 2, -3, 3, -1], you
#  want to find the largest sum of contiguous integers; in
#  this case it would be 4 + 2 - 2 + 3 = 7.

#  Note: the empty set has sum 0.

def partialsums(a):
    ## computes all of the partial sums in linear time
    ## ans[0] = a[0], ans[1] = a[0]+a[1], ans[2] = a[0]+a[1]+a[2], etc
    ans = []
    sum= 0
    for i in range(0,len(a)):
        if i == 0:
            sum = a[i]
        else:
           *****************# previous sum + current
        ans.append(sum)
   
    return ans
       
def maxsums(a):
    ## "brute force" algorithm to return
    ## the largest sum in time O(n^2)

    ans = 0
    li = partialsums(a)
    for i in range(0,len(a)):
        li.extend(********** **********)
        for j in range(i,len(li)):
            if li[j] > ans:
                ans = li[j]
    return ans

def maxsums_list(a):
    ## "brute force" algorithm to return
    ## the list of values corresponding to
    ## the largest sum in time O(n^2)

    ans = []
    li =[]
    for i in range(0,len(a)):
        maxsumsval = 0
        li = a[i:]
        for j in range(len(li)):
            maxsumsval += li[j]
            if(maxsumsval == maxsums(a)):
                ans = li[0:j+1]
   
    return ans

*** indicated that some partial code has been removed


Divide & Conquer

#!/usr/bin/python

# Written by [email protected]

#  Given an array of n integers a_0,a_1,...,a_{n-1} positive

#  and negative, such as [-1, 3, 2, -7, 4, 2, -3, 3, -1], you

#  want to find the largest sum of contiguous integers; in

#  this case it would be 4 + 2 - 2 + 3 = 7.

 

#  Note: the empty set has sum 0.

###########################################################

 

def partialsums(a):

    ## computes all of the partial sums in linear time

    ## ans[0] = a[0], ans[1] = a[0]+a[1], ans[2] = a[0]+a[1]+a[2], etc

    partial = 0

    ans = []

    for elt in a:

        **********************

        ans.append(partial)

    return ans

 

def maxsums_dc(a):

    ## divide and conquer algorithm to return

    ## the largest sum in time O(n log n)

 

    # Base case step

    if len(a) == 0:

        return 0

    elif len(a) == 1:

        return max(*************)

 

    # Recursive case step

    # '//' is a floor division

    # http://docs.python.org/release/2.2.3/whatsnew/node7.html

    middle = len(a)//2

 

    lsum = 0

    lmax = 0

    # xrange([start], stop[, step])

    # This function is very similar to range()

    # but returns an range object?

    for left in xrange(1, middle + 1):

        lsum += a[middle - left]

       ***********************

 

    rsum = 0

    rmax = 0

    for right in xrange(middle, len(a)):

        rsum += *****************************

        rmax = max(rmax, rsum)

 

    return max(lmax + rmax, maxsums_dc(a[:middle]), *********************))

    #O(n log n)

 

 

*** indicated that some partial code has been removed

 

Dynamic Programming

#!/usr/bin/python

# Written by [email protected]

#  Given an array of n integers a_0,a_1,...,a_{n-1} positive

#  and negative, such as [-1, 3, 2, -7, 4, 2, -3, 3, -1], you

#  want to find the largest sum of contiguous integers; in

#  this case it would be 4 + 2 - 2 + 3 = 7.

 

#  Note: the empty set has sum 0.

 

def partialsums(a):

    ## computes all of the partial sums in linear time

    ## ans[0] = a[0], ans[1] = a[0]+a[1], ans[2] = a[0]+a[1]+a[2], etc

    partial = 0

    ans = []

    for elt in a:

        ******************

        ans.append(partial)

    return ans

 

def maxsums_dp(a):

    ## using dynamic programming to find

    ## the largest sum in time O(n)

 

    ## you will need to figure out what your sub-problem is

    maxsum = 0

    maxindex = 0

    for i in xrange(0, len(a)):

      *******************************************

        maxsum = ********************

    return maxsum

    #O(n) 

*** indicated that some partial code has been removed


Optimum Path

#!/usr/bin/python
# Written by [email protected]

def switch(a, b):
## assume a and b are 1-indexed and n = no. of minutes
    n = len(b)
    opt = [0] * (2 * n)
    opt[0] = a[0]
    opt[1] = b[0]
    for i in range(1, n):
        opt[*********] = max(a[i] + opt[2 * (i-1) + ***], opt[2 * (i-***) + ***])
        opt[*********] = max(b[i] + opt[2 * (i-1) + ***], opt[2 * (i-***) + ***])
    return max(opt[2 * n - 2], opt[2 * n -1])

*** indicated that some partial code has been removed


DNA Longest Substring

""" (a) O(n^4)

    (b) O(n)

"""


def longest_substring(s, t):

    """Finds the longest substring that occurs in both s and t"""

    result = ''

    minLength = 0

    maxLength = min(len(s), len(t))

    while **************************

        mid = (minLength + maxLength)/2

        ans = k_substring(s, t, mid)

        if ans is None:

            maxLength = mid-1

        else:

             *************
             ****************

    return result



def k_substring(s, t, k):

    """Finds a substring of length k in both s and t if there is one,

    and returns it. Otherwise, returns None."""

    substr_set = set() # set for storage

    

    for s_start in range(len(s)-k+1):

        current = s[*********************]

        substr_set.add(current)

    

    # find substring between s and k

    for t_start in range(len(t)-k+1):

        current = t[********************]

        if current in substr_set:

            return current

    return None

*** indicated that some partial code has been removed

 

Minimum Spanning Tree

# Written by [email protected] 

def parent(i):

    return i/2


def left(i):

    return 2*i


def right(i):

    return 2*i+1


class heap:

    """

    Python implementation of minheap, using 1-based indexing.

    """


    def __init__(self):

        self.A = [None] # To make the heap 1-based, None is stuck in slot 0.

        self.heapsize = 0

        

    def __getitem__(self, i):

        return self.A[i]


    def heapify_up(self, i):

        if i >= 1:

            j = parent(i)

            if self.A[i] < self.A[j]:

                self._swap(**************)

                self.heapify_up(j)


    def heapify_down(self, i):

        ## fill in the implementation of heapify_down

        if left(i) > self.heapsize:

            return None

        elif left(i) < self.heapsize:

            if *************************

            else:

                j =*********************

        elif left(i) == self.heapsize:

            j = left(i)

        if self.A[j] < self.A[i]:

            self._swap(j, i)

            self.heapify_down(j)

            


    def insert(self, v):

        """inserts the item v into the heap"""

        ### fix the following buggy implementation of insert

        self.heapsize ***************

        self.A.append(******)

        self.heapify_up(self.heapsize)


    def delete(self, i):

        """deletes the element in heap position i"""

        ### fix the following buggy implementation of delete

        if i == self.heapsize:

            self.A.pop()

        else:

            ******************

        ****************

        self.heapify_down(i)

        

    def extract_min(self):

        if self.heapsize < 1:

            print "error: empty heap"

            return

        min = **************

        self.delete(1)

        return min

    

    def _swap(self, index1, index2):

        self.A[index1], self.A[index2] = self.A[index2], self.A[index1]



class positive_infinity:

    "bigger than any object other than itself"

    def __cmp__(self, other):

        if isinstance(other, self.__class__):

            return 0

        return 1


class negative_infinity:

    "smaller than any object other than itself"

    def __cmp__(self, other):

        if isinstance(other, self.__class__):

            return 0

        return - 1


*** indicated that some partial code has been removed


Breadth-First Search Tree

verbose = False


def edges2nb(n, edges):

    # pre-processing to convert a list of edges into adj. list representation

    # n is the no. of vertices, and we assume vertices are numbered 1,2,..,n

    # edges is a list of edges

    # e.g. n = 3, edges = [(1,2),(1,3)]; then nb[1] = [2,3], nb[2] = [1], nb[3] = [1]


    nb = [[] for n in range(n+1)]   ## the error lies in this line  

    

    for edge in edges:

        nb[edge[0]].append(edge[1])

        nb[edge[1]].append(edge[0])

    return nb


def bfs(n, edges, s):

    # runs BFS on the graph ([n], edges) starting from node s

    # n and edges as before, s is the start node for BFS

    # e.g. n = 3, edges = [(1,2),(1,3),(2,3)], s =1: output will be [(1,2),(1,3)]


    nb = edges2nb(n, edges)

    discovered = [False] * (n+1)

    discovered[s] = True

    i, L, T = ******************  ## the error lies in this line


    while (L[i]):   

        #if verbose: print "level ", i, " : ", L[i]

        L.append([])

        for u in L[i]:   

            # add all undiscovered neighbors of u

            for v in nb[u]:

                if not discovered[v]:

                    discovered[v] = True

                    T.append((u,v))

                    L[i+1].append(v)

                    

        ****************              ## the error lies in this line

    return T


def bfs_path(n, edges, s, t):

    # on the graph ([n], edges), return

    # the shortest path from s to t

    if s==t:

        return [t]     

    else:

        bfs_tree=***************

        for edge in bfs_tree:

           *****************   

                break

    return  bfs_path(n, edges, s, edge[0])+[t]

 

*** indicated that some partial code has been removed


Sub Sequence

#!/usr/bin/python


def subsequence(p, s):

    # p's length must less or equal to s

    if len(p) > len(s):

        return *****

    

    # loop thru to remember how many found

    StrFound = 0

    for str in p:

        ********************
*****************************
**************

            

    # if found # match

    if StrFound == len(p):

        return True

    else:

        return False

*** indicated that some partial code has been removed

 

Time Stamp Matching

#!/usr/bin/python

 

# Written by [email protected] 


def timestamp_matching(t, x):

    """checks whether the events x match the approximate time-stamps in t"""

    """t is a 0-indexed list where t[i] is a list of 2 entries [t_i,e_i]

       corresponding to the time interval t_i +/- e_i"""

    """x is a 0-indexed list where x[i] is the time x_i"""

    

    x.sort()

    ## sort the list x

    t.sort(key=lambda y: y[0]) 

    ## sort the list t according to the values t_i

    

    # my algorithm start here

    # t, x

    XLength=len(x)

    TLength=len(t)


    i_count, j_count = 0,0

    while i_count *************:

        while **************** :

            if ********( (t[j_count])[0] - x**********) <= (*********])[*]:

                i_count+= *****************

               ***************

            else:

                j_count += 1

        if j_count == ***:

            return False

    return True


# Test only

# t, x

#timestamp_matching([[1,1],[2,1]],[2,3]) # True

#timestamp_matching([[1,1],[2,1]],[5,5]) # False

#timestamp_matching([[3,3],[3,1]],[1,3]) # True

#print 2 in range(1,3)

 

*** indicated that some partial code has been removed

 

 

Dijkstra Shortest Path

# Written by [email protected]

import heap_id

import math


def node_by_name(nodes, city, state):

    nodes_length = len(nodes)

    i_count = 0

    #print(city)

    while i_count < nodes_length:

        if nodes[*********].***** == state:

            if (********************.count(city) > 0:

                #print nodes[i_count].description

                return nodes[i_count]

        i_count += 1

    return False # in case couldn't find


def distance(node1, node2):

    # distance = SquareRoot( (x2 - x1)^2 + (y2 - y1)^2 )

    x1 = node1.longitude

    y1 = node1.latitude

    x2 = node2.longitude

    y2 = node2.latitude

    #print(x2,x1,y2,y1)

    #distance = math.sqrt( (********************************)

    # In python ^ 2 is express as ** 2

    distance = math.sqrt( *************** **2 )

    return distance


def shortest_path(nodes, edges, weight, s, t):

    # http://docs.python.org/tutorial/datastructures.html

    """>>> tel = {'jack': 4098, 'sape': 4139}

    >>> tel['guido'] = 4127

    >>> tel

    {'sape': 4139, 'guido': 4127, 'jack': 4098}

    """

    # Create empty data storages of dictionaries

    adj_list = {}   # nodes and edges 

    node_to_id = {}  # node to id reference

    id_to_node = {} # id to node reference

    ************** = {} # node's parent reference

    node_to_key = {} # node to heap key reference

    

    # heap_id object instance

    id_heap = heap_id.heap_id()

    

    for edge in edges:

        # beginning node to ending node

         ******************
         ***********************

        # ending node to beginning node

        if edge.end in adj_list:

            adj_list[edge.end].append(edge.begin)

        else:

            adj_list[edge.end] =******************

    

    # node to key reference dictionary

    for node in nodes:

        # parent node

        if node == s:

            **************************

            node_to_key[node] = 0   # node_to key 0

            ***************** = None # no parent

        # child node

        else:

           ******************************

            node_to_key[node] = heap_id.positive_infinity # node_to key to positive_infinity

        # new references

        node_to_id[node] = id            #update node_to_id dictionary

        *******************************

    

    # check what nodes still left

    while node_to_id:

        ****************************    # extract min node use heap_id obj id_heap

        ext_min_node_node = id_to_node[ext_min_node[1]] # node

        ext_min_node_key = ext_min_node[0]  # key

        # delete id for the ext min node

        del node_to_id[**************************]

        # has outgoing edges ?

        if ext_min_node_node in adj_list:

            for idx in adj_list[ext_min_node_node]: # loop thru the dictionary

                if ext_min_node_key != ***********************: # has a connected path to

                    # weight priority queue

                    if node_to_key[idx] > ext_min_node_key + weight( ext_min_node_node, idx ):

                        node_to_key[idx] = ext_min_node_key + weight( ext_min_node_node, idx )

                        id_heap.decrease_key_using_id(node_to_id[idx], node_to_key[idx]) # decrease key

                        node_to_parent[idx] = ************** # parent node


    # prepare for shortest path result

    result_list = []

    result_list.append(t) # put destination into result

    node = t # where t is destination

    

    # parent insertion

    while node_to_parent[node] is not None: # 'is not None' is not equal to '!='

        ************************ # node

        node = node_to_parent[node] # parent

 

    return result_list

 

*** indicated that some partial code has been removed

 

Fraud Check Divide and Conquer

#!/usr/bin/python


# Written by [email protected]

def fraudcheck(L):

    """takes a list L of length n"""

    """outputs True if there's an element in L that appears > n/2 times"""

    (ans, aux) = fraudcheckhelper(L)

    return ans


def fraudcheckhelper(L):

    """takes a list L of length n"""

    """this function should return some function in addition to True/False"""


    if len(L) == 1: ## this is the base case

        return (***********)

    

    mid = len(L)/2  ## this is the divide step

    List1 = L[:mid]

    List2 = L[mid:]

    (ans1, aux1) = fraudcheckhelper(List1)

    (ans2, aux2) = fraudcheckhelper(List2)

    

    if ( L.count(aux1)>mid ) or ( *********** ) or ( *********>len(L)/4 and List2.count(aux2)>len(L)/4 and aux1******************aux2 ):

        return (***************)

    else:

        return (*************)

 

*** indicated that some partial code has been removed

 

 

Coins Make Change

#!/usr/bin/python

 

# Written by [email protected] 


def make_change(denomination, C):


    ## Here is some skeletal code to help you get started.


    ## initialization; you should replace 100 with a quantity

    ## related to the number of sub-problems

    """"

    opt = [0] * (100)     ## opt for sub-problems

    parent = [0] * (100)  ## maintain parent nodes for back-tracking


    ## solving the sub-problems

    for i in range(1,100):

        *****************


    ## back-tracking

    ans = []

    while (*************):

        ans.append(0)

        i = parent[i]

     """       

    list = [None for element in range(C + 1)]

    list[0] = []

    for i in range(**************):

        for cointype in ******************:

            if cointype > i: continue

            elif not ********* or ( ******************************** ):

                list[i] = list[******************][:]

               *****************

    #print(list[-1])

    return list[-1]

#test

#make_change([1, 5, 10, 17], 33)

*** indicated that some partial code has been removed

 

Progress

#!/usr/bin/python

 

# Written by [email protected]

def longest_increasing_subsequence(scores):

    """ This function takes a list of scores, and returns the longest increasing

        subsequence of those scores. It uses dynamic programming and finds the answer

        in a bottom up manner. """

    scores_length = len(scores)

    if scores_length == 0:  # empty input return it

        return []

    # storages

    parentdict = {} # dictionary of parent

    maxscoredict = {}   # dictionary of LIS ends at index i

    #######################################################

    # iterate score in scores list

    ****************** # fist index i initialize to 0

    for i in range(scores_length):

        ********************************

        maxjparent = -1 # parent of the max score for all j < i

        for j in range(i):

            # if score[i] and maxscoredict[j] is the new large value

            if ( *********************************** ):

                maxjparent = j

                *****************************************

        parentdict[i] = *************

       *********************# add 1 to subproblem at i below

        maxscoredict[i] = maxjscore

        

    #######################################################

    # iterate score and do max compare to dictionary

    maxival = 0

    maxiindex = 0

    for k in range(scores_length):

        if ***********************

            maxiindex = k

            ********************

    lislist = [***********************] # build score list with last index on scores

    #######################################################

    # iterate when it has parent

    while parentdict.has_key(parentdict[maxiindex]):

        **************************

        lislist.append(scores[maxiindex])

    #######################################################

    # result

    #print(lislist)

    lislist.reverse() # reverse list element order

    return lislist

 

*** indicated that some partial code has been removed

 

Merge Sort

#!/usr/bin/python

# Written by [email protected]


import time


## write down T(n) for  n = 1000, 2000, 4000, 10000, 20000

# Running time tested on the bottom

# These are the console return

#

#===============================================================================

# ('T(1000): ', 0.031000137329101562, 'seconds')

# ('T(2000): ', 0.03099989891052246, 'seconds')

# ('T(4000): ', 0.07899999618530273, 'seconds')

# ('T(10000): ', 0.23399996757507324, 'seconds')

# ('T(20000): ', 0.46900010108947754, 'seconds')

# ('T(40000): ', 0.9839999675750732, 'seconds')

#===============================================================================

#


def merge(a, b):

    """combines two sorted lists into shorted whole"""

    i, j, out = 0, 0, []

    while i<len(a) and j<len(b):

        if a[i] < b[j]:

            out.append(a[i])

            i = i + 1

        else:

            out.append(b[j])

            j = j + 1

            

    if(len(a)>i):

        out.extend(*************)

    elif(len(b)>j):

        ******************

    

    return out


def mergesort(a):

    if len(a) <= 1:

        return a

    else:

        mid = ***************

        return merge(mergesort(********),mergesort(*************))


def mergetest(n):

    a = range(1,n)

    a.reverse()

    return mergesort(a)



# TEST Running Time for T(n)

# ---------------------------------------------------

#===============================================================================

# start_time = time.time()

# mergetest(1000)

# end_time = time.time()

# print ('T(1000): ', end_time - start_time, 'seconds')

# start_time = time.time()

# mergetest(2000)

# end_time = time.time()

# print ('T(2000): ', end_time - start_time, 'seconds')

# start_time = time.time()

# mergetest(4000)

# end_time = time.time()

# print ('T(4000): ', end_time - start_time, 'seconds')

# start_time = time.time()

# mergetest(10000)

# end_time = time.time()

# print ('T(10000): ', end_time - start_time, 'seconds')

# start_time = time.time()

# mergetest(20000)

# end_time = time.time()

# print ('T(20000): ', end_time - start_time, 'seconds')

# start_time = time.time()

# mergetest(40000)

# end_time = time.time()

# print ('T(40000): ', end_time - start_time, 'seconds')

#===============================================================================

 

*** indicated that some partial code has been removed

 

Ford–Fulkerson

#!/usr/bin/python
# Written by [email protected]

from maxflow import maxflow
from maxflow import edges2matrix

def cooking(notavail):
    n = len(notavail)
    edgesC = []
    
    for i in range(1,n+1):
        edgesC.append([0,i,1])
        for j in range(1,n+1):
            if j in notavail[i-1]:
                *********
        edgesC.append([i,j+n,1])

    for k in range(n+1,n*2+1):
        #print("k")
       *********
    
    # construct adj list
    adjlist = edges2matrix(n*2+2, *********)
    
    if (maxflow(adjlist,0,n*2+1)!=*********):
        #print("F")
        return False
    else:
        #print("T")
        return True