[Date]

ASSIGNMENT IVth SEMESTER

SUBMITTED TO: MS. KOMAL SHARMA

SUBMITTED BY: Rohit mehra
1. Write a program to implement Breadth First and Depth First Search.
class Graph:
def __init__(self):
self.graph = {}

def add_edge(self, vertex, edge):

if vertex in self.graph:
self.graph[vertex].append(edge)
else:
self.graph[vertex] = [edge]

def bfs(self, start_vertex):

visited = []
queue = [start_vertex]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.append(vertex)
queue.extend(self.graph[vertex])
return visited

def dfs(self, start_vertex):

visited = []
stack = [start_vertex]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.append(vertex)
stack.extend(self.graph[vertex])
return visited

# Usage example
graph = Graph()
graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
graph.add_edge('B', 'D')
graph.add_edge('B', 'E')
graph.add_edge('C', 'F')

print("BFS:", graph.bfs('A'))
print("DFS:", graph.dfs('A'))
 2. Write a Program for the Best First Search and A* search algorithm.

from queue import PriorityQueue

class Graph:

def __init__(self):

self.graph = {}

def add_edge(self, vertex, edge, cost):

if vertex in self.graph:

self.graph[vertex].append((edge, cost))

else:

self.graph[vertex] = [(edge, cost)]

def best_first_search(self, start_vertex, goal_vertex):

visited = []

pq = PriorityQueue()

pq.put((0, start_vertex))

while not pq.empty():

cost, vertex = pq.get()

if vertex == goal_vertex:

visited.append(vertex)

break

if vertex not in visited:

visited.append(vertex)

for neighbor, neighbor_cost in self.graph[vertex]:

pq.put((neighbor_cost, neighbor))

return visited

def a_star_search(self, start_vertex, goal_vertex, heuristic):

visited = []

pq = PriorityQueue()
 pq.put((0 + heuristic[start_vertex], start_vertex))

while not pq.empty():

cost, vertex = pq.get()

if vertex == goal_vertex:

visited.append(vertex)

break

if vertex not in visited:

visited.append(vertex)

for neighbor, neighbor_cost in self.graph[vertex]:

pq.put((cost + neighbor_cost + heuristic[neighbor], neighbor))

return visited

# Usage example

graph = Graph()

graph.add_edge('A', 'B', 5)

graph.add_edge('A', 'C', 3)

graph.add_edge('B', 'D', 2)

graph.add_edge('B', 'E', 4)

graph.add_edge('C', 'F', 6)

heuristic = {'A': 10, 'B': 8, 'C': 5, 'D': 7, 'E': 6, 'F': 0}

print("Best First Search:", graph.best_first_search('A', 'F'))

print("A* Search:", graph.a_star_search('A', 'F', heuristic))

 3. Write a program to implement Water Jug Problem.

def water_jug_problem(capacity1, capacity2, target):

jug1 = 0

jug2 = 0

steps = []

while jug1 != target and jug2 != target:

if jug1 == 0:

jug1 = capacity1

steps.append((jug1, jug2))

elif jug2 == capacity2:

jug2 = 0

steps.append((jug1, jug2))

else:

amount = min(jug1, capacity2 - jug2)

jug1 -= amount

jug2 += amount

steps.append((jug1, jug2))

return steps

# Usage example

capacity1 = 5

capacity2 = 3

target = 4

steps = water_jug_problem(capacity1, capacity2, target)

for step in steps:

print(step)
 4. Write a program to implement 4-Queen Problem.

def is_safe(board, row, col):

for i in range(row):

if board[i] == col or \

board[i] - i == col - row or \

board[i] + i == col + row:

return False

return True

def solve_n_queens(n):

def backtrack(row):

if row == n:

solutions.append(list(board))

else:

for col in range(n):

if is_safe(board, row, col):

board[row] = col

backtrack(row + 1)

board = [-1] * n

solutions = []

backtrack(0)

return solutions

# Usage example

n=4

solutions = solve_n_queens(n)

for solution in solutions:

print(solution)
5. Write a program for Text Classification for the given sentence using NLTK.

import nltk

