P1
1. Implement depth first search algorithm and Breadth First Search algorithm, Use an
undirected graph and develop a recursive algorithm for searching all the vertices of a
graph or tree data structure.
class Node:
def __init__(self, x):
self.data = x
self.left = None
self.right = None
def recursive_bfs(root, goal_node):
if not root:
return False
queue = [root]
while queue:
current = queue.pop(0)
print(current.data, end=" ")
if current.data == goal_node:
return True
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
return False
def recursive_dfs(node, goal_node):
if not node:
return False
print(node.data, end=" ")
if node.data == goal_node:
return True
left_found = recursive_dfs(node.left, goal_node)
right_found = recursive_dfs(node.right, goal_node)
return left_found or right_found
if __name__ == "__main__":
root_data = int(input("Enter the data for the root node: "))
root = Node(root_data)
queue = [root]
while queue:
current = queue.pop(0)
left_data = int(input(f"Enter the left child data of {current.data} (enter -1 for no left child): "))
if left_data != -1:
current.left = Node(left_data)
queue.append(current.left)
right_data = int(input(f"Enter the right child data of {current.data} (enter -1 for no right child):
"))
if right_data != -1:
current.right = Node(right_data)
queue.append(current.right)
goal_node = int(input("Enter the goal node: "))
print("\nBFS Traversal:")
if recursive_bfs(root, goal_node):
print(f"\nGoal node {goal_node} found using BFS!")
else:
print(f"\nGoal node {goal_node} not found using BFS!")
print("\nDFS Traversal:")
if recursive_dfs(root, goal_node):
print(f"\nGoal node {goal_node} found using DFS!")
else:
print(f"\nGoal node {goal_node} not found using DFS!")
OUTPUT:
P2
1. Implement A star Algorithm for any game search problem.
class Node:
def __init__(self,data,level,fval):
""" Initialize the node with the data, level of the node and the calculated fvalue """
self.data = data
self.level = level
self.fval = fval
def generate_child(self):
""" Generate child nodes from the given node by moving the blank space
either in the four directions {up,down,left,right} """
x,y = self.find(self.data,'_')
""" val_list contains position values for moving the blank space in either of
the 4 directions [up,down,left,right] respectively. """
val_list = [[x,y-1],[x,y+1],[x-1,y],[x+1,y]]
children = []
for i in val_list:
child = self.shuffle(self.data,x,y,i[0],i[1])
if child is not None:
child_node = Node(child,self.level+1,0)
children.append(child_node)
return children
def shuffle(self,puz,x1,y1,x2,y2):
""" Move the blank space in the given direction and if the position value are out
of limits the return None """
if x2 >= 0 and x2 < len(self.data) and y2 >= 0 and y2 < len(self.data):
temp_puz = []
temp_puz = self.copy(puz)
temp = temp_puz[x2][y2]
temp_puz[x2][y2] = temp_puz[x1][y1]
temp_puz[x1][y1] = temp
return temp_puz
else:
return None
def copy(self,root):
""" Copy function to create a similar matrix of the given node"""
temp = []
for i in root:
t = []
for j in i:
t.append(j)
temp.append(t)
return temp
def find(self,puz,x):
""" Specifically used to find the position of the blank space """
for i in range(0,len(self.data)):
for j in range(0,len(self.data)):
if puz[i][j] == x:
return i,j
class Puzzle:
def __init__(self,size):
""" Initialize the puzzle size by the specified size,open and closed lists to empty """
self.n = size
self.open = []
self.closed = []
def accept(self):
""" Accepts the puzzle from the user """
puz = []
for i in range(0,self.n):
temp = input().split(" ")
puz.append(temp)
return puz
def f(self,start,goal):
""" Heuristic Function to calculate hueristic value f(x) = h(x) + g(x) """
return self.h(start.data,goal)+start.level
def h(self,start,goal):
""" Calculates the different between the given puzzles """
temp = 0
for i in range(0,self.n):
for j in range(0,self.n):
if start[i][j] != goal[i][j] and start[i][j] != '_':
temp += 1
return temp
def process(self):
""" Accept Start and Goal Puzzle state"""
print("Enter the start state matrix \n")
start = self.accept()
print("Enter the goal state matrix \n")
goal = self.accept()
start = Node(start,0,0)
start.fval = self.f(start,goal)
""" Put the start node in the open list"""
self.open.append(start)
print("\n\n")
while True:
cur = self.open[0]
print("")
print(" | ")
print(" | ")
print(" \\\'/ \n")
for i in cur.data:
for j in i:
print(j,end=" ")
print("")
""" If the difference between current and goal node is 0 we have reached the goal node"""
if(self.h(cur.data,goal) == 0):
break
for i in cur.generate_child():
i.fval = self.f(i,goal)
self.open.append(i)
self.closed.append(cur)
del self.open[0]
""" sort the opne list based on f value """
self.open.sort(key = lambda x:x.fval,reverse=False)
puz = Puzzle(3)
puz.process()
OUTPUT:
P3
1. Implement Greedy search algorithm for any of the following application:
#prims
INF = 9999999
# Take input for the number of vertices in the graph
V = int(input("Enter the number of vertices in the graph: "))
# Create an empty graph with all edges initially set to 0
G = [[0] * V for _ in range(V)]
# Take input for the adjacency matrix representing the graph
print("Enter the adjacency matrix (Enter edge (u v weight) - Enter 0 0 0 to finish):")
while True:
edge_input = input().split()
if edge_input == ['0', '0', '0']:
break
u, v, weight = map(int, edge_input)
G[u][v] = weight
G[v][u] = weight
# Create an array to track selected vertices
selected = [0] * V
# Set the number of edges to 0
no_edge = 0
# Choose the 0th vertex and make it true
selected[0] = True
# Print for edge and weight
print("\nEdge : Weight\n")
while no_edge < V - 1:
minimum = INF
x=0
y=0
for i in range(V):
if selected[i]:
for j in range(V):
if not selected[j] and G[i][j] and minimum > G[i][j]:
minimum = G[i][j]
x=i
y=j
print(f"{x}-{y}: {G[x][y]}")
selected[y] = True
no_edge += 1
OUTPUT:
#kruskal
class Graph:
def __init__(self, vertices):
self.vertices = vertices
self.edges = []
def add_edge(self, u, v, weight):
self.edges.append((u, v, weight))
def kruskal_mst(self):
self.edges = sorted(self.edges, key=lambda edge: edge[2])
parent = [i for i in range(self.vertices)]
rank = [0] * self.vertices
result = []
def find_set(vertex):
if parent[vertex] == vertex:
return vertex
parent[vertex] = find_set(parent[vertex])
return parent[vertex]
def union_sets(root1, root2):
if rank[root1] < rank[root2]:
parent[root1] = root2
elif rank[root1] > rank[root2]:
parent[root2] = root1
else:
parent[root1] = root2
rank[root2] += 1
for edge in self.edges:
u, v, weight = edge
root1 = find_set(u)
root2 = find_set(v)
if root1 != root2:
result.append(edge)
union_sets(root1, root2)
return result
# Take input for the number of vertices in the graph
V = int(input("Enter the number of vertices in the graph: "))
# Create a graph object
graph = Graph(V)
# Take input for the adjacency matrix representing the graph
print("Enter the edges (u v weight) - Enter 0 0 0 to finish:")
while True:
edge_input = input().split()
if edge_input == ['0', '0', '0']:
break
u, v, weight = map(int, edge_input)
graph.add_edge(u, v, weight)
# Find and print the Minimum Spanning Tree using Kruskal's algorithm
mst_edges = graph.kruskal_mst()
print("\nEdges of Minimum Spanning Tree:")
for edge in mst_edges:
u, v, weight = edge
print(f"{u}-{v}: {weight}")
OUTPUT:
#selectionsort
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
# Swap the found minimum element with the first element
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
# Take input from the user
try:
input_values = input("Enter a list of space-separated numbers: ").split()
unsorted_array = [int(value) for value in input_values]
except ValueError:
print("Invalid input. Please enter numbers separated by spaces.")
exit()
sorted_array = selection_sort(unsorted_array)
print("Sorted array:", sorted_array)
OUTPUT:
#dijkstra
class Graph:
def __init__(self):
self.graph = {}
def add_edge(self, u, v, weight):
if u not in self.graph:
self.graph[u] = []
if v not in self.graph:
self.graph[v] = []
self.graph[u].append((v, weight))
self.graph[v].append((u, weight)) # Assuming an undirected graph
def dijkstra(self, start):
priority_queue = [(0, start)] # (distance, vertex)
visited = set()
distances = {vertex: float('infinity') for vertex in self.graph}
distances[start] = 0
while priority_queue:
current_distance, current_vertex = self.pop_min(priority_queue)
if current_vertex in visited:
continue
visited.add(current_vertex)
for neighbor, weight in self.graph[current_vertex]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
self.insert(priority_queue, (distance, neighbor))
return distances
def pop_min(self, queue):
min_index = 0
for i in range(1, len(queue)):
if queue[i][0] < queue[min_index][0]:
min_index = i
return queue.pop(min_index)
def insert(self, queue, element):
queue.append(element)
def input_graph(self):
while True:
try:
u, v, weight = map(int, input("Enter an edge (u v weight), or enter 'done' to finish: ").split())
self.add_edge(u, v, weight)
except ValueError:
break
# Example usage:
g = Graph()
g.input_graph()
start_vertex = int(input("Enter the starting vertex for Dijkstra's algorithm: "))
shortest_distances = g.dijkstra(start_vertex)
print(f"Shortest distances from vertex {start_vertex}:")
for vertex, distance in shortest_distances.items():
print(f"To vertex {vertex}: {distance}")
OUTPUT:
#jobSequence
class Job:
def __init__(self, id, deadline, profit):
self.id = id
self.deadline = deadline
self.profit = profit
class Solution:
def jobScheduling(self, jobs):
jobs.sort(key=lambda x: x.profit, reverse=True)
maxi = jobs[0].deadline
for i in range(1, len(jobs)):
maxi = max(maxi, jobs[i].deadline)
slot = [-1] * (maxi + 1)
countJobs = 0
jobProfit = 0
for i in range(len(jobs)):
for j in range(jobs[i].deadline, 0, -1):
if slot[j] == -1:
slot[j] = i
countJobs += 1
jobProfit += jobs[i].profit
break
return countJobs, jobProfit
if __name__ == "__main__":
jobs = []
n = int(input("Enter the number of jobs: "))
for i in range(n):
id, deadline, profit = map(int, input(f"Enter details for job {i + 1} (id deadline profit): ").split())
jobs.append(Job(id, deadline, profit))
count, profit = Solution().jobScheduling(jobs)
print(f"Maximum number of jobs that can be scheduled: {count}")
print(f"Total profit: {profit}")
OUTPUT:
P4
1. Implement a solution for a Constraint Satisfaction Problem using Branch and Bound
and Backtracking for n-queens problem or a graph coloring problem.
def solveNQueens(n: int):
res = []
board = [['.' for _ in range(n)] for _ in range(n)]
def isSafe(row, col):
# check in column
for i in range(row):
if (board[i][col] == 'Q'):
return False
# check in positive diagonal
i = row
j = col
while (i >= 0 and j < n):
if (board[i][j] == 'Q'):
return False
i -= 1
j += 1
# check in negative diagonal
i = row
j = col
while (i >= 0 and j >= 0):
if (board[i][j] == 'Q'):
return False
i -= 1
j -= 1
return True
def backtrack(row):
if (row == n):
res.append([''.join(row) for row in board])
return False
for col in range(n):
if (isSafe(row, col)):
board[row][col] = 'Q'
possible = backtrack(row+1)
if (possible):
return True
board[row][col] = '.'
return False
backtrack(0)
return res
def printSolutions(boards):
for board in enumerate(boards):
print(f"Solution {board[0]+1}")
for row in board[1]:
for col in row:
print(col, end=' ')
print()
print()
if __name__ == "__main__":
n=int(input("enter no of queen:"))
boards = solveNQueens(n)
printSolutions(boards)
OUTPUT:
P5
1. Develop an elementary chatbot for any suitable customer interaction application.
bot_name = "Siriiiiii"
knowledge_base = {
"what is your name?": [
f"My name is {bot_name}! \n Happy to help you out with your College enquiries!"
],
"hello": [
f"Hello my name is {bot_name}! \n Happy to help you out with your College enquiries!"
],
"what are the best colleges from pune?": [
"COEP",
"PICT",
"VIT",
"CUMMINS",
"PCCOE"
],
"which are the best engineering branches?": [
"Computer Engineering",
"IT Engineering",
"ENTC Engineering"
],
"what are the top branch cut-offs for coep?": [
"Computer Engineering : 99.8 percentile",
"Does not have IT branch",
"ENTC Engineering: 99.2 percentile",
],
"what are the top branch cut-offs for pict?": [
"Computer Engineering : 99.4 percentile",
"IT Engineering : 98.6 percentile",
"ENTC Engineering: 97.2 percentile",
],
"what are the top branch cut-offs for vit?": [
"Computer Engineering : 99.8 percentile",
"IT Engineering: 97.1 percentile",
"ENTC Engineering: 96.2 percentile",
],
"what are the top branch cut-offs for cummins?": [
"Computer Engineering : 99.8 percentile",
"Does not have IT branch",
"ENTC Engineering: 99.2",
],
"what are the top branch cut-offs for pccoe?": [
"Computer Engineering : 99.8 percentile",
"Does not have IT branch",
"ENTC Engineering: 99.2",
],
"When do college admissions start?": [
"Admissions generally start around August",
],
}
def respond(input_str):
input_str = input_str.lower()
if input_str in knowledge_base:
values = knowledge_base[input_str]
for value in values:
print(value)
else:
print("Question is not present in the knowledge base!")
key = input_str
answer = input("Could you please enter the appropriate answer for the question
below?\nAnswer: ")
knowledge_base[key] = [answer]
print("Answer added!")
if __name__ == "__main__":
while True:
user_input = input("Enter a query here: ")
user_input = user_input.lower()
if user_input in ['exit', 'bye', 'quit']:
print("Thank you for using the Chatbot")
break
respond(user_input)
OUTPUT:
