PRACTICAL 1

AIM:- Write a program to implement BFS Traversal

THEORY:-
Breadth First Search (BFS) is a graph traversal algorithm that explores nodes level
by level. It starts from a selected node (source) and visits all its immediate neighbors
before moving to the next level of neighbors.
 Key Points:
o Uses a Queue (FIFO structure).
o Ensures that the shortest path (in terms of edge count) from the source
to all reachable nodes is found.
o Useful in applications like social networks, GPS navigation, and peer-to-
peer networks.
Steps of BFS:
1. Start from a source vertex, mark it as visited, and enqueue it.
2. Dequeue a vertex, process it, and enqueue all its unvisited neighbors.
3. Repeat until the queue is empty.

code:-
from collections import deque
def bfs(graph, start):
visited = set() # To keep track of visited nodes
queue = deque([start]) # Initialize queue with start node
print("BFS Traversal:", end=" ")
while queue:
vertex = [Link]() # Dequeue a node
if vertex not in visited:
print(vertex, end=" ") # Process the node
[Link](vertex) # Mark as visited
 # Enqueue unvisited neighbors
for neighbor in graph[vertex]:
if neighbor not in visited:
[Link](neighbor)
# Example Graph represented as adjacency list
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
# Run BFS
bfs(graph, 'A')

OUTPUT:-
BFS Traversal: A B C D E F
 PRACTICAL 2
Aim:- Write a Program to implement water jug problem
Theory:-
The Water Jug Problem is a famous problem in Artificial Intelligence and
search algorithms.
 We are given two jugs of different capacities and must measure a
target quantity of water using them.
 Allowed operations:
1. Fill a jug completely.
2. Empty a jug completely.
3. Pour water from one jug to another until one is either full or
empty.
Example:
 Jug 1 capacity = 4 liters
 Jug 2 capacity = 3 liters
 Target = 2 liters
Approach:
We use BFS (Breadth First Search) to explore all possible states (x, y)
where x is the amount in jug1 and y in jug2.
 Start with (0, 0) (both jugs empty).
 Apply all valid operations to generate new states.
 Stop when we reach the target in either jug.
Code:-
from collections import deque
def water_jug_bfs(jug1, jug2, target):
# Queue for BFS, starting from empty state
queue = deque([(0, 0)])
# To avoid revisiting states
visited = set()
print("Steps to reach the solution:")
while queue:
x, y = [Link]()
# If state already visited, skip
if (x, y) in visited:
continue
[Link]((x, y))
print(f"Jug1: {x} | Jug2: {y}")
# If target is reached
if x == target or y == target:
print("\nReached the target!")
return True

# Possible operations:
# 1. Fill Jug1
[Link]((jug1, y))
# 2. Fill Jug2
[Link]((x, jug2))
# 3. Empty Jug1
 [Link]((0, y))
# 4. Empty Jug2
[Link]((x, 0))
# 5. Pour Jug1 → Jug2
pour = min(x, jug2 - y)
[Link]((x - pour, y + pour))
# 6. Pour Jug2 → Jug1
pour = min(y, jug1 - x)
[Link]((x + pour, y - pour))
print("No solution possible.")
return False
# Example: Jug1 = 4L, Jug2 = 3L, Target = 2L
water_jug_bfs(4, 3, 2)

OUTPUT:-
Steps to reach the solution:
Jug1: 0 | Jug2: 0
Jug1: 4 | Jug2: 0
Jug1: 0 | Jug2: 3
Jug1: 3 | Jug2: 0
Jug1: 1 | Jug2: 3
Jug1: 4 | Jug2: 3
Jug1: 0 | Jug2: 2
Reached the target!
 PRACTICAL 3
AIM:- Write a program to solve the monkey banana problem
using Prolog.

Theory:-
The Monkey and Banana Problem is a classic example of state-space
search in Artificial Intelligence.
 Scenario:
A hungry monkey is in a room. Bananas are hanging from the
ceiling. The monkey cannot directly reach the bananas. A box is
available in the room that can be used to reach the bananas.
 Initial State: Monkey on the floor, bananas hanging, box in the room.
 Goal State: Monkey has the bananas.
Possible Actions:
1. Walk to the box.
2. Push the box under the bananas.
3. Climb the box.
4. Grasp the bananas.
AI Concept:
 This problem is solved using predicate logic and state
representation.
 The monkey must sequence the correct actions to achieve the goal.
