Notes

week 1
write a program to implement BFS traversal

from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def addEdge(self,u,v):
self.graph[u].append(v)
self.visited=[]
def BFS(self, s):
queue = []
queue.append(s)
self.visited.append(s)

while queue:
# Dequeue a vertex from
# queue and print it
s = queue.pop(0)
print (s, end = " ")
for i in self.graph[s]:
if i not in visited:
queue.append(i)
self.visited.append(s)

g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
print ("Following is Breadth First Traversal"
" (starting from vertex 2)")
g.BFS(2)

week 2
write a program to implement DFS traversal

from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def addEdge(self, u, v):
self.graph[u].append(v)
def DFSUtil(self, v, visited):
visited.add(v)
print(v, end=' ')
for neighbour in self.graph[v]:
if neighbour not in visited:
self.DFSUtil(neighbour, visited)
def DFS(self, v):
visited = set()
self.DFSUtil(v, visited)
if __name__ == "__main__":
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
print("Following is Depth First Traversal (starting from vertex 2)")
g.DFS(2)

week 3
write a program to implement A* Search

def aStarAlgo(start_node, stop_node):
open_set = set(start_node)
closed_set = set()
g = {}
parents = {}
g[start_node] = 0
parents[start_node] = start_node
while len(open_set) > 0:
n = None
#node with lowest f() is found
for v in open_set:
if n == None or g[v] + heuristic(v) < g[n] + heuristic(n):
n = v
if n == stop_node or Graph_nodes[n] == None:
pass
else:
for (m, weight) in get_neighbors(n):
if m not in open_set and m not in closed_set:
open_set.add(m)
parents[m] = n
g[m] = g[n] + weight
else:
if g[m] > g[n] + weight:
#update g(m)
g[m] = g[n] + weight
#change parent of m to n
parents[m] = n
#if m in closed set,remove and add to open
if m in closed_set:
closed_set.remove(m)
open_set.add(m)
if n == None:
print('Path does not exist!')
return None
if n == stop_node:
path = []
while parents[n] != n:
path.append(n)
n = parents[n]
path.append(start_node)
path.reverse()
print('Path found: {}'.format(path))
return path
open_set.remove(n)
closed_set.add(n)
print('Path does not exist!')
return None
def get_neighbors(v):
if v in Graph_nodes:
return Graph_nodes[v]
else:
return None
def heuristic(n):
H_dist = {
'A': 11,
'B': 6,
'C': 5,
'D': 7,
'E': 3,
'F': 6,
'G': 5,
'H': 3,
'I': 1,
'J': 0
}
return H_dist[n]
Graph_nodes = {
'A': [('B', 6), ('F', 3)],
'B': [('A', 6), ('C', 3), ('D', 2)],
'C': [('B', 3), ('D', 1), ('E', 5)],
'D': [('B', 2), ('C', 1), ('E', 8)],
'E': [('C', 5), ('D', 8), ('I', 5), ('J', 5)],
'F': [('A', 3), ('G', 1), ('H', 7)],
'G': [('F', 1), ('I', 3)],
'H': [('F', 7), ('I', 2)],
'I': [('E', 5), ('G', 3), ('H', 2), ('J', 3)],
}

aStarAlgo('A', 'J')

week4
write a program to implement travelling salesman problem

from sys import maxsize
from itertools import permutations
V = 4
def travellingSalesmanProblem(graph, s):
vertex = []
for i in range(V):
if i != s:
vertex.append(i)
min_path = maxsize
next_permutation=permutations(vertex)
for i in next_permutation:
current_pathweight = 0
k = s
for j in i:
current_pathweight += graph[k][j]
k = j
current_pathweight += graph[k][s]
min_path = min(min_path, current_pathweight)
return min_path
if __name__ == "__main__":
graph = [[0, 10, 15, 20], [10, 0, 35, 25],
[15, 35, 0, 30], [20, 25, 30, 0]]
s = 0
print(travellingSalesmanProblem(graph, s))


