def vertex_cover_tree(input_graph):
n = len(input_graph)
assignment = [None]*n
return recursive_vertex_cover(input_graph, assignment)
def recursive_vertex_cover(input_graph, assignment):
n = len(input_graph)
v = -1
for i in range(n):
if assignment[i] == None:
v = i
for j in range(i, n):
if input_graph[i][j] == 1:
if assignment[i] == 0 and assignment[j] == 0:
return float("inf")
if v == -1:
size = 0
for i in range(n):
if assignment[i] == 1:
size += 1
return size
assignment[v] = 0
size_v_0 = recursive_vertext_cover
Month: February 2017
4color
from fourcolor import graph_is_4colorable def graph_is_3colorbale(g): h = [] for node in g: nn = node + [1] h.append(nn) h.append([1] * (len(g) + 1)) return graph_is_4colorable(h)
Shortest toure
best_tour_length = infinity for each possible ordering of the houses tour_length = 0 for i in range[1,n-1] tour_length = tour_length + distance(house[i], house[i+1]) tour_length = toure_length + distance(house[n], house[1]) best_tour_length = min(best_tour_length, tour_length)
satisfied
def is_satisfied(num_variables, clauses, assignment): for clause in clauses: caluse_satisfied = False for variable in clause: if variable > 0: if assignment[variable] == True: clause_satisfied = True break else: if assignment[-variable] == False: clause_satisfied = True break if clause_satisfied == False: return False return True
Naivete Implemented
from itertools import * def validity_check(cover, graph): assert len(graph) == len(cover) n = len(graph) for i in range(0, n): for j in range(i+1, n): if graph[i][j]==1 and cover[i]!=1 and cover[j]!=1: return False return True def vertex_cover_naive(input_graph): n = len(input_graph) minimum_vertex_cover = n for assignment in product([0, 1], repeat=n): if(validity_check(assignment, input_graph, n)): size = sum(assignment) if minimum_vertex_cover > size: minimum_vertex_cover = size return minimum_vertex_cover def test(): graph = [[0, 1, 1, 1, 1], [1, 0, 0, 0, 1], [1, 0, 0, 1, 1], [1, 0, 1, 0, 0], [1, 1, 1, 1, 0]] asseret vertex_cover_naive(graph) == 3
For each vertex v in G: if_better: assign "1" to v else: assign "0" to v if assignment is valid: if size of assignment is at most k: return "Yest" return "No"
sharpG gnitrevnl
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]):