AI Lab Report 25537 Hridesh Sapkota

1. WAP to implement BFS for a graph.

(Recommended Language : Python) (Note: The graph
should be drawn in lab report)

from collections import defaultdict, deque

def bfs(graph, start):

visited = set() # Set to track visited vertices
queue = deque([start]) # Queue for BFS traversal
visited.add(start)

while queue:
vertex = queue.popleft()
print(vertex, end=' ') # Process the vertex (e.g., print it)

for neighbor in graph[vertex]:

if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)

graph = defaultdict(list)
graph[0] = [1, 2]
graph[1] = [2, 3]
graph[2] = [3]
graph[3] = [4, 5]
graph[4] = []
graph[5] = []

print("BFS Traversal:")
bfs(graph, 0)

Output:

1
AI Lab Report 25537 Hridesh Sapkota

2. WAP to implement Uniform-cost search.

(Recommended Language : Python) (Note: The graph
should be drawn in lab report)

import heapq

def ucs(graph, start, goal):

visited = set()
queue = [(0, start)]
cost_so_far = {start: 0}

while queue:
current_cost, current_node = heapq.heappop(queue)

if current_node == goal:
break

if current_node in visited:
continue

visited.add(current_node)

for neighbor, weight in graph[current_node]:

new_cost = cost_so_far[current_node] + weight

if neighbor not in cost_so_far or new_cost <

cost_so_far[neighbor]:
cost_so_far[neighbor] = new_cost
heapq.heappush(queue, (new_cost, neighbor))

return cost_so_far[goal] if goal in cost_so_far else float('inf')

graph = {
'A': [('B', 4), ('C', 2)],
'B': [('A', 4), ('C', 1), ('D', 5)],
'C': [('A', 2), ('B', 1), ('D', 8)],
'D': [('B', 5), ('C', 8), ('E', 3)],
'E': [('D', 3)]
}

start_node = 'A'
goal_node = 'E'

2
AI Lab Report 25537 Hridesh Sapkota

cost = ucs(graph, start_node, goal_node)

print("The cost to reach", goal_node, "from", start_node, "is", cost)

Output:

3
AI Lab Report 25537 Hridesh Sapkota

3. WAP to implement DFS for a graph (Recommended

Language: Python). (Note: The graph should be
drawn in lab report).
def dfs(graph, start, visited):
visited.add(start)
print(start, end=' ')

for neighbor in graph[start]:

if neighbor not in visited:
dfs(graph, neighbor, visited)

graph = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['E'],
'D': [],
'E': ['F'],
'F': []
}

print("DFS Traversal:")
visited_nodes = set()
dfs(graph, 'A', visited_nodes)

Output:

4. WAP to implement Depth limited search for a

graph (Recommended Language: Python). (Note: The
graph should be drawn in lab report)
def dls(graph, start, goal, depth_limit):
return dls_recursive(graph, start, goal, depth_limit, 0, set())

def dls_recursive(graph, current_node, goal, depth_limit,

current_depth, visited):
if current_node == goal:
return True

if current_depth >= depth_limit:

return False

4
AI Lab Report 25537 Hridesh Sapkota

visited.add(current_node)

for neighbor in graph[current_node]:

if neighbor not in visited:
if dls_recursive(graph, neighbor, goal, depth_limit,
current_depth + 1, visited):
return True

return False

graph = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['E'],
'D': [],
'E': ['F'],
'F': []
}

print("Depth-Limited Search:")
start_node = 'A'
goal_node = 'F'
limit = 3

result = dls(graph, start_node, goal_node, limit)

if result:
print("Goal node", goal_node, "found within depth limit", limit)
else:
print("Goal node", goal_node, "not found within depth limit",
limit)

5
AI Lab Report 25537 Hridesh Sapkota

Output:

5. WAP to implement greedy best first search.

(Recommended Language: Python) (Note: Necessary
information should be included in report.)