week 5
write a program to implement graph colouring problem

colors = ['Red', 'Blue', 'Green', 'Yellow', 'Black']
states = ['Andhra', 'Karnataka', 'TamilNadu', 'Kerala']
neighbors = {}
neighbors['Andhra'] = ['Karnataka', 'TamilNadu']
neighbors['Karnataka'] = ['Andhra', 'TamilNadu', 'Kerala']
neighbors['TamilNadu'] = ['Andhra', 'Karnataka', 'Kerala']
neighbors['Kerala'] = ['Karnataka', 'TamilNadu']
colors_of_states = {}
def promising(state, color):
for neighbor in neighbors.get(state):
color_of_neighbor = colors_of_states.get(neighbor)
if color_of_neighbor == color:
return False
return True
def get_color_for_state(state):
for color in colors:
if promising(state, color):
return color

def main():
for state in states:
colors_of_states[state] = get_color_for_state(state)
print(colors_of_states)
main()

week 6
write a program to implement missionaries and cannibals problem

def is_valid(state):
m1, c1, b, m2, c2 = state
return 0 <= m1 <= 3 and 0 <= c1 <= 3 and 0 <= m2 <=3 and 0 <= c2 <= 3 and ((m1 == 0 or m1 >= c1) and(m2 == 0 or m2 >= c2))
def generate_next_states(state):
m1, c1, b, m2, c2 = state
moves = [ (1, 0), (2, 0), (0, 1), (0, 2), (1, 1)]
next_states = []
for dm, dc in moves:
if b == 1:
new_state = (m1 - dm, c1 - dc, 0, m2 + dm, c2 + dc)
else:
new_state = (m1 + dm, c1 + dc, 1, m2 - dm, c2 - dc)
if is_valid(new_state):
next_states.append(new_state)

return next_states

def solve_bfs(start_state):
queue = [(start_state, [start_state])]
while queue:
current_state, path = queue.pop(0)
if current_state == (0, 0, 0, 3, 3):
return path
for next_state in generate_next_states(current_state):
if next_state not in path:
queue.append((next_state, path + [next_state]))
return None
start_state = (3, 3, 1, 0, 0)
solution = solve_bfs(start_state)
if solution:
a=0
print("Solution path:")
for state in solution:
m1, c1, b, m2, c2 = state
print(f"{m1} missionaries, {c1} canniballs, {'boat on left' if b==1 else 'boat on right'}, {m2} missionaries, {c2} canniballs")
a=a + 1
print("total cost is ", a)
else:
print("no solution found")

week 7
write a program to implement water jug problem

from collections import defaultdict
jug1, jug2, aim = 4, 3, 2
visited = defaultdict(lambda: False)
def waterJugSolver(amt1, amt2):
if (amt1 == aim and amt2 == 0) or (amt2 == aim and amt1 == 0):
print(amt1, amt2)
return True
if visited[(amt1, amt2)] == False:
print(amt1, amt2)
visited[(amt1, amt2)] = True
return (waterJugSolver(0, amt2) or
waterJugSolver(amt1, 0) or
waterJugSolver(jug1, amt2) or
waterJugSolver(amt1, jug2) or
waterJugSolver(amt1 + min(amt2, (jug1-amt1)),
amt2 - min(amt2, (jug1-amt1))) or
waterJugSolver(amt1 - min(amt1, (jug2-amt2)),
amt2 + min(amt1, (jug2-amt2))))
else:
return False

print("Steps: ")
waterJugSolver(0, 0)

week 8
write a program to implement hangman game

import random
name = input("What is your name? ")
print("Good Luck ! ", name)
words = ['rainbow', 'computer', 'science', 'programming',
'python', 'mathematics', 'player', 'condition',
'reverse', 'water', 'board', 'geeks']
word = random.choice(words)
print("Guess the characters")
guesses = ''
turns = 12