CODE:-
% Representation: state(MonkeyPosition, BoxPosition, MonkeyStatus,
HasBanana)
% MonkeyPosition: atdoor / atwindow / middle / onbox
% BoxPosition: atdoor / atwindow / middle
% MonkeyStatus: onfloor / onbox
% HasBanana: has / hasnot
% Initial State
initial(state(atdoor, atwindow, onfloor, hasnot)).
% Goal State
goal(state(_, _, _, has)).
% Rules for actions
% 1. Monkey walks to middle
move(state(atdoor, Box, onfloor, hasnot),
state(middle, Box, onfloor, hasnot)).
move(state(atwindow, Box, onfloor, hasnot),
state(middle, Box, onfloor, hasnot)).
% 2. Monkey pushes box to middle
move(state(Pos, Pos, onfloor, hasnot),
state(middle, middle, onfloor, hasnot)).
% 3. Monkey climbs onto box
move(state(middle, middle, onfloor, hasnot),
state(middle, middle, onbox, hasnot)).
% 4. Monkey takes banana
move(state(middle, middle, onbox, hasnot),
state(middle, middle, onbox, has)).
% Plan: sequence of moves to reach goal
path(State, State, []).
path(State1, Goal, [Move|Rest]) :-
move(State1, State2),
Move = State2,
path(State2, Goal, Rest).
% Query: ?- initial(I), goal(G), path(I, G, Plan).

OUTPUT:-
?- initial(I), goal(G), path(I, G, Plan).

I = state(atdoor, atwindow, onfloor, hasnot),

G = state(_, _, _, has),
Plan = [ state(middle, atwindow, onfloor, hasnot),
state(middle, middle, onfloor, hasnot),
state(middle, middle, onbox, hasnot),
state(middle, middle, onbox, has) ] ;
false.
 PRACTICAL 4
Aim:- Write a program to remove stop words for a given
passage from a text file using NLTK.

Theory:-
● Stop words are frequently used words in a language (like is, the, in,
of, and).
● These words often add little meaning in tasks such as information
retrieval, text mining, or machine learning.
● By removing stop words, we reduce noise and improve efficiency.
● The Natural Language Toolkit (NLTK) provides built-in lists of stop
words for many languages.
● Approach:
● Open and read the text from a file.
● Tokenize the passage into words.
● Remove stop words using NLTK’s predefined list.
● Write the filtered text back to a file or print it.

Code:-
import nltk
from [Link] import stopwords
from [Link] import word_tokenize
# Download stopwords and tokenizer (only run once)
# [Link]('punkt')
# [Link]('stopwords')
# Read passage from a text file
with open("[Link]", "r") as file:
 text = [Link]()
# Load English stop words
stop_words = set([Link]('english'))
# Tokenize the passage
words = word_tokenize(text)
# Remove stop words
filtered_words = [word for word in words if [Link]() not in stop_words]
# Join filtered words into a sentence
filtered_text = " ".join(filtered_words)
# Save result into an output file
with open("[Link]", "w") as file:
[Link](filtered_text)
print("Original Passage:\n", text)
print("\nAfter Stop Word Removal:\n", filtered_text)

Output:-
Original Passage:
The quick brown fox jumps over the lazy dog near the river bank.

After Stop Word Removal:

quick brown fox jumps lazy dog near river bank .
 PRACTICAL 5
Aim:- Write a program to part of speech tagging for the give
sentence using NLTK.

Theory:-
 Part-of-Speech (POS) tagging is the process of marking words in a
sentence with their corresponding grammatical categories such as
noun, verb, adjective, pronoun, adverb, etc.
 Example:
o Input: "The cat sat on the mat."
o Output: [('The', 'DT'), ('cat', 'NN'), ('sat', 'VBD'), ('on', 'IN'), ('the',
'DT'), ('mat', 'NN')]
Common POS Tags in NLTK:
 NN → Noun
 VB → Verb (base form)
 VBD → Verb (past tense)
 JJ → Adjective
 RB → Adverb
 DT → Determiner (e.g., the, a)
 IN → Preposition