from queue import PriorityQueue

def gbfs(graph, start, goal):
visited = set()
queue = PriorityQueue()
queue.put((0, start))
while not queue.empty():
_, current_node = queue.get()

if current_node == goal:
return True
visited.add(current_node)
for neighbor, _ in graph[current_node]:
if neighbor not in visited:
priority = heuristic(neighbor, goal)
queue.put((priority, neighbor))
return False
def heuristic(node, goal):
return 0
graph = {
'A': [('B', 5), ('C', 3)],
'B': [('D', 2)],
'C': [('E', 4)],
'D': [],
'E': [('F', 1)],
'F': []
}
start_node = 'A'
goal_node = 'F'
result = gbfs(graph, start_node, goal_node)
if result:
print("Goal node", goal_node, "found.")
else:
print("Goal node", goal_node, "not found.")

6
AI Lab Report 25537 Hridesh Sapkota

Output:

7
AI Lab Report 25537 Hridesh Sapkota

6. WAP to implement A* search. (Recommended

Language : Python) (Note: Necessary information
should be included in report.))

from queue import PriorityQueue

def astar(graph, start, goal):
visited = set()
queue = PriorityQueue()
queue.put((0, start))
cost_so_far = {start: 0}

while not queue.empty():

_, current_node = queue.get()

if current_node == goal:
return True

visited.add(current_node)

for neighbor, weight in graph[current_node]:

new_cost = cost_so_far[current_node] + weight

if neighbor not in cost_so_far or new_cost <

cost_so_far[neighbor]:
cost_so_far[neighbor] = new_cost
priority = new_cost + heuristic(neighbor, goal)
queue.put((priority, neighbor))

return False

def heuristic(node, goal):

return 0

graph = {
'A': [('B', 4), ('C', 2)],
'B': [('C', 1), ('D', 5)],
'C': [('D', 8)],
'D': [('E', 3)],
'E': []
}
start_node = 'A'
goal_node = 'E'

result = astar(graph, start_node, goal_node)

if result:
8
AI Lab Report 25537 Hridesh Sapkota

print("Goal node", goal_node, "found.")

else:
print("Goal node", goal_node, "not found.")

Output:

9
AI Lab Report 25537 Hridesh Sapkota

7. WAP to implement Hill Climbing (Steepest

Ascent) Search. (Recommended Language : Python)
def hill_climbing(problem):
current_state = problem.initial_state()

while True:
neighbors = problem.get_neighbors(current_state)
best_neighbor = max(neighbors, key=lambda state:
problem.heuristic(state))

if problem.heuristic(best_neighbor) <=
problem.heuristic(current_state):
return current_state

current_state = best_neighbor

class Problem:
def initial_state(self):
pass

def heuristic(self, state):

pass

def get_neighbors(self, state):

pass

class MyProblem(Problem):
def initial_state(self):
return 0

def heuristic(self, state):

pass

def get_neighbors(self, state):

pass

problem = MyProblem()
solution = hill_climbing(problem)

print("Solution:", solution)

10
AI Lab Report 25537 Hridesh Sapkota

8. WAP to solve any one Cryptarithmetic Problem

(like TWO +TWO = FOUR or SEND+MORE = MONEY ).
(Recommended Language : Python)

from itertools import permutations

def solve_cryptarithmetic(puzzle):
letters = set()
for word in puzzle:
for letter in word:
letters.add(letter)

letters = sorted(list(letters))
for perm in permutations(range(10), len(letters)):
mapping = {letters[i]: perm[i] for i in range(len(letters))}
if is_solution(puzzle, mapping):
return mapping

return None

def is_solution(puzzle, mapping):

sum1 = sum2 = sum3 = 0

for word in puzzle[0:len(puzzle)-1]:

value = 0
for letter in word:
value = value * 10 + mapping[letter]
sum1 += value

for letter in puzzle[len(puzzle)-1]:

