Using CSV Module

import os
import pprint
import csv

DATADIR = ""
DATAFILE = "beatles-diskography.csv"

def parse_csv(datafile):
	data = []
	n = 0
	with open(datafile,'rb') as sd:
		r = csv.DictReader(sd)
		for line in r:
			data.append(line)
	return data

if __name__ == '__main__':
	datafile = os.path.join(DATADIR, DATAFILE)
	parse_scv(datafile)
	d = parse_csv(datafile)
	pprint.pprint(d)

Parsing CSV Files

import os

DATADIR = ""
DATAFILE = "beatles-diskography.csv"


def parse_file(datafile):
    data = []
    with open(datafile, "r") as f:
    	header = f.readline().split(",")
    	counter = 0
        for line in f:
            if counter == 10:
            	break

            fields = line.split(",")
            entry = {}

            for i, value in enumerate(fields):
            	entry[header[i].strip()] = value.strip()

            data.append(entry)
            counter += 1

    return data


def test():
    # a simple test of your implemetation
    datafile = os.path.join(DATADIR, DATAFILE)
    d = parse_file(datafile)
    firstline = {'Title': 'Please Please Me', 'UK Chart Position': '1', 'Label': 'Parlophone(UK)', 'Released': '22 March 1963', 'US Chart Position': '-', 'RIAA Certification': 'Platinum', 'BPI Certification': 'Gold'}
    tenthline = {'Title': '', 'UK Chart Position': '1', 'Label': 'Parlophone(UK)', 'Released': '10 July 1964', 'US Chart Position': '-', 'RIAA Certification': '', 'BPI Certification': 'Gold'}

    assert d[0] == firstline
    assert d[9] == tenthline

Title,Released,Label,UK Chart Position,US Chart Position,BPI Certification,RIAA Certification
Please Please Me,22 March 1963,Parlophone(UK),1,-,Gold,Platinum
With the Beatles,22 November 1963,Parlophone(UK),1,-,Platinum,Gold
Beatlemania! With the Beatles,25 November 1963,Capitol(CAN),-,-,,
Introducing... The Beatles,10 January 1964,Vee-Jay(US),-,2,,
Meet the Beatles!,20 January 1964,Capitol(US),-,1,,5xPlatinum
Twist and Shout,3 February 1964,Capitol(CAN),-,-,,
The Beatles' Second Album,10 April 1964,Capitol(US),-,1,,2xPlatinum
The Beatles' Long Tall Sally,11 May 1964,Capitol(CAN),-,-,,
A Hard Day's Night,26 June 1964,United Artists(US)c,-,1,,4xPlatinum
,10 July 1964,Parlophone(UK),1,-,Gold,
Something New,20 July 1964,Capitol(US),-,2,,Platinum
Beatles for Sale,4 December 1964,Parlophone(UK),1,-,Gold,Platinum
Beatles '65,15 December 1964,Capitol(US),-,1,,3xPlatinum
Beatles VI,14 June 1965,"Parlophone(NZ), Capitol(US)",-,1,,Platinum
Help!,6 August 1965,Parlophone(UK),1,-,Platinum,
,13 August 1965,Capitol(US) c,-,1,,3xPlatinum
Rubber Soul,3 December 1965,Parlophone(UK),1,-,Platinum,
,6 December 1965,Capitol(US) c ,-,1,,6xPlatinum
Yesterday and Today,15 June 1966,Capitol(US),-,1,,2xPlatinum
Revolver,5 August 1966,Parlophone(UK),1,-,Platinum,
,8 August 1966,Capitol(US) c,-,1,,5xPlatinum
Sgt. Pepper's Lonely Hearts Club Band,1 June 1967,"Parlophone(UK), Capitol(US)",1,1,3xPlatinum,11xPlatinum
Magical Mystery Tour,27 November 1967,"Parlophone(UK), Capitol(US)",31[D],1,Platinum,6xPlatinum
The Beatles,22 November 1968,"Apple(UK), Capitol(US)",1,1,Platinum,19xPlatinum
Yellow Submarine,13 January 1969,"Apple(UK), Capitol(US)",3,2,Silver,Platinum
Abbey Road,26 September 1969,"Apple(UK), Capitol(US)",1,1,2xPlatinum,12xPlatinum
Let It Be,8 May 1970,"Apple(UK),United Artists(US)",1,1,Gold,4xPlatinum

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