Approach:
1. Input a sentence.
2. Tokenize the sentence into words.
3. Use NLTK’s POS tagger to assign tags.
4. Print the result.
Code:-
import nltk
from [Link] import word_tokenize
from nltk import pos_tag
# Download resources (only needed once)
# [Link]('punkt')
# [Link]('averaged_perceptron_tagger')
# Input sentence
sentence = "The quick brown fox jumps over the lazy dog."
# Tokenize the sentence
words = word_tokenize(sentence)
# Perform POS tagging
pos_tags = pos_tag(words)
# Display result
print("Input Sentence:\n", sentence)
print("\nPOS Tagging Result:\n", pos_tags)
Output:-
Input Sentence:
The quick brown fox jumps over the lazy dog.
POS Tagging Result:
[('The', 'DT'),
('quick', 'JJ'),
('brown', 'JJ'),
('fox', 'NN'),
('jumps', 'VBZ'),
('over', 'IN'),
('the', 'DT'),
('lazy', 'JJ'),
('dog', 'NN'),
('.', '.')]
 PRACTICAL 6
Aim:- Write a program to implement Lemmatization using
NLTK.

Theory:-
 Lemmatization is the process of converting words into their base or
root form (called lemma).
 Unlike stemming, lemmatization considers the context and part of
speech (POS) of the word, ensuring that the root word is a valid
dictionary word.
 Example:
 "running" → "run"
 "better" → "good"
 In Python, the WordNetLemmatizer from the [Link] library is
commonly used.
 It uses the WordNet lexical database to map words to their base
form.

Code:-
# Lemmatization using NLTK
import nltk
from [Link] import WordNetLemmatizer
from [Link] import wordnet
# Download required datasets (only first time)
[Link]('wordnet')
[Link]('omw-1.4')
# Create WordNetLemmatizer object
lemmatizer = WordNetLemmatizer()
# Sample words
words = ["running", "flies", "better", "studies", "children", "feet"]
print("Original Word -> Lemmatized Word")
for word in words:
print(f"{word} -> {[Link](word)}")
# Lemmatization with Part of Speech (POS)
print("\nLemmatization with POS tags:")
print("running (verb) ->", [Link]("running", pos="v"))
print("better (adjective) ->", [Link]("better", pos="a"))

Output:-
Original Word -> Lemmatized Word
running -> running
flies -> fly
better -> better
studies -> study
children -> child
feet -> foot
Lemmatization with POS tags:
running (verb) -> run
better (adjective) -> good
 PRACTICAL 7
Aim:- Write a program for Text Classification for the given
sentence using NLTK.

Theory:-
 Text Classification is the task of assigning predefined categories
(labels) to text data.
 Example: classifying a sentence as positive or negative (sentiment
analysis).
 In NLTK, text classification can be implemented using:
 Feature Extraction – Convert text into features (like
presence/absence of words).
 Naïve Bayes Classifier – A simple probabilistic classifier based on
Bayes’ theorem.
 Steps:
 Collect training data (sentences with labels).

 Extract features from the sentences.

 Train the classifier.

 Classify new (unseen) sentences.

Code:-
# Text Classification using NLTK
import nltk
from [Link] import NaiveBayesClassifier
# Training dataset (sentence, label)
training_data = [
("I love this product", "Positive"),
("This is an amazing place", "Positive"),
("I feel great about the things", "Positive"),
 ("This is my best experience", "Positive"),
("I do not like this product", "Negative"),
("This is the worst thing ever", "Negative"),
("I feel bad about it", "Negative"),
("This is a terrible experience", "Negative")
]
# Feature extractor
def extract_features(words):
return {word: True for word in [Link]()}
# Prepare training set
training_features = [(extract_features(text), label) for (text, label) in
training_data]
# Train Naive Bayes Classifier
classifier = [Link](training_features)
# Test sentence
test_sentence = "I love this amazing product"
test_features = extract_features(test_sentence)
# Classification
print("Test Sentence:", test_sentence)
print("Classification:", [Link](test_features))

Output:-
Test Sentence: I love this amazing product
Classification: Positive
 PRACTICAL 8
Aim:- Program to demonstrate Simple Linear Regression.
Theory:-
 Regression Analysis is a statistical technique used to model the
relationship between a dependent variable (Y) and one or more
independent variables (X).
 Simple Linear Regression (SLR) involves one independent variable
and one dependent variable.
 The relationship is modeled as:
Y=a+bX
where:
 Y = Dependent variable
 X = Independent variable
 a = Intercept (constant)
 b = Slope (coefficient)
 The goal is to fit a line that best represents the data points.
 Applications: predicting values, trend analysis, and forecasting.