sum3 = sum3 * 10 + mapping[letter]

return sum1 == sum3

puzzle = ['SEND', 'MORE', 'MONEY']

solution = solve_cryptarithmetic(puzzle)

if solution:
print("Solution:")
for word in puzzle:
value = 0
for letter in word:
value = value * 10 + solution[letter]
print(word, '=', value)
else:
11
AI Lab Report 25537 Hridesh Sapkota

print("No solution found.")

Output:

12
AI Lab Report 25537 Hridesh Sapkota

9. Implementing Frame ( Recommended Language: C++

/ use object pointers) "Ram is a person living in
Nepal. He was born on 15th December of year 1990.
He is 6 inch tall and has 75 kg weight. He has a
job. He works at 'ABC company' as AI Researcher
and earns 1.5 lakhs per month. The company is
situated at Kathmandu."
#include <iostream>
#include <string>

class Person {
private:
std::string name;
std::string country;
int birthDay;
int birthMonth;
int birthYear;
double height;
double weight;

public:
Person(const std::string& name, const std::string& country, int
birthDay, int birthMonth, int birthYear,
double height, double weight)
: name(name), country(country), birthDay(birthDay),
birthMonth(birthMonth), birthYear(birthYear),
height(height), weight(weight) {}

void display() {
std::cout << name << " is a person living in " << country <<
".\n";
std::cout << "He was born on " << birthDay << "th " <<
getMonthName(birthMonth) << " of year " << birthYear << ".\n";
std::cout << "He is " << height << " inch tall and has " <<
weight << " kg weight.\n";
}

std::string getMonthName(int month) {

switch (month) {
case 1:
return "January";
case 2:
return "February";
13
AI Lab Report 25537 Hridesh Sapkota

case 3:
return "March";
case 4:
return "April";
case 5:
return "May";
case 6:
return "June";
case 7:
return "July";
case 8:
return "August";
case 9:
return "September";
case 10:
return "October";
case 11:
return "November";
case 12:
return "December";
default:
return "";
}
}
};

class Job {
private:
std::string companyName;
std::string position;
double salary;

public:
Job(const std::string& companyName, const std::string& position,
double salary)
: companyName(companyName), position(position), salary(salary)
{}

void display() {
std::cout << "He has a job. He works at '" << companyName <<
"' as " << position;
std::cout << " and earns " << salary << " lakhs per month.\n";
std::cout << "The company is situated at Kathmandu.\n";
}
};

int main() {

14
AI Lab Report 25537 Hridesh Sapkota

Person* ram = new Person("Ram", "Nepal", 15, 12, 1990, 6, 75);

Job* ramJob = new Job("ABC company", "AI Researcher", 1.5);

ram->display();
ramJob->display();

delete ram;
delete ramJob;

return 0;
}

Output:

15
AI Lab Report 25537 Hridesh Sapkota

10. Implementing Frame (Recommended Language: C++

/ use object pointers) "Ram is a person living in
Nepal. He was born on 15th December of year 1990.
He is 6 inch tall and has 75 kg weight. He has a
job. He works at 'ABC company' as AI Researcher
and earns 1.5 lakhs per month. The company is
situated at Kathmandu." Represent above
information in frames diagrammatically and
implement it using the concepts of class in C++.

#include <iostream>
#include <string>

class Person {
private:
std::string name;
std::string country;
int birthDay;
int birthMonth;
int birthYear;
double height;
double weight;

public:
Person(const std::string& name, const std::string& country, int
birthDay, int birthMonth, int birthYear,
double height, double weight)
: name(name), country(country), birthDay(birthDay),
birthMonth(birthMonth), birthYear(birthYear),
height(height), weight(weight) {}

void display() {
std::cout << "Person Frame:\n";
std::cout << "Name: " << name << std::endl;
std::cout << "Country: " << country << std::endl;
std::cout << "Birthdate: " << birthDay << "th " <<
getMonthName(birthMonth) << ", " << birthYear << std::endl;
std::cout << "Height: " << height << " inches" << std::endl;
std::cout << "Weight: " << weight << " kg" << std::endl;
}

std::string getMonthName(int month) {

static const std::string monthNames[] = {
"January", "February", "March", "April", "May", "June",
"July",
16
AI Lab Report 25537 Hridesh Sapkota

"August", "September", "October", "November", "December"

};
return monthNames[month - 1];
}
};

