NAME : Bijaya kumar rout

REG. NO. : 2301292452

SECTION : A
BRANCH : CSE (AIML)

1.BASIC PYTHON PROGRAM’S

1. Hello World Program
Print :-
Syntax:

print(value, ..., sep=' ', end='\n', file=sys.stdout, flush=False)

Description:

The print() function is used to display output on the console. It can take multiple arguments to print, separated
by a default space, and allows customization of separators (sep), line endings (end), and output destinations
(file).

Code:
print("Hello, World!")

Output:
Hello, World!

2. Variables and Input

Input :-
Syntax:

variable = input(prompt)

Description:

The input() function is used to take user input as a string. The optional prompt displays a message to the user
before input is provided.

Code:
name = input("Enter your name: ")

print(f"Hello, {name}!")

Output:
Enter your name: John

Hello, John!

3. Conditional Statements

If else :-
Syntax:

if condition:

# Code to execute if the condition is True

else:

# Code to execute if the condition is False

Description:

The if-else statement is used for decision-making in Python. It executes one block of code if the condition is
True and another block if the condition is False.

Code:
num = int(input("Enter a number: "))

if num % 2 == 0:

print(f"{num} is even.")

else:

print(f"{num} is odd.")

Output:
Enter a number: 5

5 is odd.

4. Loops
While:-

Syntax:

while condition:

# Code to execute repeatedly while the condition is True

Description:

The while loop is used to repeatedly execute a block of code as long as the given condition
evaluates to True. It is commonly used for indefinite iteration when the number of iterations
is not known in advance.

While Loop:
i=1

while i <= 5:

print(i)

i += 1

Output:
1

For:-
Syntax:

for variable in iterable:

# Code to execute for each item in the iterable

Description:

The for loop is used to iterate over a sequence (such as a list, tuple, string, or range) or any iterable. It executes
the block of code once for each item in the sequence.

For Loop:
for i in range(1, 6):

print(i)

Output:
1

5. Functions
Def :-
Syntax:

def function_name(parameters):
 # Code block defining the function

return value # (optional)

Description:

The def keyword is used to define a function in Python. A function is a reusable block of code that performs a
specific task. It can accept parameters, perform operations, and optionally return a value.

Code:
def add(x, y):

return x + y

num1 = float(input("Enter the first number: "))

num2 = float(input("Enter the second number: "))

result = add(num1, num2)

print(f"The sum of {num1} and {num2} is {result}")

Output:
Enter the first number: 7

Enter the second number: 3

The sum of 7.0 and 3.0 is 10.0

6. List Operations

List:-
Syntax:

my_list = [item1, item2, item3, ...]

Description:

A list is a mutable, ordered collection in Python that can store elements of any data type. Items in a list can be
added, removed, or modified. Lists are defined using square brackets [].

Code:
# Demonstrating List Operations

print("\nList Operations")

my_list = [1, 2, 3, 4, 5]

print("Original List:", my_list)

# Adding elements
my_list.append(6)

print("After append:", my_list)

my_list.insert(2, 10)

print("After insert:", my_list)

# Removing elements

my_list.remove(10)

print("After remove:", my_list)

popped_element = my_list.pop()

print("After pop (removed element):", popped_element, "List:", my_list)

# Slicing and indexing

print("Element at index 1:", my_list[1])

print("Sliced List (1:4):", my_list[1:4])

# Other operations

my_list.reverse()

print("Reversed List:", my_list)

my_list.sort()

print("Sorted List:", my_list)

print("Length of List:", len(my_list))

Output:
List Operations

Original List: [1, 2, 3, 4, 5]

After append: [1, 2, 3, 4, 5, 6]

After insert: [1, 2, 10, 3, 4, 5, 6]

After remove: [1, 2, 3, 4, 5, 6]

After pop (removed element): 6 List: [1, 2, 3, 4, 5]

Element at index 1: 2

Sliced List (1:4): [2, 3, 4]

Reversed List: [5, 4, 3, 2, 1]

Sorted List: [1, 2, 3, 4, 5]

Length of List: 5
7. Dictionary Example
Dictionary:-
Syntax:

my_dict = {key1: value1, key2: value2, ...}

Description:

A dictionary is an unordered, mutable collection in Python that stores data as key-value pairs. Keys must be
unique and immutable, while values can be of any data type. Dictionaries are defined using curly braces {}.

Code:
# Demonstrating Dictionary Operations

print("\nDictionary Operations")

my_dict = {"name": "Alice", "age": 25, "city": "New York"}

print("Original Dictionary:", my_dict)

# Accessing elements

print("Name:", my_dict["name"])