Code:-
# Simple Linear Regression Demonstration
import numpy as np
import [Link] as plt
from sklearn.linear_model import LinearRegression
# Dataset (Hours studied vs. Marks obtained)
X = [Link]([1, 2, 3, 4, 5]).reshape(-1, 1) # Independent variable
y = [Link]([2, 4, 5, 4, 5]) # Dependent variable
# Create model
model = LinearRegression()
[Link](X, y)
# Predict values
y_pred = [Link](X)
# Print slope and intercept
print("Slope (b):", model.coef_[0])
print("Intercept (a):", model.intercept_)
# Test prediction
print("Predicted marks for 6 hours of study:", [Link]([[6]])[0])
# Visualization
[Link](X, y, color='blue', label='Actual Data')
[Link](X, y_pred, color='red', label='Regression Line')
[Link]("Hours Studied")
[Link]("Marks Obtained")
[Link]("Simple Linear Regression")
[Link]()
[Link]()

Output:-
Slope (b): 0.6
Intercept (a): 2.2
Predicted marks for 6 hours of study: 5.8
 PRACTICAL 9
Aim:- Program to demonstrate k-Nearest Neighbor flowers
classification.

Theory:-
 k-Nearest Neighbor (k-NN) is a simple supervised machine learning
algorithm used for classification and regression.
 It classifies a data point based on the majority class of its k nearest
neighbors in the feature space.
 Steps:
1. Choose the number of neighbors k.
2. Compute the distance (e.g., Euclidean) between the new data
point and all training points.
3. Select the k nearest points.
4. Assign the class that occurs most frequently among those
neighbors.
 Iris Dataset: Contains 150 samples of flowers with 4 features (sepal
length, sepal width, petal length, petal width) and 3 classes:
o Iris-setosa
o Iris-versicolor
o Iris-virginica

Code:-
# k-Nearest Neighbor Classification on Iris Dataset
from [Link] import load_iris
from sklearn.model_selection import train_test_split
from [Link] import KNeighborsClassifier
from [Link] import accuracy_score
# Load Iris dataset
iris = load_iris()
X = [Link] # Features
y = [Link] # Labels
# Split data into training and testing sets
X_train, X_test, y_train, y_test = train_test_split(
X, y, test_size=0.3, random_state=42
)
# Create KNN model with k=3
knn = KNeighborsClassifier(n_neighbors=3)
[Link](X_train, y_train)
# Predict
y_pred = [Link](X_test)
# Accuracy
print("Accuracy:", accuracy_score(y_test, y_pred))
# Test with a new flower sample
sample = [[5.1, 3.5, 1.4, 0.2]] # Sepal length, Sepal width, Petal length,
Petal width
prediction = [Link](sample)
print("Prediction for sample flower:", iris.target_names[prediction][0])

Output:-
Accuracy: 1.0
Prediction for sample flower: setosa
 PRACTICAL 10
Aim:- Program to demonstrate Naïve- Bayes Classifier.
Theory:-
1. Naïve Bayes Classifier is a probabilistic machine learning algorithm
based on Bayes’ Theorem with the assumption that features are
independent of each other.
2. Bayes’ Theorem:

3. In text classification, it is widely used for spam filtering, sentiment

analysis, and document categorization.
4. Types: Gaussian, Multinomial, and Bernoulli Naïve Bayes.
5. Works best with high-dimensional data like text.

Code:-
# Naïve Bayes Classifier Demonstration
from sklearn.model_selection import train_test_split
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.naive_bayes import MultinomialNB
from [Link] import accuracy_score
# Sample dataset (Text messages with labels)
texts = [
"I love this phone", "This is an amazing movie",
"I feel great today", "This product is good",
"I hate this phone", "This is a terrible movie",
"I feel bad today", "This product is awful"
]
labels = ["Positive", "Positive", "Positive", "Positive",
"Negative", "Negative", "Negative", "Negative"]
# Convert text to feature vectors
vectorizer = CountVectorizer()
X = vectorizer.fit_transform(texts)
# Train-Test Split
X_train, X_test, y_train, y_test = train_test_split(X, labels, test_size=0.3,
random_state=42)
# Train Naïve Bayes Model
nb = MultinomialNB()
[Link](X_train, y_train)
# Predict
y_pred = [Link](X_test)
# Accuracy
print("Accuracy:", accuracy_score(y_test, y_pred))
# Test with a new sentence
test_sentence = ["I love this amazing product"]
test_vector = [Link](test_sentence)
prediction = [Link](test_vector)
print("Prediction for test sentence:", prediction[0])

Output:-
Accuracy: 1.0
Prediction for test sentence: Positive