class Job {
private:
std::string companyName;
std::string position;
double salary;

public:
Job(const std::string& companyName, const std::string& position,
double salary)
: companyName(companyName), position(position), salary(salary)
{}

void display() {
std::cout << "Job Frame:\n";
std::cout << "Company: " << companyName << std::endl;
std::cout << "Position: " << position << std::endl;
std::cout << "Salary: " << salary << " lakhs per month" <<
std::endl;
}
};

int main() {
Person* ram = new Person("Ram", "Nepal", 15, 12, 1990, 6, 75);

Job* ramJob = new Job("ABC company", "AI Researcher", 1.5);

ram->display();
std::cout << std::endl;
ramJob->display();

delete ram;
delete ramJob;

return 0;
}

Output:

17
AI Lab Report 25537 Hridesh Sapkota

11. Prolog Basic a. About Language (What/ When/

Who/ Why)
b. Atoms, Variables, Facts and
Rules in Prolog

a. Prolog is a logic programming language that was developed in the

1970s. It is a declarative language based on formal logic and provides
a different approach to programming compared to procedural or object-
oriented languages. Prolog stands for "Programming in Logic" and is
often used in areas such as artificial intelligence, natural language
processing, expert systems, and theorem proving.

- What: Prolog is a programming language that uses a formal logic-

based approach for solving problems. It is based on the concept of
logical clauses and inference rules.
- When: Prolog was first developed in the 1970s by Alain Colmerauer
and his colleagues. It has since evolved and is still actively used
today.
- Who: Prolog was developed by Alain Colmerauer and his team at the
University of Aix-Marseille in France.
- Why: Prolog was developed with the goal of creating a language that
could handle logic-based programming and provide a foundation for
building intelligent systems. It is particularly well-suited for tasks
involving symbolic reasoning, pattern matching, and backtracking.

b. In Prolog, the basic building blocks are atoms, variables, facts,

and rules.

- Atoms: Atoms are constants in Prolog and represent basic data

elements. They are written in lowercase or enclosed in single quotes
if they contain special characters or start with an uppercase letter.
Examples of atoms are `apple`, `john`, `likes`, and `'Hello, World!'`.

18
AI Lab Report 25537 Hridesh Sapkota

- Variables: Variables in Prolog start with an uppercase letter or an

underscore `_`. They represent placeholders for unknown values that
can be unified with other terms. Variables can be used to instantiate
and query Prolog predicates. Examples of variables are `X`, `_`,
`Person`, and `Age`.

- Facts: Facts are statements in Prolog that represent known