print("Keys:", my_dict.keys())

print("Values:", my_dict.values())

# Adding and updating elements

my_dict["country"] = "USA"

print("After adding country:", my_dict)

my_dict["age"] = 26

print("After updating age:", my_dict)

# Removing elements

deleted_value = my_dict.pop("city")

print("After pop (city):", deleted_value, "Dictionary:", my_dict)

# Other operations

print("Items:", my_dict.items())
my_dict.clear()

print("After clear:", my_dict)

Output:
Dictionary Operations

Original Dictionary: {'name': 'Alice', 'age': 25, 'city': 'New York'}

Name: Alice

Keys: dict_keys(['name', 'age', 'city'])

Values: dict_values(['Alice', 25, 'New York'])

After adding country: {'name': 'Alice', 'age': 25, 'city': 'New York', 'country': 'USA'}

After updating age: {'name': 'Alice', 'age': 26, 'city': 'New York', 'country': 'USA'}

After pop (city): New York Dictionary: {'name': 'Alice', 'age': 26, 'country': 'USA'}

Items: dict_items([('name', 'Alice'), ('age', 26), ('country', 'USA')])

After clear: {}

8. Tuple Example
Tuple:-
Syntax:

my_tuple = (item1, item2, item3, ...)

Description:

A tuple is an immutable, ordered collection in Python that can store elements of any data type. Once defined,
the items in a tuple cannot be changed. Tuples are defined using parentheses ().

Code:
# Demonstrating Tuple Operations

print("\nTuple Operations")

my_tuple = (10, 20, 30, 40, 50)

print("Original Tuple:", my_tuple)

# Accessing elements

print("Element at index 2:", my_tuple[2])

print("Sliced Tuple (1:4):", my_tuple[1:4])

# Other operations
print("Length of Tuple:", len(my_tuple))

print("Count of 20 in Tuple:", my_tuple.count(20))

print("Index of 30 in Tuple:", my_tuple.index(30))

Output:
Tuple Operations

Original Tuple: (10, 20, 30, 40, 50)

Element at index 2: 30

Sliced Tuple (1:4): (20, 30, 40)

Length of Tuple: 5

Count of 20 in Tuple: 1

Index of 30 in Tuple: 2

9. Set Example
Set:-
Syntax:

my_set = {item1, item2, item3, ...}

Description:

A set is an unordered, mutable collection in Python that does not allow duplicate elements. Sets are typically
used to store unique items and are defined using curly braces {}.

Code:
# Demonstrating Set Operations

print("\nSet Operations")

my_set = {1, 2, 3, 4, 5}

print("Original Set:", my_set)

# Adding and removing elements

my_set.add(6)

print("After add:", my_set)

my_set.remove(3)

print("After remove:", my_set)

my_set.discard(10) # No error if element not found

print("After discard (10):", my_set)

# Set operations

set1 = {1, 2, 3}

set2 = {3, 4, 5}

print("Union:", set1.union(set2))

print("Intersection:", set1.intersection(set2))

print("Difference:", set1.difference(set2))

print("Symmetric Difference:", set1.symmetric_difference(set2))

Output:
Set Operations

Original Set: {1, 2, 3, 4, 5}

After add: {1, 2, 3, 4, 5, 6}

After remove: {1, 2, 4, 5, 6}

After discard (10): {1, 2, 4, 5, 6}

Union: {1, 2, 3, 4, 5}

Intersection: {3}

Difference: {1, 2}

Symmetric Difference: {1, 2, 4, 5}

10. PLOT Y = X
Numpy :-
Syntax:

import numpy as np

Description:

NumPy is a powerful library for numerical computing in Python. It provides support for large, multi-
dimensional arrays and matrices, along with a collection of mathematical functions to operate on them
efficiently. The common alias np is used for convenience.

Code:
import matplotlib.pyplot as plt

import numpy as np

x = np.linspace(-10, 10)

y=x

plt.plot(x, y, label='y = x', color='blue')

plt.xlabel('x')
plt.ylabel('y')

plt.title('Plot of y = x')

plt.grid(True)

plt.show()

Output:

11. PLOT Y = SIN(X)

Matplotlib:-
Syntax:

import matplotlib.pyplot as plt

Description:

Matplotlib is a plotting library for Python that provides a variety of tools to create static, animated, and
interactive visualizations. pyplot is a commonly used module within matplotlib for creating plots and charts,
and it's typically imported as plt.

Code:
import numpy as np

import matplotlib.pyplot as plt

dx = 0.01
x = np.arange(0, 2 * np.pi, dx)

y = np.sin(x)

