Computational Algorithms in Python Homework Sample

Given a list of numbers, is there a number that is the sum of 2 other values? Complete the code in DFS to perform a depth first search. Write another version of the DFS using a stack, use the deque append and pop to implement the stack. Check if a graph is bipartite (there are 2 separate graphs where it is not possible to get from one node on one side to a node on the other side). For more Python programming assignments contact us.

Solution:

SumFree.py

# Candidate number:

# Test if a list A of integers is sum free
# Your code should co here
def SumFree(a):
# make alist of sum of all pairs
d=[x + y for i, x in enumerate(a) for y in a[i+1:]]
return (common_data(a,d))
#check if element of list exist in another list
def common_data(list1, list2):
result = False

# traverse in the 1st list
for x in list1:

# traverse in the 2nd list
for y in list2:

# if one common
if x == y:
result = True
return result

return result
if __name__ == ‘__main__’:
c = [6, 7, 8, 9,10]
print(SumFree(c))
m=[2,3,4,7,10]
print(SumFree(m))

a = [1, 2, 3, 4, 5]

# printing the list using loop
for x in range(len(a)):
print (a[x])

# Test if a list A of increasing integers between 1 and 10 is sum free
# Your code should go here
DFS.py

# Candidate number:

from collections import deque
from Graph import Graph

# Depth-first search (recursive, as presented in the lecture)
# Your code should go here
def dfs(graph, node):
global time
time=0
visited = [node]
stack = [node]
while stack:
node = stack[-1]
if node not in visited:
visited.extend(node)
remove_from_stack = True
for next in graph.V:
time=time+1
graph.f=time
if next not in visited:
stack.extend(next)
remove_from_stack = False
break
if remove_from_stack:
stack.pop()
# Display result of DFS
def display(G):
for v in G.V:
s = str(v.id) + “: ” + str(v.d) + ” ” + str(v.f)
print s

if __name__ == ‘__main__’:

# Road network example from the lecture
G = Graph()
# Create vertices
for i in range(0,27):
G.add_node()
# Create horizontal edges
G.add_edge_using_ids(0,1)
G.add_edge_using_ids(1,2)
G.add_edge_using_ids(2,3)
G.add_edge_using_ids(3,4)
G.add_edge_using_ids(4,5)
G.add_edge_using_ids(6,7)
G.add_edge_using_ids(7,8)
G.add_edge_using_ids(9,10)
G.add_edge_using_ids(10,11)
G.add_edge_using_ids(11,12)
G.add_edge_using_ids(13,14)
G.add_edge_using_ids(14,15)
G.add_edge_using_ids(16,17)
G.add_edge_using_ids(18,19)
G.add_edge_using_ids(19,20)
G.add_edge_using_ids(21,22)
G.add_edge_using_ids(22,23)
G.add_edge_using_ids(24,25)
# Create vertical edges
G.add_edge_using_ids(2,6)
G.add_edge_using_ids(3,7)
G.add_edge_using_ids(4,8)
G.add_edge_using_ids(6,9)
G.add_edge_using_ids(7,10)
G.add_edge_using_ids(8,11)
G.add_edge_using_ids(9,13)
G.add_edge_using_ids(10,14)
G.add_edge_using_ids(11,15)
G.add_edge_using_ids(12,16)
G.add_edge_using_ids(14,18)
G.add_edge_using_ids(15,19)
G.add_edge_using_ids(16,20)
G.add_edge_using_ids(18,21)
G.add_edge_using_ids(19,22)
G.add_edge_using_ids(20,23)
G.add_edge_using_ids(21,24)
G.add_edge_using_ids(22,25)
G.add_edge_using_ids(25,26)

print “Road network example from the lecture”
print “The graph:”
G.display()

# Uncomment this line once you implemented the algorithm
dfs(G,4)

print “Discovery and finishing times:”
display(G)

print “”

# DFS example from the lecture
H = Graph()
for i in range(0,9):
H.add_node()
H.add_directed_edge_using_ids(0,1)
H.add_directed_edge_using_ids(1,2)
H.add_directed_edge_using_ids(0,3)
H.add_directed_edge_using_ids(0,4)
H.add_directed_edge_using_ids(1,4)
H.add_directed_edge_using_ids(3,7)
H.add_directed_edge_using_ids(3,6)
H.add_directed_edge_using_ids(4,7)
H.add_directed_edge_using_ids(5,8)

print “DFS example from the lecture”
print “The graph:”
H.display()

# Uncomment this line once you implemented the algorithm
#DFS(H)

print “Discovery and finishing times:”
display(H)

Bipartite.py

# Candidate number:

from collections import deque
# Explain IF Graph is Bipartite or not
class Graph():

def __init__(self, v):
self.V = v
self.graph = [[0 for column in range(v)]
for row in range(v)]

self.ColorArr = [-1 for i in range(self.V)]

# This function returns true if Graph G[U][V]
# is bipartite, else False
def isBipartite_Util(self, source):

# Create a color array to store colors
# assigned to all Veritces. Vertex
# Number is used as Index in this array.
# The Value ‘-1’ of Self.ColorArr[i] is used
# to indicate that no Color is assigned to
# Vertex ‘i’. The Value 1 is used to indicate
# First Color is Assigned and Value 0
# Indicates Second Color is assigned.

# Assign First Color to Source

# Create a Queue (LILO) of Vertex Numbers and
# Enqueue Source Vertex For BFS Traversal
Queue = []
Queue.append(source)

# Run While there are Vertices in Queue
while Queue:

u = Queue.pop()

# Return False if there is a Self-Loop
if self.graph[u][u] == 1:
return False;

for v in range(self.V):

# An Edge from U to V Exists
if (self.graph[u][v] == 1 and
self.ColorArr[v] == -1):

# Assign Alternate Color to
# This Adjacent V of U
self.ColorArr[v] = 1 – self.ColorArr[u]
Queue.append(v)

# An Edge from U to V Exists and Destination
# V is Colored with Same Color as U
elif (self.graph[u][v] == 1 and
self.ColorArr[v] == self.ColorArr[u]):
return False
# Vertices Can be Colored with Alternate Color
return True

def isBipartite(self):
self.ColorArr = [-1 for i in range(self.V)]
for i in range(self.V):
if self.ColorArr[i] == -1:
if not self.isBipartite_Util(i):
return False
return True

if __name__ == ‘__main__’:
g = Graph(4)
g.graph = [[1, 0, 0, 1],
[0, 0, 1, 1],
[1, 1, 0, 0],
[0, 0, 1, 1]]
print (“yes” if g.isBipartite() else “no”)