information about a predicate. They are used to define the
relationships between atoms. Facts consist of a predicate followed by
a list of arguments enclosed in parentheses. Facts are often referred
to as the "base case" in Prolog. Here's an example fact: `likes(john,
apples)`.
- Rules: Rules in Prolog define logical relationships and can be used
to derive new information. They consist of a head and a body,
separated by `:-` (pronounced "if"). The head represents the
conclusion or the goal, while the body contains the conditions or the
premises. Rules are often used to define recursive relations. Here's
an example rule: `parent(X, Y) :- father(X, Y) ; mother(X, Y)`.

In Prolog, the combination of facts and rules forms a knowledge base.

By making queries to this knowledge base, Prolog can perform logical
inference and provide solutions based on the rules and facts defined.

These basic elements of Prolog allow for the representation and

manipulation of knowledge using logical clauses and inference rules,
making it a powerful language for tasks involving logic-based
reasoning.

15. WAP to develop a sample medical expert system

capable of diagnosing disease based on the
provided symptoms. (Recommended Language: Prolog
or Python)

diseases = {
"flu": ["fever", "cough", "sore throat", "headache"],
"cold": ["sneezing", "runny nose", "congestion"],
"allergies": ["sneezing", "itchy eyes", "runny nose"]
}
def diagnose_disease(symptoms):
matching_diseases = []

for disease, disease_symptoms in diseases.items():

if set(symptoms).issuperset(disease_symptoms):
matching_diseases.append(disease)

return matching_diseases
user_symptoms = ["sneezing", "runny nose"]
19
AI Lab Report 25537 Hridesh Sapkota

diagnosed_diseases = diagnose_disease(user_symptoms)

if diagnosed_diseases:
print("The possible disease(s) based on the provided symptoms
are:")
for disease in diagnosed_diseases:
print("- " + disease)
else:
print("No matching disease found for the provided symptoms.")

Output:

16. Realization of AND, OR and NOT gates using

Artificial Neurons (Recommended Language: Python)

import numpy as np
def step_function(x):
return 1 if x >= 0 else 0
def AND_gate(x1, x2):
w1, w2, b = 0.5, 0.5, -0.7
inputs = np.array([x1, x2])
weighted_sum = np.sum(inputs * np.array([w1, w2]))
output = step_function(weighted_sum + b)
return output
def OR_gate(x1, x2):
w1, w2, b = 0.5, 0.5, -0.2
inputs = np.array([x1, x2])
weighted_sum = np.sum(inputs * np.array([w1, w2]))
output = step_function(weighted_sum + b)
return output
def NOT_gate(x):
w, b = -0.5, 0.2
weighted_sum = x * w
output = step_function(weighted_sum + b)
return output

print("AND Gate")
print(AND_gate(0, 0)) # 0
print(AND_gate(0, 1)) # 0

20
AI Lab Report 25537 Hridesh Sapkota

print(AND_gate(1, 0)) # 0
print(AND_gate(1, 1)) # 1

print("OR Gate")
print(OR_gate(0, 0)) # 0
print(OR_gate(0, 1)) # 1
print(OR_gate(1, 0)) # 1
print(OR_gate(1, 1)) # 1

print("NOT Gate")
print(NOT_gate(0)) # 1
print(NOT_gate(1)) # 0

Output:

17. A Simple Example of Back Propagation Learning

(Recommended Language : Python)

import numpy as np
def sigmoid(x):
return 1 / (1 + np.exp(-x))

def sigmoid_derivative(x):
return x * (1 - x)

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

21
AI Lab Report 25537 Hridesh Sapkota

self.weights1 = np.random.uniform(-1, 1, (self.input_size,

self.hidden_size))
self.weights2 = np.random.uniform(-1, 1, (self.hidden_size,
self.output_size))

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

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

def forward(self, X):

self.hidden_layer = sigmoid(np.dot(X, self.weights1) +
self.bias1)
self.output_layer = sigmoid(np.dot(self.hidden_layer,
self.weights2) + self.bias2)

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

output_error = y - self.output_layer
output_delta = output_error *
sigmoid_derivative(self.output_layer)

hidden_error = output_delta.dot(self.weights2.T)
hidden_delta = hidden_error *
sigmoid_derivative(self.hidden_layer)

self.weights2 += self.hidden_layer.T.dot(output_delta) *
learning_rate
self.weights1 += X.T.dot(hidden_delta) * learning_rate

self.bias2 += np.sum(output_delta) * learning_rate

self.bias1 += np.sum(hidden_delta) * learning_rate

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

for epoch in range(epochs):
self.forward(X)
self.backward(X, y, learning_rate)

def predict(self, X):

self.forward(X)
return self.output_layer

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

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

nn = NeuralNetwork(2, 2, 1)

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

predictions = nn.predict(X)

22
AI Lab Report 25537 Hridesh Sapkota

print(predictions)

Output:

18. WAP to solve N Queen Problem.(Recommended

Language : Python) (Problem: To find an
arrangement of N queens on a chess board of size
N×N, such that no queen can attack any other
queens on the board)

def is_safe(board, row, col, N):

for i in range(row):
if board[i][col] == 1:
return False

i = row - 1
j = col - 1
while i >= 0 and j >= 0:
if board[i][j] == 1:
return False
i -= 1
j -= 1

i = row - 1
j = col + 1
while i >= 0 and j < N:
if board[i][j] == 1:
return False
i -= 1
23
AI Lab Report 25537 Hridesh Sapkota

j += 1

return True

def solve_n_queens_util(board, row, N):

if row == N:
for i in range(N):
for j in range(N):
print(board[i][j], end=' ')
print()
print()
return True

for col in range(N):

if is_safe(board, row, col, N):
board[row][col] = 1

solve_n_queens_util(board, row + 1, N)

board[row][col] = 0

return False

def solve_n_queens(N):
board = [[0] * N for _ in range(N)]

if not solve_n_queens_util(board, 0, N):

print("No solution exists for N =", N)

N = 4
solve_n_queens(N)

Output:

24
AI Lab Report 25537 Hridesh Sapkota

19. WAP to solve Water Jug Problem. (Recommended

Language : Python) (Problem statement: Given two
jugs, a 4-gallon and 3-gallon having no measuring
markers on them. There is a pump that can be used
to fill the jugs with water and the water can be
poured on the ground. How can you get exactly 2
gallons of water into 4- gallon jug?

def water_jug_problem():
jug1_capacity = 4
jug2_capacity = 3
target = 2

jug1 = 0
jug2 = 0

path = []

while jug1 != target and jug2 != target:

if jug1 == 0:
jug1 = jug1_capacity
path.append((jug1, jug2))
elif jug2 == jug2_capacity:
jug2 = 0
path.append((jug1, jug2))
elif jug1 > 0 and jug2 < jug2_capacity:
pour_amount = min(jug1, jug2_capacity - jug2)
25
AI Lab Report 25537 Hridesh Sapkota

jug1 -= pour_amount
jug2 += pour_amount
path.append((jug1, jug2))
elif jug2 > 0:
jug2 = 0
path.append((jug1, jug2))

return path
solution = water_jug_problem()

for state in solution:

print(state)

Output:

20. WAP to demonstrate some NLP tasks using NLTK.

(Recommended Language : Python) [Sentence
tokenization, Word tokenization, stop words
filtering, word stemming, POS tagging, etc.]
import nltk
from nltk.corpus import stopwords
from nltk.stem import PorterStemmer
from nltk.tokenize import sent_tokenize, word_tokenize,
wordpunct_tokenize
from nltk import pos_tag

nltk.download('punkt')
nltk.download('stopwords')
nltk.download('averaged_perceptron_tagger')
26
AI Lab Report 25537 Hridesh Sapkota

text = "Hello! How are you? I hope you are doing well."
sentences = sent_tokenize(text)
print("Sentence Tokenization:")
for sentence in sentences:
print(sentence)
print()

sentence = "This is an example sentence."

words = word_tokenize(sentence)
print("Word Tokenization:")
for word in words:
print(word)
print()

stop_words = set(stopwords.words('english'))
filtered_words = [word for word in words if word.casefold() not in
stop_words]
print("Stop Words Filtering:")
for word in filtered_words:
print(word)
print()

stemmer = PorterStemmer()
stemmed_words = [stemmer.stem(word) for word in words]
print("Word Stemming:")
for word in stemmed_words:
print(word)
print()

pos_tags = pos_tag(words)
print("POS Tagging:")
for word, tag in pos_tags:
print(word, tag)
print()

Output:

27
AI Lab Report 25537 Hridesh Sapkota

28