plt.plot(x, y, label='y = sin(x)', color='blue')

plt.xlabel('x')

plt.ylabel('y')

plt.title('Plot of y = sin(x)')

plt.legend()

plt.grid(True)

plt.show()

Output:

12.PIE CHAT
Pie:-
Syntax:

plt.pie(sizes, labels=labels, autopct='%1.1f%%', startangle=90)

Description:
The pie() function in matplotlib creates a pie chart. It takes a list of sizes representing the portions of each pie
slice, and labels to name each slice. Optional parameters like autopct display the percentage on each slice, and
startangle rotates the chart for better visualization.

Code:
import matplotlib.pyplot as plt

labels = ['Category A', 'Category B', 'Category C', 'Category D']

values = [25, 35, 20, 20]

plt.pie(values, labels=labels, colors=['gold', 'skyblue', 'lightgreen', 'salmon'])

plt.title('Simple Pie Chart')

plt.legend()

plt.show()

Output:

13. BARGRAPH
Bar:-
Syntax:

plt.bar(x, height, width=0.8, align='center')

Description:

The bar() function in matplotlib creates a bar chart. It takes the x positions of the bars and their corresponding
height values. Optional parameters like width control the thickness of the bars, and align determines how the
bars are aligned along the x-axis.

Code:
import matplotlib.pyplot as plt

categories = ['A', 'B', 'C', 'D']

values = [5, 7, 3, 8]

plt.bar(categories, values, color='skyblue')

plt.xlabel('Categories')

plt.ylabel('Values')

plt.title('Simple Bar Chart')

plt.legend()

plt.show()

Output:
 2.Algorithm for Breadth First Search (BFS)

ALGORITHM:-
1. Initialize a queue and mark the starting node as visited.

2. Enqueue the starting node into the queue.–

3. While the queue is not empty:

o Dequeue a node from the front of the queue.

o Visit the node and process it.

o For each unvisited neighbor of the current node:

 Mark the neighbor as visited.

 Enqueue the neighbor into the queue.

FLOWCHART:-
DESCRIPTION :-
deque in module collections :-

class deque(builtins.object)

deque([iterable[, maxlen]]) --> deque object

A list-like sequence optimized for data accesses near its endpoints.

dict object :-

class dict(object)

dict() -> new empty dictionary

dict(mapping) -> new dictionary initialized from a mapping object's

(key, value) pairs

dict(iterable) -> new dictionary initialized as if via:

d = {}

class set in module builtins :-

class set(object)

set() -> new empty set object

set(iterable) -> new set object

Build an unordered collection of unique elements.

add( ) :-

(method) def add(

element: str,
/
) -> None

Add an element to a set.

This has no effect if the element is already present.

append( ) :-

(method) def append(

x: str,
/
) -> None

PROGRAM 1:-
from collections import deque

# Example graph represented as an adjacency list

