EXPERIMENT-1

AIM: Write a python program to implement Breadth First Search Traversal.

Problem Statement: The problem is to implement a Breadth First Search (BFS) traversal algorithm in
Python for a given graph. BFS is a fundamental graph traversal technique that explores all the vertices of a
graph level by level, starting from a given source node. Unlike Depth First Search, which goes deep into one
branch before backtracking, BFS uses a queue data structure to ensure that all neighbors of a node are
visited before moving to the next level. The task is to represent the graph using an appropriate data
structure (such as an adjacency list or adjacency matrix) and then write a Python program that performs
BFS traversal from a chosen starting vertex. The program should output the sequence of nodes visited
during the traversal, thereby demonstrating how BFS systematically explores the graph layer by layer.

Problem Introduction: Breadth-First Search (BFS) is a graph traversal algorithm used to explore nodes and
edges of a graph systematically. It starts from a chosen source node and visits all its immediate neighbors
first, before moving on to the next level of neighbors. BFS uses a queue to keep track of nodes to be visited,
making it a level-order traversal technique. It is widely used to find the shortest path in unweighted graphs,
check connectivity, and solve real-world problems like web crawling and social network analysis.
Example-: Graph Representation:
Vertices = {0, 1, 2, 3, 4}
Edges = {(0–1), (0–2), (1–3), (1–4)}
Graph structure (undirected):

BFS Traversal starting from node 0:

 Start at 0 → Visit it → Queue = [0]
 Dequeue 0 → Visit neighbors 1, 2 → Queue = [1, 2]
 Dequeue 1 → Visit neighbors 3, 4 → Queue = [2, 3, 4]
 Dequeue 2 → No new nodes (already visited) → Queue = [3, 4]
 Dequeue 3 → No new nodes → Queue = [4]
 Dequeue 4 → No new nodes → Queue = []

Algorithm: Steps are:

Step-1: Start from the source node and mark it as visited.
Step-2: Insert the source node into a queue.
Step-3: While the queue is not empty:
 Remove the front node from the queue and process it.
 For each unvisited neighbor of this node:
o Mark it as visited and enqueue it.
Step-4: Repeat until all reachable nodes are visited.
Step-5: End.

Flowchart:

Code:
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
traversal = []
while queue:
node = [Link]()
if node not in visited:
[Link](node)
[Link](node)
for neighbor in graph[node]:
if neighbor not in visited:
 [Link](neighbor)
return traversal
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
result = bfs(graph, 'A')
print("Breadth First Search Traversal:", result)
print("\nName: Pallavi Pandey")
print("Roll No: 2400971539009")

Output:
 EXPERIMENT-2

AIM: Write a python program to implement Water Jug Problem.

Problem Statement: To implement the Water Jug Problem using a search algorithm (such as BFS or DFS).
The problem is defined as follows:
 You are given two jugs with capacities m liters and n liters.
 There is an infinite supply of water.
 The objective is to measure exactly d liters of water using these two jugs.
You are allowed to perform the following operations:
1. Fill a jug completely.
2. Empty a jug completely.
3. Pour water from one jug into the other until either the first jug is empty or the second jug is full.
The program should take m, n, and d as inputs and display the sequence of steps (states of the two jugs) to
reach the goal state (d, 0) or (0, d). If it is not possible to measure d liters, the program should indicate that.

Problem Introduction: The Water Jug Problem is a classic example in Artificial Intelligence and Problem-
Solving, often used to demonstrate state space search techniques. It involves two jugs of different
capacities and the goal is to measure an exact amount of water using a limited set of operations. The
problem becomes interesting because the jugs do not have measurement markings, so we can only achieve
the goal by performing a sequence of operations such as filling, emptying, and pouring water between the
jugs.
This problem is widely used in computer science to explain search algorithms like Breadth First Search (BFS)
and Depth First Search (DFS), as it can be represented as a graph where each node represents a state of the
two jugs and edges represent the possible operations. By exploring these states systematically, we can find
the sequence of steps required to reach the goal state.
Example-: Suppose we have:
 Jug 1 capacity = 4 liters
 Jug 2 capacity = 3 liters
 Target = 2 liters