while turns > 0:
failed = 0
for char in word:
if char in guesses:
print(char, end=" ")
else:
print("_")
failed += 1
if failed == 0:
print("You Win")
print("The word is: ", word)
break
print()
guess = input("guess a character:")
guesses += guess
if guess not in word:
turns -= 1
print("Wrong")
print("You have", + turns, 'more guesses')
if turns == 0:
print("You Loose")

week9
write a program to implement tic-tac-toe game

import os
import time

board = [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']
player = 1
Win = 1
Draw = -1
Running = 0
Stop = 1

Game = Running
Mark = 'X'
def DrawBoard():
print(" %c | %c | %c " % (board[1], board[2], board[3]))
print("___|___|___")
print(" %c | %c | %c " % (board[4], board[5], board[6]))
print("___|___|___")
print(" %c | %c | %c " % (board[7], board[8], board[9]))
print(" | | ")
def CheckPosition(x):
if board[x] == ' ':
return True
else:
return False
def CheckWin():
global Game
if board[1] == board[2] and board[2] == board[3] and board[1] != ' ':
Game = Win
elif board[4] == board[5] and board[5] == board[6] and board[4] != ' ':
Game = Win
elif board[7] == board[8] and board[8] == board[9] and board[7] != ' ':
Game = Win
elif board[1] == board[4] and board[4] == board[7] and board[1] != ' ':
Game = Win
elif board[2] == board[5] and board[5] == board[8] and board[2] != ' ':
Game = Win
elif board[3] == board[6] and board[6] == board[9] and board[3] != ' ':
Game = Win
elif board[1] == board[5] and board[5] == board[9] and board[5] != ' ':
Game = Win
elif board[3] == board[5] and board[5] == board[7] and board[5] != ' ':
Game = Win
elif board[1] != ' ' and board[2] != ' ' and board[3] != ' ' and
board[4] != ' ' and board[5] != ' ' and board[6] != ' ' and
board[7] != ' ' and board[8] != ' ' and board[9] != ' ':
Game = Draw
else:
Game = Running
print("Tic-Tac-Toe Game Designed By Sourabh Somani")
print("Player 1 [X] --- Player 2 [O]n")
print()
print()
print("Please Wait...")
time.sleep(3)
while Game == Running:
os.system('cls')
DrawBoard()
if player % 2 != 0:
print("Player 1's chance")
Mark = 'X'
else:
print("Player 2's chance")
Mark = 'O'
choice = int(input("Enter the position between [1-9] where you want to mark: "))
if CheckPosition(choice):
board[choice] = Mark
player += 1
CheckWin()
os.system('cls')
DrawBoard()
if Game == Draw:
print("Game Draw")
elif Game == Win:
player -= 1
if player % 2 != 0:
print("Player 1 Won")
else:
print("Player 2 Won")

week 10
write a program to implement 8 queens problem

print ("Enter the number of queens")
N = int(input())
board = [[0]*N for _ in range(N)]

def attack(i, j):
for k in range(0,N):
if board[i][k]==1 or board[k][j]==1:
return True
for k in range(0,N):
for l in range(0,N):
if (k+l==i+j) or (k-l==i-j):
if board[k][l]==1:
return True
return False

def N_queens(n):
if n==0:
return True
for i in range(0,N):
for j in range(0,N):
if (not(attack(i,j))) and (board[i][j]!=1):
board[i][j] = 1
if N_queens(n-1)==True:
return True
board[i][j] = 0

return False
N_queens(N)
for i in board:
print (i)

week11
write a program to implement bayesian Network

import math
from pomegranate import *
guest =DiscreteDistribution( { 'A': 1/3, 'B': 1/3, 'C': 1/3 } )
prize =DiscreteDistribution( { 'A': 1/3, 'B': 1/3, 'C': 1/3 } )
monty =ConditionalProbabilityTable(
[[ 'A', 'A', 'A', 0.0 ],
[ 'A', 'A', 'B', 0.5 ],
[ 'A', 'A', 'C', 0.5 ],
[ 'A', 'B', 'A', 0.0 ],
[ 'A', 'B', 'B', 0.0 ],
[ 'A', 'B', 'C', 1.0 ],
[ 'A', 'C', 'A', 0.0 ],
[ 'A', 'C', 'B', 1.0 ],
[ 'A', 'C', 'C', 0.0 ],
[ 'B', 'A', 'A', 0.0 ],
[ 'B', 'A', 'B', 0.0 ],
[ 'B', 'A', 'C', 1.0 ],
[ 'B', 'B', 'A', 0.5 ],
[ 'B', 'B', 'B', 0.0 ],
[ 'B', 'B', 'C', 0.5 ],
[ 'B', 'C', 'A', 1.0 ],
[ 'B', 'C', 'B', 0.0 ],
[ 'B', 'C', 'C', 0.0 ],
[ 'C', 'A', 'A', 0.0 ],
[ 'C', 'A', 'B', 1.0 ],
[ 'C', 'A', 'C', 0.0 ],
[ 'C', 'B', 'A', 1.0 ],
[ 'C', 'B', 'B', 0.0 ],
[ 'C', 'B', 'C', 0.0 ],
[ 'C', 'C', 'A', 0.5 ],
[ 'C', 'C', 'B', 0.5 ],
[ 'C', 'C', 'C', 0.0 ]], [guest, prize] )

d1 = State( guest, name="guest" )
d2 = State( prize, name="prize" )
d3 = State( monty, name="monty" )

#Building the Bayesian Network
network = BayesianNetwork( "Solving the Monty Hall Problem With Bayesian Networks" )
network.add_states(d1, d2, d3)
network.add_edge(d1, d3)
network.add_edge(d2, d3)
network.bake()
print(model.probability([['B','B','C'],['A','A','C'],['A','C','B'],['A','B','B']]))
print(model.predict([['A',None,'C'],['A','A',None],[None,'B','B'],['A',None,'B']]))

week 12
write a program to implement hidden markov model

import numpy as np
import itertools
import pandas as pd
states = ['sleeping', 'eating', 'walking']

hidden_states = ['healthy', 'sick']
pi = [0.5, 0.5]
state_space = pd.Series(pi, index=hidden_states, name='states')
print(state_space)
a_df = pd.DataFrame(columns=hidden_states, index=hidden_states)
a_df.loc[hidden_states[0]] = [0.7, 0.3]
a_df.loc[hidden_states[1]] = [0.4, 0.6]
print(a_df)
observable_states = states
b_df = pd.DataFrame(columns=observable_states, index=hidden_states)
b_df.loc[hidden_states[0]] = [0.2, 0.6, 0.2]
b_df.loc[hidden_states[1]] = [0.4, 0.1, 0.5]
print(b_df)
def HMM(obsq,b_df,a_df,pi,states,hidden_states):
hidst=list(itertools.combinations_with_replacement(hidden_states,len(obsq)))
sum=0
for k in hidst:
prod=1
for j in range(len(k)):
for i in obsq:
c=0
if c==0:
prod*=b_df[i][k[j]]*pi[hidden_states.index(k[j])]
c=1
else:
prod*=a_df[k[j]][k[j-1]]*b_df[i][k[j]]
sum+=prod
c=0
return sum

def vertibi(obsq,b_df,a_df,pi,states,hidden_states):
sum=0
hidst=list(itertools.combinations_with_replacement(hidden_states,len(obsq)))
for k in hidst:
sum1=0
prod=1
for j in range(len(k)):
for i in obsq:
c=0
if c==0:
prod*=b_df[i][k[j]]*pi[hidden_states.index(k[j])]
c=1
else:
prod*=a_df[k[j]][k[j-1]]*b_df[i][k[j]]
c=0
sum1+=prod
if(sum1>sum):
sum=sum1
hs=k
return sum,hs