graph = {
 'A': ['B', 'C'],

'B': ['A', 'D', 'E'],

'C': ['A', 'F'],

'D': ['B'],

'E': ['B', 'F'],

'F': ['C', 'E']

# Initialize the starting node and data structures

start = 'A'

queue = deque([start]) # Create a queue and enqueue the start node

visited = set([start]) # Create a set to track visited nodes

# Perform BFS

while queue:

node = queue.popleft() # Dequeue a node from the front of the queue

print(node, end=" ") # Process the node (here we print it)

# Explore the neighbors of the current node

for neighbor in graph[node]:

if neighbor not in visited:

visited.add(neighbor) # Mark the neighbor as visited

queue.append(neighbor) # Enqueue the neighbor

OUTPUT :-
ABCDEF

PROGRAM 2:-
from collections import deque

# Example graph represented as an adjacency list

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

'B': [ 'E','F'],

'C': ['G','H'],

'D': ['I'],

'E': ['J','K'],

'F': [],

'G': ['L'],

'H': [],

'I': ['M'],

'J': [],

'K': ['N'],

'L': [],

'M': [],

'N': []

# Initialize the starting node and data structures

start = 'A'

queue = deque([start]) # Create a queue and enqueue the start node

visited = set([start]) # Create a set to track visited nodes

# Perform BFS

while queue:

node = queue.popleft() # Dequeue a node from the front of the queue

print(node, end=" ") # Process the node (here we print it)

# Explore the neighbors of the current node

for neighbor in graph[node]:

if neighbor not in visited:

visited.add(neighbor) # Mark the neighbor as visited

queue.append(neighbor) # Enqueue the neighbor

OUTPUT :-
ABCDEFGHIJKLMN

PROGRAM 3:-
from collections import deque

# Example graph represented as an adjacency list

graph = {

'A': ['B', 'C','D'],

'B': [ 'E','F'],

'C': ['G','H'],

'D': ['I'],

'E': ['J','K'],

'F': [],

'G': ['L'],

'H': [],

'I': ['M'],

'J': [],

'K': ['N'],

'L': [],

'M': [],

'N': []

# Initialize the starting node and data structures

start = 'A'

GOAL='G'

queue = deque([start]) # Create a queue and enqueue the start node

visited = set([start]) # Create a set to track visited nodes

# Perform BFS
while queue:

node = queue.popleft() # Dequeue a node from the front of the queue

print(node, end=" ") # Process the node (here we print it)

if(node==GOAL): # Check if the node is the goal

break

# Explore the neighbors of the current node

for neighbor in graph[node]:

if neighbor not in visited:

visited.add(neighbor) # Mark the neighbor as visited

queue.append(neighbor) # Enqueue the neighbor

Output :-
ABCDEFG

PROGRAM 4 :-
from collections import deque

# Function to take graph input from the user

def input_graph():

graph = {}

num_nodes = int(input("Enter the number of nodes in the graph: "))

for _ in range(num_nodes):

node = input("Enter the node: ")

neighbors = input(f"Enter the neighbors of {node} separated by spaces: ").split()

graph[node] = neighbors

return graph

# Get graph and goal node from the user

graph = input_graph()

start = input("Enter the start node: ")

GOAL = input("Enter the goal node: ")

# Initialize the BFS data structures

queue = deque([start]) # Create a queue and enqueue the start node

visited = set([start]) # Create a set to track visited nodes

# Perform BFS

found = False

while queue:

node = queue.popleft() # Dequeue a node from the front of the queue

print(node, end=" ") # Process the node (here we print it)

if node == GOAL: # Check if the node is the goal

found = True

print("\nGoal node found!")

break

# Explore the neighbors of the current node

for neighbor in graph[node]:

if neighbor not in visited:

visited.add(neighbor) # Mark the neighbor as visited

queue.append(neighbor) # Enqueue the neighbor

if not found:

print("\nGoal node not found in the graph.")

OUTPUT :-
Enter the number of nodes in the graph: 5

Enter the node: A

Enter the neighbors of A separated by spaces: B C

Enter the node: B

Enter the neighbors of B separated by spaces: D E

Enter the node: C

Enter the neighbors of C separated by spaces:

Enter the node: D

Enter the neighbors of D separated by spaces:

Enter the node: E

Enter the neighbors of E separated by spaces:

Enter the start node: A

Enter the goal node: E

ABCDE

Goal node found!

_____________________________________________
 3.Algorithm for Depth First Search (DFS)
ALGORITHM:-

1. Start with an initial node (source).

2. Use a stack to keep track of nodes to visit.
3. Mark nodes as visited to avoid revisiting.
4. While the stack is not empty:
o Pop a node from the stack.
o Process the node (e.g., print or store it).
o Push all its unvisited neighbors onto the stack in reverse order.
5. End when all nodes are visited..
FLOWCHART:-

DESCRIPTION :-
reversed :-

class reversed(
sequence: Reversible[_T@reversed],
/
)

Return a reverse iterator over the values of the given sequence.

dict object(graph) :-

class dict(object)
 dict() -> new empty dictionary

dict(mapping) -> new dictionary initialized from a mapping object's

(key, value) pairs

dict(iterable) -> new dictionary initialized as if via:

d = {}

class set in module builtins :-

class set(object)

set() -> new empty set object

set(iterable) -> new set object

Build an unordered collection of unique elements.

add( ) :-

(method) def add(

element: str,
/
) -> None

Add an element to a set.

This has no effect if the element is already present.

append( ) :-

(method) def append(

x: str,
/
) -> None

Pop( ) :-

(method) def pop(

index: SupportsIndex = -1,
/
) -> str

Remove and return item at index (default last).

Raises IndexError if list is empty or index is out of range.

PROGRAM 1:-
graph = {

'A': ['B', 'C', 'D'],

'B': ['E', 'F'],

'C': ['G'],

'D': [],

'E': [],

'F': [],

'G': []

# Initialize

start_node = 'A'

visited = set() # To track visited nodes

stack = [start_node] # Stack to store nodes to visit

# Depth First Search (without recursion)

print("DFS Traversal Order:")

while stack:

current_node = stack.pop() # Get the last added node

if current_node not in visited:

print(current_node, end=" ") # Process the current node

visited.add(current_node) # Mark as visited

# Add neighbors in reverse order to maintain the correct order

for neighbor in reversed(graph[current_node]):

if neighbor not in visited:

stack.append(neighbor)

Output :-
DFS Traversal Order:

ABEFCGD
PROGRAM 2:-
graph = {

'A': ['B', 'C','D'],

'B': [ 'E','F'],

'C': ['G','H'],

'D': ['I'],

'E': ['J','K'],

'F': [],

'G': ['L'],

'H': [],

'I': ['M'],

'J': [],

'K': ['N'],

'L': [],

'M': [],

'N': []

# Initialize

start_node = 'A'

visited = set() # To track visited nodes

stack = [start_node] # Stack to store nodes to visit

# Depth First Search (without recursion)

print("DFS Traversal Order:")

while stack:

current_node = stack.pop() # Get the last added node

if current_node not in visited:

print(current_node, end=" ") # Process the current node

visited.add(current_node) # Mark as visited

# Add neighbors in reverse order to maintain the correct order

 for neighbor in reversed(graph[current_node]):

if neighbor not in visited:

stack.append(neighbor)

OUTPUT :-
DFS Traversal Order:

ABEJKNFCGLHDIM

PROGRAM 3:-
# Graph represented as an adjacency list

graph = {

'A': ['B', 'C', 'D'],

'B': ['E', 'F'],

'C': ['G'],

'D': [],

'E': [],

'F': [],

'G': []

# Initialize

start_node = 'A'

goal='E'

visited = set() # To track visited nodes

stack = [start_node] # Stack to store nodes to visit

# Depth First Search (without recursion)

print("DFS Traversal Order:")

while stack:

current_node = stack.pop() # Get the last added node

if current_node not in visited:

print(current_node, end=" ") # Process the current node

visited.add(current_node) # Mark as visited

if(current_node==goal): # Check if the node is the goal

 break

# Add neighbors in reverse order to maintain the correct order

for neighbor in reversed(graph[current_node]):

if neighbor not in visited:

stack.append(neighbor)

OUTPUT :-
DFS Traversal Order:

ABE

PROGRAM 4 :-
def get_graph():

graph = {}

print("Enter the adjacency list of the graph (format: node: neighbor1 neighbor2 ...). Enter 'done' to finish:")

while True:

line = input().strip()

if line.lower() == 'done':

break

parts = line.split(":")

if len(parts) != 2:

print("Invalid format. Please use the format: node: neighbor1 neighbor2 ...")

continue

node = parts[0].strip()

neighbors = parts[1].split()

graph[node] = neighbors

return graph

# Get user input for the start and goal nodes

def get_start_and_goal():

start_node = input("Enter the start node: ").strip()

goal_node = input("Enter the goal node: ").strip()

return start_node, goal_node

# Perform DFS

print("Depth First Search (DFS)")

graph = get_graph()

start_node, goal_node = get_start_and_goal()

visited = set()

stack = [start_node]

print("\nDFS Traversal Order:")

while stack:

current_node = stack.pop()

if current_node not in visited:

print(current_node, end=" ")

visited.add(current_node)

if current_node == goal_node:

print("\nGoal node reached!")

break

for neighbor in reversed(graph.get(current_node, [])):

if neighbor not in visited:

stack.append(neighbor)

else:

print("\nGoal node not found.")

OUTPUT :-
Depth First Search (DFS)

Enter the adjacency list of the graph (format: node: neighbor1 neighbor2 ...). Enter 'done' to finish:

A:B C

B:D E

C:F G

D:

E:

F:
G:

DONE

Enter the start node: A

Enter the goal node: G

DFS Traversal Order:

ABDECFG

Goal node reached!

___________________________________________________________________________

4.Algorithm for Best-First Search

ALGORITHM:-
1. Create a priority queue pq and add the start node with its heuristic value.

2. Create an empty set visited to track visited nodes.

3. Create a list path to store the traversal order.

 4. While pq is not empty:

 Dequeue the node current with the lowest heuristic value from pq.

 If current is the goal, stop and return path.

 Add current to visited and path.

 For each neighbor of current:

 If the neighbor is not in visited:

 Add it to pq with its heuristic value.

FLOWCHART:-
priority queue:-
Syntax:

Using queue.PriorityQueue (built-in module):

import queue

pq = queue.PriorityQueue()

pq.put((priority, item)) # Insert element with priority

priority, item = pq.get() # Remove element with the highest priority

Using heapq (alternative approach):

import heapq

pq = []

heapq.heappush(pq, (priority, item)) # Insert element with priority

priority, item = heapq.heappop(pq) # Remove element with the highest priority

Description:

A priority queue is a data structure where elements are dequeued based on their priority instead of their
insertion order. Lower numerical values indicate higher priority by default. The queue.PriorityQueue class
provides a thread-safe implementation, while heapq provides a lightweight heap-based alternative.

Continue:-
Syntax:

for i in range(5):

if i == 2:

continue # Skip the rest of the loop body for this iteration

print(i)

Description:

The continue statement is used inside loops to skip the current iteration and move to the next iteration
immediately, without executing the remaining code in the loop body.

PROGRAM :-

import heapq

# Graph represented as an adjacency list

graph = {

0: [1, 2],

1: [0, 3, 4],

2: [0, 5],

3: [1],

4: [1],

5: [2]

# Heuristic values for each node

heuristic = {

0: 10,

1: 8,

2: 5,

3: 7,

4: 3,

5: 0 # Assuming node 5 is the goal

# Initialization

start_node = 0

goal_node = 5
priority_queue = []

heapq.heappush(priority_queue, (heuristic[start_node], start_node)) # (heuristic, node)

visited = set()

path = []

# Best-First Search

while priority_queue:

# Get the node with the smallest heuristic value

_, current = heapq.heappop(priority_queue)

if current in visited:

continue

# Mark the current node as visited and add it to the path

visited.add(current)

path.append(current)

# If the goal is reached, stop

if current == goal_node:

break

# Add neighbors to the priority queue

 for neighbor in graph[current]:

if neighbor not in visited:

heapq.heappush(priority_queue, (heuristic[neighbor], neighbor))

# Output the result

print("Best-First Search Traversal:", path)

OUTPUT :-

Best-First Search Traversal: [0, 2, 5]

__________________________________________________________________________________________
 5.Algorithm for A* Search
Inputs:

1. Graph: A tree with nodes and edges where each edge has a cost.

2. Start node: The initial node where the search begins.

3. Goal node: The destination node that we want to reach.

4. Heuristic: A heuristic function or pre-defined values estimating the cost from each node to the goal
node.

Outputs:

 The optimal path from the start node to the goal node, or a message saying no path exists.

ALGORITHM:-
1. Initialization:

o Define the open list: A priority queue (min-heap) which will hold nodes that need to be
evaluated.

o Define the closed list: A set to keep track of nodes that have already been evaluated.

o Define Actual cost(g-cost) for each node, which represents the cost from the start node to
the current node.

o Define heuristic values(h value) for each node, which estimate the cost from that node to the
goal node.

2. Start:

o Add the start node to the open list with its F Value.

3. Main Loop:

o While the open list is not empty:

1. Select the node from the open list that has the lowest F Value. This node is the most
promising candidate for exploration.

2. If this node is the goal node, the search is complete. Reconstruct the path from the
goal node back to the start node.

3. Otherwise, move the current node from the open list to the closed list, marking it as
explored.

4. Explore each neighbor of the current node:

 For each neighbor, calculate the tentative g-cost: the cost to reach that
neighbor through the current node.

 If the neighbor has not been evaluated (i.e., it’s not in the closed list), or if a
better path to that neighbor is found (i.e., the tentative g-value is lower
than the current g-value), then:
  Update the g-value for that neighbor.

 Calculate the new F value.

 If the neighbor is not already in the open list, add it.

4. Termination:

o If the goal node is found, return the reconstructed path.

o If the open list becomes empty and no path to the goal node is found, return that no path
exists.

FLOWCHART:-
heap-based priority queue:-
Syntax:

import heapq

# Creating a min-heap

heap = []

heapq.heappush(heap, 3)

heapq.heappush(heap, 1)

heapq.heappush(heap, 2)

# Removing the smallest element

smallest = heapq.heappop(heap)

Description:

The heapq module provides a heap-based priority queue in Python. It implements a min-heap by default, where
the smallest element is always at the root. It allows efficient insertion and removal of the smallest element in
O(log n) time.

PROGRAM :-
import heapq

# Node and heuristic setup

start = "A" # Starting node

goal = "G" # Goal node

nodes = {

"A": {"B": 1, "C": 4}, # A has children B and C, costs 1 and 4 respectively

"B": {"D": 2, "E": 5}, # B has children D and E, costs 2 and 5 respectively

"C": {"E": 1}, # C has child E, cost 1

"D": {"G": 3}, # D has child G, cost 3

"E": {"G": 1}, # E has child G, cost 1

"G": {} # G has no children, it's the goal

}
# Heuristic values (estimated cost to reach the goal)

heuristic = {

"A": 6, # Estimated cost to reach G from A

"B": 5,

"C": 2,

"D": 1,

"E": 1,

"G": 0 # The goal node has a heuristic of 0

# Open list (priority queue) and closed list

open_list = []

closed_list = set()

# Starting node setup

heapq.heappush(open_list, (heuristic[start], 0, start)) # (f_score, g_score, node)

g_score = {start: 0} # Starting node has a g_score of 0

came_from = {} # To reconstruct the path

while open_list:

# Pop the node with the lowest f_score

current_f, current_g, current_node = heapq.heappop(open_list)

# If the current node is the goal, reconstruct the path

if current_node == goal:

path = []

while current_node in came_from:

path.append(current_node)

current_node = came_from[current_node]

path.append(start)

path.reverse()
 print("Path found:", path)

break

closed_list.add(current_node)

# Explore neighbors

for neighbor, cost in nodes[current_node].items():

if neighbor in closed_list:

continue

tentative_g_score = current_g + cost

# If the neighbor is not in the open list or we found a better path to it

if neighbor not in g_score or tentative_g_score < g_score[neighbor]:

g_score[neighbor] = tentative_g_score

f_score = tentative_g_score + heuristic[neighbor]

heapq.heappush(open_list, (f_score, tentative_g_score, neighbor))

came_from[neighbor] = current_node

else:

print("No path found.")

OUTPUT :-
Path found: ['A', 'B', 'D', 'G']

___________________________________________________________________________
 6.Constraint Satisfaction Problem ( CSP )

CSP (Constraint Satisfaction Problem) is a mathematical framework used in computer

science and artificial intelligence to solve problems that require finding values for variables
under given constraints. A CSP consists of:

1. Variables – The elements that need to be assigned values.

2. Domains – The possible values that each variable can take.

3. Constraints – The rules or conditions that restrict the values the variables can take.

CSPs are commonly used in scheduling, planning, optimization, and artificial intelligence
applications such as Sudoku, map coloring, and the N-Queens problem. Popular solving
techniques include backtracking, constraint propagation, and heuristic search algorithms
like AC-3 and Min-Conflicts.

Algorithm for Graph Coloring (CSP) Using Backtracking:-

Step 1: Define the Problem

 Define the number of vertices VVV in the graph.

 Define the adjacency matrix representing the graph.

 Define the number of colors mmm.

Step 2: Initialize Variables

 Create a list colors of size VVV initialized with -1 to represent uncolored vertices.

Step 3: Check Safety Condition (is_safe Function)

 Check if assigning a specific color to a vertex is valid by ensuring no adjacent vertex has the same
color.

Step 4: Recursive Backtracking (graph_coloring Function)

 If all vertices are assigned a color, return True (solution found).

 Try assigning each color from 0 to m-1 to the current vertex:

o If it is safe to assign a color, assign it and move to the next vertex.

o If assigning a color leads to a dead end, backtrack by removing the assigned color and trying
the next one.

 If no valid color is found for a vertex, return False (no solution).

Step 5: Start the Coloring Process

 Call graph_coloring() starting from vertex 0.

  If a solution is found, print the assigned colors; otherwise, print "No solution exists."

PROGRAM :-
# Define the number of vertices in the graph

V=4

# Adjacency matrix representing the graph

# 0 means no edge, 1 means there is an edge

graph = [

[0, 1, 1, 0], # Node 0 is connected to nodes 1 and 2

[1, 0, 1, 1], # Node 1 is connected to nodes 0, 2, and 3

[1, 1, 0, 1], # Node 2 is connected to nodes 0, 1, and 3

[0, 1, 1, 0] # Node 3 is connected to nodes 1 and 2

# Number of colors

m = 3 # We are trying to use at most 3 colors

# List to store the color assigned to each vertex

colors = [-1] * V # -1 indicates that no color has been assigned yet

# Backtracking algorithm to assign colors to the vertices

def is_safe(vertex, color, colors, graph):

# Check all adjacent vertices to ensure no adjacent vertex has the same color

for i in range(V):

if graph[vertex][i] == 1 and colors[i] == color:

return False

return True

def graph_coloring(graph, m, colors, vertex):

# Base case: if all vertices are assigned a color, return True

 if vertex == V:

return True

# Try different colors for vertex

for color in range(m):

if is_safe(vertex, color, colors, graph):

colors[vertex] = color # Assign color to vertex

# Recur to assign colors to the next vertex

if graph_coloring(graph, m, colors, vertex + 1):

return True

# If assigning color does not lead to a solution, backtrack

colors[vertex] = -1

return False # If no color can be assigned to this vertex, return False

# Start coloring the graph

if graph_coloring(graph, m, colors, 0):

# Print the solution if found

print("Solution found:")

for vertex in range(V):

print(f"Vertex {vertex} -> Color {colors[vertex]}")

else:

print("No solution exists.")

OUTPUT :-
Solution found:

Vertex 0 -> Color 0

Vertex 1 -> Color 1

Vertex 2 -> Color 2

Vertex 3 -> Color 0

 7.Mean-End Analysis (MEA)

Mean-End Analysis (MEA) is a problem-solving technique used in artificial intelligence and cognitive
psychology. It is a heuristic method that breaks down a complex problem into smaller, more manageable
subproblems to achieve a goal.

How MEA Works:

1. Identify the initial state (current situation) and the goal state (desired outcome).

2. Determine the difference between the two states.

3. Choose an operator (action) that reduces this difference.

4. Apply the operator and update the current state.

5. Repeat the process until the goal state is reached.

Applications of MEA:

 Artificial Intelligence (AI): Used in automated planning and problem-solving systems.

 Cognitive Science: Helps explain how humans solve problems.

 Robotics: Assists in path planning and decision-making.

 Game Development: Used in AI-driven decision-making in games.

Algorithm for Mean-End Analysis (MEA) Robot Navigation in a Grid

Step 1: Initialize Grid and Variables

1. Define the grid size (GRID_SIZE = 5).

2. Set the initial position of the robot (current_position = [0, 0]).

3. Define the goal position (goal_position = [4, 4]).

Step 2: Loop Until the Goal is Reached

4. Repeat the following steps until current_position == goal_position:

o Print the current position and the goal position.

o Compute the difference between the current and goal positions:

 x_diff = goal_x - current_x

 y_diff = goal_y - current_y

Step 3: Apply MEA to Move Towards the Goal

5. Choose the movement direction based on the larger difference:

 o If |x_diff| > |y_diff|:

 Move right if x_diff > 0 (current_x += 1).

 Move left if x_diff < 0 (current_x -= 1).

o Otherwise:

 Move down if y_diff > 0 (current_y += 1).

 Move up if y_diff < 0 (current_y -= 1).

Step 4: Update and Print Grid

6. Create a new grid (5x5 with '.' representing empty cells).

7. Mark the robot’s position ('R') in the grid.

8. Print the updated grid after each move.

Step 5: End Condition

9. Once current_position == goal_position, print "Goal reached!" with the final position.

PROGRAM :-
# Grid dimensions (5x5)

GRID_SIZE = 5

# Initial Position of the robot

current_position = [0, 0] # Robot starts at (0, 0)

goal_position = [4, 4] # Goal is at (4, 4)

# Loop until the robot reaches the goal

while current_position != goal_position:

# Print the current position and goal position

print("Current Position:", current_position)

print("Goal Position:", goal_position)

# Calculate the difference in x and y coordinates

x_diff = goal_position[0] - current_position[0]

y_diff = goal_position[1] - current_position[1]

# Choose action to minimize the most significant difference

 if abs(x_diff) > abs(y_diff):

if x_diff > 0:

current_position[0] += 1 # Move right

elif x_diff < 0:

current_position[0] -= 1 # Move left

else:

if y_diff > 0:

current_position[1] += 1 # Move down

elif y_diff < 0:

current_position[1] -= 1 # Move up

# Print the grid after each move

grid = [['.' for _ in range(GRID_SIZE)] for _ in range(GRID_SIZE)]

x, y = current_position

grid[x][y] = 'R'

for row in grid:

print(" ".join(row))

print("\n")

# Print final goal reached

print("Goal reached at:", current_position)

OUTPUT :-
Current Position: [0, 0]

Goal Position: [4, 4]

.R...

.....

.....

.....

.....

Current Position: [0, 1]

Goal Position: [4, 4]

.....

.R...

.....

.....

.....

Current Position: [1, 1]

Goal Position: [4, 4]

.....

..R..

.....

.....

.....

Current Position: [1, 2]

Goal Position: [4, 4]

.....

.....

..R..

.....

.....

Current Position: [2, 2]

Goal Position: [4, 4]

.....

.....

...R.

.....

.....

Current Position: [2, 3]

Goal Position: [4, 4]

.....

.....
.....

...R.

.....

Current Position: [3, 3]

Goal Position: [4, 4]

.....

.....

.....

....R

.....

Current Position: [3, 4]

Goal Position: [4, 4]

.....

.....

.....

.....

....R

Goal reached at: [4, 4]

__________________________________________________________________________________________

NAME : Bijaya kumar rout

REG. NO. : 2301292452
SECTION : A
BRANCH : CSE (AIML)

THE END