Goal: Measure exactly 2 liters using these two jugs.
Solution:
1. Fill Jug 2 completely → (Jug1, Jug2) = (0, 3)
2. Pour Jug 2 into Jug 1 → (Jug1, Jug2) = (3, 0)
3. Fill Jug 2 again → (Jug1, Jug2) = (3, 3)
4. Pour Jug 2 into Jug 1 until Jug 1 is full → (Jug1, Jug2) = (4, 2)
Result: Jug 2 now contains exactly 2 liters, achieving the goal.

Algorithm: Steps are:

Step-1: Start with both jugs empty (0, 0).
Step-2: Check if either jug has the target quantity d. If yes, stop.
Step-3: Generate all possible next states using:
 Fill either jug
 Empty either jug
 Pour from one jug to the other
Step-4: Keep track of visited states to avoid repetition.
Step-5: Use BFS/DFS to explore states until the target is reached or all possibilities are exhausted.
Step-6: If the target is found, print the sequence of steps; otherwise, report no solution.
Step-7: End.

Flowchart:

Code:
from collections import deque
def water_jug_bfs(jug1, jug2, target):
visited = set()
queue = deque()
 [Link]((0, 0, []))
while queue:
x, y, path = [Link]()
if (x, y) in visited:
continue
[Link]((x, y))
if x == target or y == target:
return path + [(x, y)]
next_states = [
(jug1, y),
(x, jug2),
(0, y),
(x, 0),
(x - min(x, jug2 - y), y + min(x, jug2 - y)),
(x + min(y, jug1 - x), y - min(y, jug1 - x))
]
for state in next_states:
if state not in visited:
[Link]((state[0], state[1], path + [(x, y)]))
return None
jug1 = 4
jug2 = 3
target = 2
solution = water_jug_bfs(jug1, jug2, target)
print("Name: Pallavi Pandey")
print("Roll No: 2400971539009")
if solution:
print("\nSteps to achieve target:")
for step in solution:
print(f"Jug1: {step[0]}L, Jug2: {step[1]}L")
print(f"\nTarget of {target}L reached!")
else:
 print("No solution possible.")

Output:

EXPERIMENT-3

AIM: Write a python program to remove punctuations from the given string.

Problem Statement: The task is to write a Python program that removes all punctuation marks from a
given string. The program should accept a string input from the user, process it by eliminating characters
such as commas, periods, exclamation marks, question marks, hyphens, semicolons, quotation marks, and
other punctuation symbols, and return a clean string containing only letters, numbers, and spaces. This is
useful for preparing text for further processing, analysis, or display in a simplified format.

Problem Introduction: In text processing and data cleaning, it is often necessary to remove unnecessary
punctuation marks from a string to make it suitable for analysis, storage, or further processing.
Punctuations such as commas, periods, exclamation marks, question marks, and quotation marks can
interfere with operations like word counting, searching, or text comparison. The goal of this program is to
take a string input from the user and produce a version of the string that contains only letters, numbers,
and spaces, effectively removing all punctuation. This process simplifies the text and prepares it for
applications in programming, natural language processing, and data analysis.
Example:
 Input String:
"Hello, World! Welcome to Python programming."
 Output String:
"Hello World Welcome to Python programming"
Explanation: All punctuation marks like the comma , and exclamation mark ! have been removed from the
input string, leaving only letters, numbers, and spaces in the output.

Algorithm: Steps are:

Step-1: Start the program.
Step-2: Take the input string from the user.
Step-3: Create an empty string to store the result.
Step-4: For each character in the input string:
 Check if the character is not a punctuation mark.
 If it is not, add it to the result string.
Step-5: After checking all characters, display the result string without punctuations.
Step-6: End.

