def inverse_graph(graph): n = len(graph) inverted_graph=[] for i in range(0, n): inverted_graph.append([]) for j in range(0, n): if (i != j): inverted_graph[i].append(1-graph[i][j]) else: inverted_graph[i].append(0) return inverted_graph def test(): g1 = [[0, 1, 1, 0], [1, 0, 0, 1], [1, 0, 0, 1], [0, 1, 1, 0]] assert inverse_graph(g1) == [[0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0], [1, 0, 0, 0]] g2 = [[0, 1, 1, 1], [1, 0, 1, 1], [1, 1, 0, 1], [1, 1, 1, 0]] assert inverse_graph(g2) == [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Careful Oh
def isprime(n): if n < 2: return False if n == 2: return True if n % 2 == 0 return False for i in range(3, int(n**0.5) + 1, 2): if n % i == 0: return False return True
challenging problems
what to do about them
-> Theoretical Computer Science
・Recognize
・Understand
・Navigate
minimum_devices = number of communication centers for each assignment of (0,1) to the communication centers: if assignment is valid number_of_devices = number of "l"s in assignment minimum_devices = min(minimum_devices,number_of_devices)
largest_group = 0 for each assignment of (0, 1) to the genes: if assignment is valid: group_size = number of "1"s in assignment largest_group = max(largest_group, group size)
Implementing
def shortest_dist_node(dist):
best_node = 'undefined'
best_value = 1000000
for v in dist:
if dist[v] < best_value:
(best_node, best_value) = (v, dist[v])
return best_node
def dijkstra(G,v):
dist_so_far = {}
dist_so_far[v] = 0
final_dist = {}
while len(final_dist) < len(G):
w = shortest_dist_node(dist_so_far)
final_dist[w] = dist_so_far[w]
del dist_so_far[w]
for x in G[w]:
if x not in dist_so_far:
dist_so_far[x] = final_dist[w] + G[w][x]
elif final_dist[w] + G[w][x] < dist_so_far[x]:
dist_so_far[x] = fianl_dist[w] + G[w][x]
return fianl_dist
def make_link(G, node1, node2, w):
if node1 not in G:
G[node1] = {}
if node2 not in G[node1]:
(G[node1])[node2] = 0
(G[node1])[node2] += w
if node2 not in G:
G[node2] = {}
if node1 not in G[node2]:
(G[node2])[node1] = 0
(G[node2])[node1] += w
return G
mean
L = [2, 3, 2, 3, 2, 4] def mean(L): total = 0 for i in range(len(L)): total += L[i] return (0.0+total)/len(L) print mean(L)
define max value on the list
def max(L):
max_so_far = L[0]
for i in range(len(L)):
if L[i] > max_so_far: max_so_far = L[i]
return max_so_far
def max(L)
search most popular name in US in 1995
f = open("yob1995.txt", "r")
maxname = "none"
maxval = 0
max2name = "none"
max2val = 0
for line in f:
(name, sex, count) = line.rsplit(",")
count = int(count)
if sex == "F":
if count > maxval:
max2name = maxname
max2val = maxval
maxval = count
maxname = name
elif count > max2val:
max2name = name
max2val = count
print maxname, max2name
print maxval, max2val
L = [31, 45, 91, 51, 66, 82, 28, 33, 11, 89, 84, 27, 36]
def partition(L, v):
smaller = []
bigger = []
for val in L:
if val < v: smaller += [val]
if val > v: bigger += [val]
return smaller + [v] + bigger
print partition(L,84)
L = [31, 45, 91, 51, 66, 82, 28, 33, 11, 89, 84, 27, 36]
def partition(L, v):
smaller = []
bigger = []
for val in L:
if val < v: smaller += [val]
if val > v: bigger += [val]
return (smaller + [v] + bigger)
def top_k(L, k):
v = L[random.randrange(len(L))]
(left,middle,right) = partition(L, y)
if len(left) == k: return left
if len(left)+1 == k: return left+[v]
if len(left) > k: return top_k(left,k)
return left+[v]+top_k(right,k-len(left)-1)
print top_k(L,5)
time1 = time.time()
charG = {}
for char1 in characters:
for book in marvelG[char1]:
make_link(charG, char1, char2)
time2 = time.time()
print "time to compute strengths: ", time2-time1
time1 = time.time()
k = 10
heap = []
for char1 in charaters:
for char2 in charG[char1]:
if characters[char1] < characters[char2]:
if len(heap) < k:
insert_heap(heap, (charG[char1][char2],(char1, char2)))
elif charG[char1][char2] > val(heap[0]):
magic trick
speed, weight lifespan brain
animals = [("dog", 46, 35, 13, 280),
("elephant", 30, 3500, 50, 6250),
("frog", 5, 0.5, 8, 3),
("hippopotamus", 45, 1600, 45, 573),
("horse", 40, 385, 30, 642),
("human", 27, 80, 78, 2000),
("lion", 50, 250, 30, 454),
("mouse", 8, 0.025, 2, 0.625),
("rabbit", 25, 4, 12, 40),
("shark", 26, 230, 20, 92),
("sparrow", 16, 0.024, 7, 2)]
def importance_rank(items, weight):
names = [item[0] for item in items]
scores = [sum([a*b for (a,b) in zip(item[1:], weights)]) for item in items]
results = zip(scores,names)
res2 = sorted(results)
return res2
answer = importance_rank(animals, (2,3,7,1))
for i in range(len(answer)):
print i, answer[i][1], "(", answer[i][0], ")"
Recurrence Relation
def makeG(N): if n == 1: return <a single node> g1 = makeG(n / 2) g2 = makeG(n / 2) for i in range(log(n)): i1 = <random node from g1 without replacement> i2 = <random node from g2 without replacement> make_link(G, i1, i2) return G
def mark_component(G, node, marked):
marked[node] = True
total_marked = 1
for neighbor in G[node]:
if neighbor not in marked:
total_marked += mark_component(G, neighbor, marked)
return total_marked
def check_connection(G, v1, v2):
marked = {}
mark_component(G, v1, marked)
def make_line(G, node1, node2):
if node1 not in G:
G[node1] = {}
(G[node1])[node2] = 1
if node2 not in G:
G[node2] = {}
(G[node2])[node1] = 1
return G
def test():
edges = [('a', 'g'),('a', 'd'),('g', 'c'),('g', 'd'),
('b', 'f'),('f', 'e'),('e', 'h')]
G = {}
for v1, v2 in edges:
make_link(G, v1, v2)
assert check_connection(G, "a", "c") == True
assert check_connection(G, 'a', 'b') == False
complete graph
def make link(G, node1, node2):
if node1 not in G:
G[node1] = {}
(G{node1})[node2] = 1
G[node2] = {}
(G[node2]){node1} = 1
return G
def clique(n):
G = {}
for i in the edges
for j in range(n):
if i
General Clique
def count(n): return n * (n-1) def clique(n): print "in a clique..." for j in range(n): for i in range(j): print i, "is friends with", j
product is divisible by 5.
361 636 277 129 434 577 796 596 727 566
156 109 714 716 546 979 366 766 137 243
331 999 922 304 657 314 634 303 677 597
363 174 431 193 361 677 403 926 279 692
749 401 346 202 763 314 333 244 796 697
674 651 517 349 337 667 617 464 379 793
542 464 962 146 946 199 302 699 606 126
519 203 137 517 146 724 696 699 747 663
126 247 469 953 396 502 562 647 364 214
346 646 331 426 763 291 557 764 939 656
753 561 797 224 537 361 263 493 196 162
362 102 629 936 663 279 966 241 907 677
945 416 122 563 667 394 654 592 977 177
666 199 463 561 954 924 991 363 754 754
199 451 796 566 629 651 517 167 704 749
622 299 466 559 973 243 639 276 603 753
def make_link(G, node1, node2):
if node1 not in G:
G[node1] = {}
(G[node1])[node2] = 1
if node2 not in G:
G[node2] = {}
(G[node2])[node2] = 1
return G
a_ring = {}
n = 5
for i in range(n):
make_link(a_ring, i, (i+1)%n)
print len(a_ring)
print sum(len(a_ring[node]) for node in a_ring.keys())/2
print a_ring
import math
def make_link(G, node1, node2):
if node1 not in G:
G[node1] = {}
(G[node1])[node2] = 1
if node2 not in G:
G[node2] = {}
(G[node2])[node1] = 1
return G
G = {}
n = 256
side = int(math.sqrt(n))
for i in range(side):
for j in range(side):
if i < side-1: make_link(G, (i,j), (i+1, j))
if j < side-1: make_link(G, (i,j), (i, j+1))
print len(G)
print sum([len(G[node]) for node in G.keys()])/2
Create a Graph with an Eulerian Tour
def create_tour(nodes):
tour = []
l = len(nodes)
for i in range(l):
t = edge(nodes[i], nodes[(i+1) % l])
tour.append(t)
return []
def get_degree(tour):
degree = {}
for x, y in tour:
degree[x] = degree.get(x, 0) + 1
degree[y] = degree.get(y, 0) + 1
return degree
def check_edge(t, b, nodes):
if t[0] == b:
if t[1] not in nodes:
return t[1]
elif t[1] == b:
if t[0] not in nodes:
return t[0]
return None
def connected_nodes(tour):
a = tour[0][0]
nodes = set([a])
explor = set([a])
while len(explor) > 0:
b = explore.pop()
for t in tour:
node = check_edge(t, b, nodes)
if node is None:
continue
nodes.add(node)
explor.add(node)
return nodes
def is_eulerian_tour(nodes, tour):
degree = get_degree(tour)
for node in nodes:
try:
d = degree[node]
if d % 2 == 1:
print "Node %s has odd degree" % node
return False
except KeyError:
print "Node %s was not in your tour" % node
return False
connected = connected_nodes(tour)
if len(connected) == len(nodes):
return True
else:
print "Your graph wasn't connected"
return False
def test():
nodes = [20, 21, 22, 23, 24, 25]
tour = create_tour(nodes)
return is_eulerian_tour(nodes, tour)