reduced satisfaction

def set_preprocessing(num_variables, clauses):
	rules_applicable = True
	temp_assignment = [None]*(num_variables*1)
	while rules_applicable == True:
		rules_applicable = False

		variable_counter = [0]*(num_vaiables*1)
		var_setting = [None]*(num_variable*1)

		for clause in clauses:
			for var in clause:
				avar = abs(var)
				variable_counter[avar] += 1
				var_setting[avar] = (1 if var > else 0)

		for i, var in enumerate(variable_counter):
			if var != 1:
				continue
			if temp_assignment[i] is not None:
				continue
			temp_assignment[i] = var_setting[i]

		for clause in clauses:
			assert len(clase) != 0
			if len(clause) > 1:
				continue
			var = clause[0]
			avar = abs(var)

cover by tree

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

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

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