Flowchart:
Code:
import string
text = input("Enter a string: ")
clean_text = ''.join(char for char in text if char not in [Link])
print("\nOutput:")
print("Name: Pallavi Pandey")
print("Roll No: 2400971539009")
print("String after removing punctuations:", clean_text)

Output:
 EXPERIMENT-4

AIM: Write a python program to sort the sentence in alphabetical order.

Problem Statement: Write a Python program that accepts a sentence from the user and sorts the words in
alphabetical order. The program should treat words in a case-insensitive manner while sorting but retain
their original forms in the output. After sorting, the program should display the newly arranged sentence.
This program helps in organizing textual data and can be useful in applications where ordered word lists are
needed, such as dictionaries, search engines, or text analysis.

Problem Introduction: Sorting the words of a sentence in alphabetical order is a basic text-processing task
in programming. It helps in organizing data, improving readability, and making it easier to search or analyze
text. In this program, the sentence entered by the user is split into individual words, sorted alphabetically
(ignoring case), and then recombined to form a new sorted sentence.
Example:
 Input:
"Learning Python is fun and exciting"
 Output:
"and exciting fun is Learning Python"
Explanation: The program takes the input sentence, splits it into words: ["Learning", "Python", "is", "fun",
"and", "exciting"], sorts them alphabetically ignoring case: ["and", "exciting", "fun", "is", "Learning",
"Python"], and then joins them to form the sorted sentence.

Algorithm: Steps are:

Step-1: Start the program.
Step-2: Accept a sentence as input from the user.
Step-3: Split the sentence into individual words using spaces as separators.
Step-4: Sort the list of words in alphabetical order, ignoring case.
Step-5: Join the sorted words back into a sentence with spaces.
Step-6: Display the sorted sentence.
Step-7: End.

Flowchart:
Code:
sentence = input("Enter a sentence: ")
words = [Link]()
[Link](key=lambda x: [Link]())
sorted_sentence = " ".join(words)
print("\nName: Pallavi Pandey")
print("Roll No: 2400971539009")
print("Sorted Sentence:", sorted_sentence)

Output:
 EXPERIMENT-5

AIM: Write a program to implement Hangman game using python.

Problem Statement: To implement the classic Hangman game, where the program selects a word randomly
and the player tries to guess it one letter at a time. For every incorrect guess, a part of the hangman is
drawn, and the player loses an attempt. The game continues until the player either correctly guesses all the
letters of the word or exhausts all attempts, resulting in a loss. The program should display the current state
of the word, the letters guessed so far, and the remaining attempts after each guess. This game not only
provides entertainment but also helps in learning programming concepts such as loops, conditionals, string
manipulation, and user input handling.

Problem Introduction: Hangman is a classic word-guessing game where the player tries to guess a hidden
word one letter at a time. Each incorrect guess brings the player closer to losing by completing a hangman
drawing. Implementing Hangman in Python helps in understanding programming concepts such as loops,
conditionals, string manipulation, lists, and user input handling. It is an interactive way to practice logic and
problem-solving while making learning fun.
Example:
Word to guess: "apple"
 Player guesses: a, e, i, o, p, l
 Progression:
o a____→app__→apple
Output: Congratulations! You guessed the word: apple

Algorithm: Steps are:

Step-1: Start the program.
Step-2: Select a random word from a predefined list.
Step-3: Initialize a display with underscores for each letter of the word.
Step-4: Set the number of allowed incorrect attempts.
Step-5: Repeat until the word is completely guessed or attempts run out:
 Ask the player to guess a letter.
 If the guessed letter is in the word, reveal it in the display.
 If the guessed letter is incorrect, reduce remaining attempts.
 Show the current state of the word and remaining attempts.
Step-6: If the word is guessed, display a congratulatory message.
Step-7: If attempts run out, reveal the word and display a losing message.
Step-8: End.

Flowchart:

Code:
import random
words = ["python", "hangman", "programming", "computer", "education", "developer"]
word_to_guess = [Link](words)
word_display = ["_"] * len(word_to_guess)
guessed_letters = set()
attempts_remaining = 6
print("Welcome to Hangman Game!")
print("You have", attempts_remaining, "incorrect attempts.")
print(" ".join(word_display))
while attempts_remaining > 0 and "_" in word_display:
guess = input("Guess a letter: ").lower()
if guess in guessed_letters:
print("You already guessed that letter.")
continue
 guessed_letters.add(guess)
if guess in word_to_guess:
for index, letter in enumerate(word_to_guess):
if letter == guess:
word_display[index] = guess
print("Good guess:", " ".join(word_display))
else:
attempts_remaining -= 1
print("Wrong guess. Attempts remaining:", attempts_remaining)
print(" ".join(word_display))
print("\nName: Pallavi Pandey")
print("Roll No: 2400971539009")
if "_" not in word_display:
print("Congratulations! You guessed the word:", word_to_guess)
else:
print("Game Over! The word was:", word_to_guess)

Output:
 EXPERIMENT-6

AIM: Write a program in Python to implement Tic Tac Toe game.

Problem Statement: Write a Python program to implement the Tic Tac Toe game, a two-player game
played on a 3×3 grid. Players take turns to mark their symbol (“X” or “O”) in an empty cell. The player who
succeeds in placing three of their marks in a horizontal, vertical, or diagonal row wins the game. If all cells
are filled without any player achieving three in a row, the game is declared a draw. The program should
display the game board after each move, accept valid moves from the players, check for a winner or a draw,
and display the final result.

Problem Introduction: Tic Tac Toe is a classic two-player game played on a 3×3 grid, where players take
turns marking cells with “X” or “O”. The goal is to place three of their symbols in a horizontal, vertical, or
diagonal row to win the game. If all cells are filled without a winning combination, the game ends in a draw.
Implementing Tic Tac Toe in Python helps in understanding arrays or lists, loops, conditional statements,
input validation, and turn-based logic, making it an excellent exercise for learning programming
fundamentals.
Example:

Algorithm: Steps are:

Step-1: Initialize the board
o Create a 3×3 grid filled with empty spaces (or numbers 1–9 to show positions).
Step-2: Set players
o Player 1 → X
o Player 2 → O
Step-3: Loop until the game ends
o Display the current board.
o Ask the current player to choose a position (1–9).
o Check validity:
  If the chosen position is empty, place the player's mark.
 Else, ask for another position.
Step-4: Check for win
o After each move, check all possible winning conditions:
 3 marks in a row (horizontal, vertical, diagonal).
o If a player wins → announce winner and end game.
Step-5: Check for draw
o If all positions are filled and no winner → declare draw.
Step-6: Switch player
o Alternate turns between X and O.
Step-7: Repeat steps 3–6 until win or draw.

Flowchart:

Code:
def display_board(board):
print("\n")
print(f" {board[0]} | {board[1]} | {board[2]} ")
print("---|---|---")
print(f" {board[3]} | {board[4]} | {board[5]} ")
print("---|---|---")
 print(f" {board[6]} | {board[7]} | {board[8]} ")
print("\n")
def check_win(board, mark):
win_conditions = [
[0,1,2], [3,4,5], [6,7,8],
[0,3,6], [1,4,7], [2,5,8],
[0,4,8], [2,4,6]
]
for condition in win_conditions:
if board[condition[0]] == board[condition[1]] == board[condition[2]] == mark:
return True
return False
def check_draw(board):
return all(space in ['X','O'] for space in board)
def tic_tac_toe():
board = [str(i) for i in range(1,10)]
current_player = 'X'
while True:
display_board(board)
move = input(f"Player {current_player}, enter your position (1-9): ")
if not [Link]() or int(move) < 1 or int(move) > 9:
print("Invalid input! Enter a number between 1 and 9.")
continue
move = int(move) - 1
if board[move] in ['X','O']:
print("Position already taken! Choose another position.")
continue
board[move] = current_player
if check_win(board, current_player):
display_board(board)
print(f"Player {current_player} wins! 🎉")
break
 if check_draw(board):
