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

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 += &#91;val&#93;
    	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 += &#91;val&#93;
    	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&#91;char2&#93;:
			if len(heap) < k:
				insert_heap(heap, (charG&#91;char1&#93;&#91;char2&#93;,(char1, char2)))
			elif charG&#91;char1&#93;&#91;char2&#93; > 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