from nltk.corpus import stopwords

from nltk.tokenize import word_tokenize

from nltk.stem import WordNetLemmatizer

from sklearn.feature_extraction.text import TfidfVectorizer

from sklearn.model_selection import train_test_split

from sklearn.naive_bayes import MultinomialNB

nltk.download('punkt')

nltk.download('stopwords')

nltk.download('wordnet')

# Prepare dataset

sentences = [

"I love this movie",

"This movie is great",

"The acting in this movie is superb",

"I don't like this movie",

"The plot is confusing"

labels = ["positive", "positive", "positive", "negative", "negative"]

# Text preprocessing

stop_words = set(stopwords.words("english"))

lemmatizer = WordNetLemmatizer()

processed_sentences = []

for sentence in sentences:

# Tokenization

words = word_tokenize(sentence.lower())
 # Stop word removal and lemmatization

processed_words = [lemmatizer.lemmatize(word) for word in words if word not in stop_words]

processed_sentences.append(" ".join(processed_words))

# Feature extraction

vectorizer = TfidfVectorizer()

features = vectorizer.fit_transform(processed_sentences).toarray()

# Split dataset into train and test sets

X_train, X_test, y_train, y_test = train_test_split(features, labels, test_size=0.2,

random_state=42)

# Train a classifier

classifier = MultinomialNB()

classifier.fit(X_train, y_train)

# Predict on test set

predictions = classifier.predict(X_test)

# Evaluate the classifier

accuracy = (predictions == y_test).mean()

print("Accuracy:", accuracy)
 6. Write a program to implement hill climbing & steepest ascent hill climbing algorithm.

import random

def objective_function(x):

return x ** 2

def hill_climbing(initial_solution, objective_function):

current_solution = initial_solution

current_value = objective_function(current_solution)

while True:

neighbors = [current_solution - 1, current_solution + 1]

neighbor_values = [objective_function(neighbor) for neighbor in neighbors]

best_neighbor_value = min(neighbor_values)

if best_neighbor_value >= current_value:

return current_solution

else:

best_neighbor_index = neighbor_values.index(best_neighbor_value)

current_solution = neighbors[best_neighbor_index]

current_value = best_neighbor_value

def steepest_ascent_hill_climbing(initial_solution, objective_function):

current_solution = initial_solution

current_value = objective_function(current_solution)
 while True:

neighbors = [current_solution - 1, current_solution + 1]

neighbor_values = [objective_function(neighbor) for neighbor in neighbors]

best_neighbor_value = min(neighbor_values)

if best_neighbor_value > current_value:

return current_solution

elif best_neighbor_value == current_value:

best_neighbor_indices = [

i for i, value in enumerate(neighbor_values) if value == best_neighbor_value

best_neighbor_index = random.choice(best_neighbor_indices)

current_solution = neighbors[best_neighbor_index]

current_value = best_neighbor_value

else:

return current_solution

# Usage example

initial_solution = 3

optimal_solution_hill_climbing = hill_climbing(initial_solution, objective_function)

optimal_solution_steepest_ascent = steepest_ascent_hill_climbing(initial_solution,
objective_function)

print("Hill Climbing Optimal Solution:", optimal_solution_hill_climbing)

print("Steepest Ascent Hill Climbing Optimal Solution:", optimal_solution_steepest_ascent)

 7. Write a program to implement Travelling Salesman Problem.

import sys

def tsp(graph, start_vertex):

num_vertices = len(graph)

visited = [False] * num_vertices

visited[start_vertex] = True

path = [start_vertex]

min_cost = sys.maxsize

def backtrack(curr_vertex, curr_cost, num_visited):

nonlocal min_cost

if num_visited == num_vertices:

min_cost = min(min_cost, curr_cost + graph[curr_vertex][start_vertex])

return

for next_vertex in range(num_vertices):

if not visited[next_vertex]:

visited[next_vertex] = True

path.append(next_vertex)

backtrack(next_vertex, curr_cost + graph[curr_vertex][next_vertex], num_visited + 1)

visited[next_vertex] = False

path.pop()

backtrack(start_vertex, 0, 1)

return min_cost, path

# Usage example

graph = [

[0, 10, 15, 20],

[10, 0, 35, 25],

[15, 35, 0, 30],

[20, 25, 30, 0]

start_vertex = 0

min_cost, optimal_path = tsp(graph, start_vertex)

print("Minimum Cost:", min_cost)

print("Optimal Path:", optimal_path)

 8. Write a program to implement back propagation algorithm using ANN.

import numpy as np

class NeuralNetwork:

def __init__(self, input_size, hidden_size, output_size):

self.input_size = input_size

self.hidden_size = hidden_size

self.output_size = output_size

self.weights1 = np.random.randn(self.input_size, self.hidden_size)

self.bias1 = np.zeros((1, self.hidden_size))

self.weights2 = np.random.randn(self.hidden_size, self.output_size)

self.bias2 = np.zeros((1, self.output_size))

def forward(self, X):

self.z1 = np.dot(X, self.weights1) + self.bias1

self.a1 = self.sigmoid(self.z1)

self.z2 = np.dot(self.a1, self.weights2) + self.bias2

self.a2 = self.sigmoid(self.z2)

return self.a2

def backward(self, X, y, learning_rate):

m = X.shape[0]

self.dz2 = self.a2 - y

self.dw2 = np.dot(self.a1.T, self.dz2) / m

self.db2 = np.sum(self.dz2, axis=0, keepdims=True) / m

self.dz1 = np.dot(self.dz2, self.weights2.T) * self.sigmoid_derivative(self.z1)

self.dw1 = np.dot(X.T, self.dz1) / m

self.db1 = np.sum(self.dz1, axis=0, keepdims=True) / m

 self.weights2 -= learning_rate * self.dw2

self.bias2 -= learning_rate * self.db2

self.weights1 -= learning_rate * self.dw1

self.bias1 -= learning_rate * self.db1

def train(self, X, y, epochs, learning_rate):

for epoch in range(epochs):

output = self.forward(X)

self.backward(X, y, learning_rate)

if epoch % 1000 == 0:

loss = self.mean_squared_error(output, y)

print(f"Epoch {epoch}: Loss = {loss}")

def predict(self, X):

return self.forward(X)

@staticmethod

def sigmoid(x):

return 1 / (1 + np.exp(-x))

@staticmethod

def sigmoid_derivative(x):

return x * (1 - x)

@staticmethod

def mean_squared_error(y_pred, y_true):

return np.mean((y_pred - y_true) ** 2)

# Usage example

X = np.array([[0, 0], [0, 1], [1, 0], [1, 1]])

y = np.array([[0], [1], [1], [0]])

input_size = X.shape[1]

hidden_size = 4

output_size = y.shape[1]

nn = NeuralNetwork(input_size, hidden_size, output_size)

nn.train(X, y, epochs=10000, learning_rate=0.1)

predictions = nn.predict(X)

print("Predictions:", predictions)
 9. Write a program to implement Artificial Neural Network (ANN) for Classification using a
dataset.

import numpy as np

from sklearn.model_selection import train_test_split

# Artificial Neural Network (ANN) class

class NeuralNetwork:

def __init__(self, input_size, hidden_size, output_size):

self.input_size = input_size

self.hidden_size = hidden_size

self.output_size = output_size

self.weights1 = np.random.randn(self.input_size, self.hidden_size)

self.bias1 = np.zeros((1, self.hidden_size))

self.weights2 = np.random.randn(self.hidden_size, self.output_size)

self.bias2 = np.zeros((1, self.output_size))

def forward(self, X):

self.z1 = np.dot(X, self.weights1) + self.bias1

self.a1 = self.sigmoid(self.z1)

self.z2 = np.dot(self.a1, self.weights2) + self.bias2

self.a2 = self.softmax(self.z2)

return self.a2

def backward(self, X, y, learning_rate):

m = X.shape[0]

self.dz2 = self.a2 - y

self.dw2 = np.dot(self.a1.T, self.dz2) / m

self.db2 = np.sum(self.dz2, axis=0, keepdims=True) / m

self.dz1 = np.dot(self.dz2, self.weights2.T) * self.sigmoid_derivative(self.z1)

 self.dw1 = np.dot(X.T, self.dz1) / m

self.db1 = np.sum(self.dz1, axis=0, keepdims=True) / m

self.weights2 -= learning_rate * self.dw2

self.bias2 -= learning_rate * self.db2

self.weights1 -= learning_rate * self.dw1

self.bias1 -= learning_rate * self.db1

def train(self, X, y, epochs, learning_rate):

for epoch in range(epochs):

output = self.forward(X)

self.backward(X, y, learning_rate)

def predict(self, X):

return np.argmax(self.forward(X), axis=1)

@staticmethod

def sigmoid(x):

return 1 / (1 + np.exp(-x))

@staticmethod

def sigmoid_derivative(x):

return x * (1 - x)

@staticmethod

def softmax(x):

exp_scores = np.exp(x)

return exp_scores / np.sum(exp_scores, axis=1, keepdims=True)

# Prepare dataset

X = np.array([
 [0, 0],

[0, 1],

[1, 0],

[1, 1]

])

y = np.array([

[1, 0],

[0, 1],

[0, 1],

[1, 0]

])

# Split dataset into train and test sets

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# Create and train the ANN model

input_size = X.shape[1]

hidden_size = 4

output_size = y.shape[1]

ann = NeuralNetwork(input_size, hidden_size, output_size)

ann.train(X_train, y_train, epochs=10000, learning_rate=0.1)

# Predict on test set

predictions = ann.predict(X_test)

print("Predictions:", predictions)
10. Write a program to implement Genetic Algorithm for different types of gene representation.
We'll consider two types of gene representation: binary and integer.
First, let's define the basic structure and functions for the GA:
Code:
import random

class GeneticAlgorithm:
def __init__(self, population_size, gene_length, gene_representation):
self.population_size = population_size
self.gene_length = gene_length
self.gene_representation = gene_representation
self.population = []

def initialize_population(self):
# Initialize a random population
self.population = [self.generate_random_gene() for _ in
range(self.population_size)]

def generate_random_gene(self):
# Generate a random gene based on the gene representation
if self.gene_representation == "binary":
return [random.choice([0, 1]) for _ in range(self.gene_length)]
elif self.gene_representation == "integer":
return [random.randint(0, 9) for _ in range(self.gene_length)]

def evaluate_fitness(self, gene):

# Evaluate the fitness of a gene (specific to the problem)
# Return a fitness score

def select_parents(self):
# Select parents from the population based on their fitness scores
# Return a pair of selected parents

def crossover(self, parent1, parent2):

# Perform crossover between two parents to create offspring
# Return the offspring gene

def mutate(self, gene):

# Perform mutation on a gene
# Return the mutated gene

def evolve_population(self):
 new_population = []

while len(new_population) < self.population_size:

parent1, parent2 = self.select_parents()
offspring = self.crossover(parent1, parent2)
mutated_offspring = self.mutate(offspring)
new_population.append(mutated_offspring)

self.population = new_population

Now, let's provide an example usage of the GeneticAlgorithm class with binary and
integer gene representations:
Code:

# Binary Gene Representation Example

population_size = 10
gene_length = 8
gene_representation = "binary"

ga_binary = GeneticAlgorithm(population_size, gene_length, gene_representation)

ga_binary.initialize_population()

for generation in range(10):

print(f"Generation: {generation}")
for gene in ga_binary.population:
fitness = ga_binary.evaluate_fitness(gene)
print(f"Gene: {gene}, Fitness: {fitness}")

ga_binary.evolve_population()
print()

# Integer Gene Representation Example

population_size = 10
gene_length = 4
gene_representation = "integer"

ga_integer = GeneticAlgorithm(population_size, gene_length, gene_representation)

ga_integer.initialize_population()

for generation in range(10):

print(f"Generation: {generation}")
for gene in ga_integer.population:
fitness = ga_integer.evaluate_fitness(gene)
print(f"Gene: {gene}, Fitness: {fitness}")
 ga_integer.evolve_population()
print()