display_board(board)
print("It's a draw! 🤝")
break
current_player = 'O' if current_player == 'X' else 'X'
print("\nGame Over")
print("Name: Pallavi Pandey")
print("Roll No: 2400971539009")
tic_tac_toe()

Output:
 EXPERIMENT-7

AIM: Write a python program to remove stop words for a given passage from a text file using NLTK.

Problem Statement: The task is to write a Python program that removes stop words from a passage stored
in a text file using the NLTK (Natural Language Toolkit) library. The program should read the text from the
file, tokenize it into individual words, and filter out common stop words such as “the”, “is”, “in”, “and”, etc.,
using NLTK’s predefined stop words list. After removing these words, the program should display the
cleaned passage without stop words. Optionally, the filtered text can also be saved to a separate file for
further use. This helps in preprocessing textual data by eliminating words that do not add significant
meaning, making it useful for tasks like text analysis, natural language processing, and information retrieval.

Problem Introduction: In natural language processing (NLP), stop words are common words that do not
carry significant meaning, such as “the”, “is”, “and”, “in”, etc. Removing these words from text is an
important preprocessing step to make text analysis more efficient and meaningful. The NLTK (Natural
Language Toolkit) in Python provides a ready-made list of stop words for various languages and tools for
tokenizing text. By removing stop words from a passage, we can focus on the important words that
contribute to the meaning of the text, which is useful for tasks like text mining, sentiment analysis, and
information retrieval.
Example:
 Input Passage:
This is an example of removing stop words from text.
 Output after removing stop words:
example removing stop words text
Explanation: Common words like “This”, “is”, “an”, “of”, “from” are stop words and have been removed,
keeping only the meaningful words.

Algorithm: Steps are:

Step-1: Import NLTK library
 Import the stop words list and tokenizer from NLTK.
Step-2: Read text from file
 Open the text file and read its content into a string variable.
Step-3: Tokenize the text
 Split the text into individual words using a tokenizer.
Step-4: Load stop words
 Get the list of stop words for the required language (e.g., English) from NLTK.
Step-5: Filter the words
 For each word in the tokenized list, check if it is not a stop word.
  Keep only the words that are not in the stop words list.
Step-6: Display or save the result
 Join the filtered words back into a string and display or write to another file.
Step-7: End.

Flowchart:

Code:
[Link]-
import nltk
from [Link] import stopwords
from [Link] import word_tokenize
[Link]('punkt')
[Link]('stopwords')
file_path = "[Link]"
with open(file_path, "r") as file:
text = [Link]()
words = word_tokenize(text)
stop_words = set([Link]("english"))
filtered_words = [word for word in words if [Link]() not in stop_words]
print("Filtered Passage (Stop Words Removed):")
print(" ".join(filtered_words))
print("\nName: Pallavi Pandey")
print("Roll No: 2400971539009")

[Link]-
This is a sample passage to demonstrate stop word removal using NLTK.

Output:
 EXPERIMENT-8

AIM: Write a Python program to implement stemming for a given sentences using NLTK.

Problem Statement: The task is to develop a Python program that demonstrates the process of stemming
using the NLTK library. The program should accept a sentence from the user and break it into individual
words through tokenization. After tokenizing the sentence, the program must apply a stemming algorithm,
such as the Porter Stemmer, to convert each word into its root form by removing suffixes. Finally, the
program should display the original words along with their stemmed versions. This problem aims to help
students understand the concept of stemming in Natural Language Processing and how it can be
implemented using Python and NLTK.

