Basic Algorithms Summer

Making Change

def making_change(coins,target):

MC = [0] * (target +1)

MC[0] = 1

for coin in coins:

for amount in range(coin, target+1):

MC[amount] += MC[amount -coin]

return MC[target]

Subset Sum

def subset_sum(coin, target):

SS = [0] * (target + 1)

SS[0] = 1

for coin in coins:

for amount in range(target, coin-1, -1):

SS[amount] += SS[amount - coin]

return SS[target]

permall driver and function

procedure permalldriver:

for i = 1 to n do:

buffer[i] = i

procedure permall(h):

local i

if h=0 then:

print buffer[1..n]

return

for i=1 to n do:

swap Buffer[h] with Buffer[i]

permall (h-1)

swap Buffer[h] with Buffer[i]

DFS-based reverse topological sort

procedure RobustReverseTopSortDriver(;;v)

mark all vertices as not started

mark all vertices as not done

while there is an unstarted vertex u do

postorderdfs(u)

procedure PostOrderDFS(;;v)

mark v as started

for each neighor w in adj[v]

if w is not yet started then postorderdfs(w)

else if w not yet done then execute cycle detected

print(v)

mark v done

DFS based reverse topological sort: started markings but no done markings

-does not detect the cycle

-incomplete wrong ordering since it can go back to ancestors

DFS based reverse topological sort: done markings but no started markings

-algorithm can’t remember which vertices have been completely processed

-stuck in an infinite loop

Find all pairs (r,s) where A[r] + B[s] = T, where both arrays are strictly increasing

def find_pairs_pseudocode(A, B, T):

A [m+1] = infinity

B[0] = -2 * infinity

i = 1

j = n

results = []

while i < m+1 and j > 0:

sum = A[i] + B[j]

if sum < T: i++

elif sum > T: j--

else:

results.append((i,j))

j--

return results

DFS, # of vertices that are green

function DFS(;;v):

v.count = 0

for each child w in child[v] do:

v.count += DFS(w)

if v is green then increment u.count

else v.count =0

return (v.count)

GFS

-purely green subtree in red/green tree (red root but all green decendants)

procedure driver:

Stack = empty

push T onto Stack

while Stack not empty do

u = pop from Stack

foreach child w in Child[u] do:

if w is red then:

push w onto Stack

else:

DFS(w)

procedure GFS(u);

u.count ← 1;

foreach child w in Child(u) do

if w is red then:

push w onto Stack

else:

GFS(w)

u.count = u.count + w.count

longest consecutive red path starting from each vertex in a tree

procedure rrreds(;,v):

v.longr = 0

for each vertex w in Child[v] do:

rrreds[w]

v.longr = max(v.longr, w.longr)

if v.color == red then:

increment v.longr

else:

v.longr = 0

longest consecutive red path starting from each vertex in a tree: Same problem, but for DAGs

procedure Driver(v):

set all v.longr fields to −1

for each vertex v in V do:

if v.longr = -1:

then RRReds(v)

procedure RRREds(;,v):

v.longr = 0

for each vertex w in Child[v] do:

if w.longr = −1 then:

RRREds[w]

v.longr ← max(v.longr, w.longr)

if v.color == red:

then increment v.longr

else:

v.longr = 0