 ## 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 = a, ans = a+a, ans = a+a+a, 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 = a, ans = a+a, ans = a+a+a, 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 = a, ans = a+a, ans = a+a+a, 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 =  * (2 * n)
opt = a
opt = b
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[*********************]

# 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

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 = [2,3], nb = , nb = 

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

for edge in edges:

nb[edge].append(edge)

nb[edge].append(edge)

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)+[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)

## 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]) - 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:

else:

# 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] # node

ext_min_node_key = ext_min_node  # 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 =  * (100)     ## opt for sub-problems

parent =  * (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 = []

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, *********)