Problem Introduction: In Natural Language Processing (NLP), words often appear in various grammatical
forms, making tasks like text analysis, searching, and classification more difficult. To handle this challenge,
stemming is used to reduce words to their base or root forms.
For example: words such as “playing,” “played,” “player,” and “plays” can all be reduced to the root word
“play.” This simplifies the text and helps algorithms process information more efficiently. In this problem,
you are required to write a Python program using the NLTK library that takes a sentence as input, tokenizes
it into individual words, and applies a stemming algorithm to produce their root forms. This introduction
highlights the importance of stemming and sets the foundation for implementing it in Python.

Algorithm: Steps are:

Step-1: Start
Step-2: Import required libraries
 Import PorterStemmer from [Link] .
 Import word_tokenize from [Link] .
Step-3: Create a stemmer object
 Initialize PorterStemmer().
Step-4: Input the sentence
 Read a sentence from the user.
Step-5: Tokenize the input sentence
 Use word_tokenize() to split the sentence into words.
Step-6: Apply stemming to each word
 For each word in the tokenized list, apply the stem() function of PorterStemmer.
Step-7: Store/Display the results
 Display the original words.
 Display the corresponding stemmed words.
Step-8: End.

Flowchart:

Code:
Stemming_nltk.py-
from [Link] import PorterStemmer
from [Link] import word_tokenize

ps = PorterStemmer()

sentence = input("Enter a sentence: ")

words = word_tokenize(sentence)
stemmed_words = [[Link](word) for word in words]

print("\nOriginal Words:", words)

print("Stemmed Words :", stemmed_words)

print("\nName: Pallavi Pandey")

print("Roll No: 2400971539009")
Output:
 EXPERIMENT-9

AIM: Write a program to Part of speech tagging for the given sentences using NLTK.

Problem Statement: Part-of-Speech (POS) tagging is an essential step in Natural Language Processing (NLP)
where each word in a sentence is assigned a grammatical category such as noun, verb, adjective, adverb,
etc. The goal of this problem is to write a Python program that performs POS tagging on a given sentence
using the NLTK library. The program should accept a sentence from the user, tokenize it into words, and
apply NLTK’s POS tagger to identify the part of speech for each word. Finally, the program should display
the sentence along with the POS tags. This helps students understand how POS tagging works and how it
supports various NLP applications like text mining, parsing, and language modelling.

Problem Introduction: Part-of-Speech (POS) tagging is a key technique in Natural Language Processing used to
identify the grammatical role of each word in a sentence. It helps in understanding sentence structure by tagging
words as nouns, verbs, adjectives, and more. In this problem, we use the NLTK library in Python to input a sentence,
tokenize it, and automatically assign POS tags to each word. This introduces students to the basics of linguistic
analysis and NLP tools.

Example: Given the sentence: "Tushar is studying in Galgotias College." POS tagging returns: [('Tushar',
'NNP'), ('is', 'VBZ'), ('studying', 'VBG'), ('in', 'IN'), ('Galgotias', 'NNP'), ('College', 'NNP'), ('.', '.')] This output
shows each word paired with its respective POS tag.

Algorithm: Steps are:

Step-1: Start
Step-2: Import the nltk library.
Step-3: Download required resources like
(punkt for tokenization andaveraged_perceptron_tagger for tagging).
Step-4: Define a multi-line input text paragraph.
Step-5: Display the original input text.
Step-6: Tokenize the input text into individual words using nltk.word_tokenize().
Step-7: Display the tokenized words.
Step-8: Apply part-of-speech tagging to the tokenized words using nltk.pos_tag().
Step-9: Print the list of words along with their POS tags.

Flowchart:
Code:
Pos_tagging_nltk.py-
import nltk
from [Link] import word_tokenize

[Link]('punkt')
[Link]('averaged_perceptron_tagger')

sentence = input("Enter a sentence: ")

words = word_tokenize(sentence)

pos_tags = nltk.pos_tag(words)

print("\nPart of Speech Tagging:")

for word, tag in pos_tags:
print(f"{word} --> {tag}")

print("\nName: Pallavi Pandey")

print("Roll No: 2400971539009")
Output: