AIM:

To write a python program to implement Fibonacci number using Recursion.

ALGORITHM:
● The Fibonacci function takes an integer n as input and returns the nth
Fibonacci number.
● It uses recursion to calculate the Fibonacci number based on the algorithm
you provided.

[Link]: 1
IMPLEMENTATION OF FIBONACCI NUMBER
USING RECURSION

PROGRAM:
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
# Example usage
n = int(input("Enter the value of n for Fibonacci series: "))
result = fibonacci(n)
print(f"The {n}th Fibonacci number is: {result}")

OUTPUT
Enter the value of n for Fibonacci series: 8
The 8th Fibonacci number is: 21
RESULT:
Thus the python program to implement Fibonacci number using Recursion was
written,
executed and Verified successfully.
AIM:
To write a python program to implement Fibonacci number using Iteration.
ALGORITHM:
● The Node class represents a node in the binary tree.
● The preorder function performs a preorder traversal of the binary tree and
prints the data of each node.
[Link]: 2
IMPLEMENTATION OF FIBONACCI NUMBER
USING ITERATION

PROGRAM:
class Node:
def __init__(self, key):
[Link] = key
[Link] = [Link] = None
def preorder(root):
if root is not None:
print([Link], end=" ")
preorder([Link])
preorder([Link])
# Example usage
root = Node(1)
[Link] = Node(2)
[Link] = Node(3)
[Link] = Node(4)
[Link] = Node(5)
[Link] = Node(6)
[Link] = Node(7)
[Link] = Node(8)
print("Preorder Traversal:")
preorder(root)
5

OUTPUT
Preorder Traversal:
12435786
RESULT:
Thus the python program to implement Fibonacci number using Recursion was
written,
executed and Verified successfully.
AIM:
To write a python program to implement merge sort analysis.
ALGORITHM:
● The merge_sort function recursively divides the array into halves until it
contains only one element.
● The merge function is responsible for merging two sorted halves into a single
sorted array.
PROGRAM:

[Link]: 3a
IMPLEMENTATION OF MERGE SORT
ANALYSIS
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2 # Calculate the middle index
# Divide the array into two halves
left_half = arr[:mid]
right_half = arr[mid:]
# Recursive calls to sort each half
merge_sort(left_half)
merge_sort(right_half)
# Merge the sorted halves
merge(arr, left_half, right_half)
def merge(arr, left, right):
i=j=k=0
# Compare elements from left and right halves and merge in sorted order
while i < len(left) and j < len(right):
if left[i] < right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1
# Copy the remaining elements from left and right halves, if any
while i < len(left):
arr[k] = left[i]
i += 1
k += 1
while j < len(right):
arr[k] = right[j]
j += 1
k += 1
# Example usage and analysis
arr = [38, 27, 43, 3, 9, 82, 10]
print("Original array:", arr)
merge_sort(arr)
print("Sorted array:", arr)
OUTPUT
Original array: [38, 27, 43, 3, 9, 82, 10]
Sorted array: [3, 9, 10, 27, 38, 43, 82]
RESULT:
Thus the python program to implement Fibonacci number using Recursion was
written,
executed and Verified successfully.

AIM:
To write a python program to implement merge sort analysis.
ALGORITHM:
● The quick_sort function recursively applies the quicksort algorithm.
● It chooses a pivot element from the array, partitions the array into elements
smaller than the pivot, equal to the pivot, and greater than the pivot, and then
recursively sorts the subarrays.

[Link]: 3b
IMPLEMENTATION OF QUICK SORT
ANALYSIS

PROGRAM:
def quick_sort(arr):
if len(arr) <= 1:
return arr # Base case: already sorted if the array has 0 or 1 element
else:
pivot = arr[len(arr) // 2] # Choose the middle element as the pivot
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# Example usage and analysis
arr = [38, 27, 43, 3, 9, 82, 10]
print("Original array:", arr)
sorted_array = quick_sort(arr)
print("Sorted array:", sorted_array)

OUTPUT
Original array: [38, 27, 43, 3, 9, 82, 10]
Sorted array: [3, 9, 10, 27, 38, 43, 82]
RESULT:
Thus the python program to implement Fibonacci number using Recursion was
written,
executed and Verified successfully.

AIM:
To write a python program for implementing Binary Search Tree.
ALGORITHM:
● The Node class represents a node in the binary search tree.
● The insert function inserts a new node into the BST based on the given key.
● The search function searches for a key in the BST and returns the node if
found.

[Link]: 4
Date:
IMPLEMENTATION OF BINARY SEARCH TREE

PROGRAM:
class Node:
def __init__(self, key):
[Link] = key
[Link] = [Link] = None
def insert(root, key):
if root is None:
return Node(key)
else:
if key < [Link]:
[Link] = insert([Link], key)
elif key > [Link]:
[Link] = insert([Link], key)
return root
def search(root, key):
if root is None or [Link] == key:
return root
if key < [Link]:
return search([Link], key)
return search([Link], key)
# Example usage and testing
root = None
keys = [50, 30, 20, 40, 70, 60, 80]
for key in keys:
root = insert(root, key)
search_key = int(input("Enter the search element: "))
result = search(root, search_key)
if result:
print(f"Element {search_key} found in the BST.")
else:
print(f"Element {search_key} not found in the BST.")

OUTPUT
Enter the search element: 60
Element 60 found in the BST.
.
RESULT:
Thus the implementation of Binary Search tree was written, executed and verified
successfully.
AIM:
To write a python program to implement Red-Black Tree.
ALGORITHM:
● The insert method is used to insert elements into the Red-Black Tree.
● The inorder_traversal method is used to visualize the Red-Black Tree using
inorder traversal.
[Link]: 5
RED BLACK TREE IMPLEMENTATION

PROGRAM:
class Node:
def __init__(self, key, color='R'):
[Link] = key
[Link] = [Link] = [Link] = None
[Link] = color
class RedBlackTree:
def __init__(self):
[Link] = Node(None, 'B') # NIL represents a null node
[Link] = [Link]
def insert(self, key):
# Step 1: Check whether the tree is empty
if [Link] == [Link]:
[Link] = Node(key, 'B') # Insert the newNode as the root with color Black
else:
# Step 2: Insert the newNode as a leaf node with Red color
new_node = Node(key, 'R')
self._insert(new_node)
def _insert(self, node):
y = None
x = [Link]
# Perform a regular binary search tree insert
while x != [Link]:
y=x
if [Link] < [Link]:
x = [Link]
else:
x = [Link]
[Link] = y
if y == None:
[Link] = node
elif [Link] < [Link]:
[Link] = node
else:
[Link] = node
# Insert may violate the Red-Black Tree properties, fix it
self._insert_fixup(node)
def _insert_fixup(self, node):
while [Link] and [Link] == 'R':
if [Link] == [Link]:
y = [Link]
if y and [Link] == 'R':
[Link] = 'B'
[Link] = 'B'
[Link] = 'R'
node = [Link]
else:
if node == [Link]:
node = [Link]
self.left_rotate(node)
[Link] = 'B'
[Link] = 'R'
self.right_rotate([Link])
else:
y = [Link]
if y and [Link] == 'R':
[Link] = 'B'
[Link] = 'B'
[Link] = 'R'
node = [Link]
else:
if node == [Link]:
node = [Link]
self.right_rotate(node)
[Link] = 'B'
[Link] = 'R'
self.left_rotate([Link])
[Link] = 'B' # Ensure the root is black
def left_rotate(self, x):
y = [Link]
[Link] = [Link]
if [Link] != [Link]:
[Link] = x
[Link] = [Link]
if [Link] == None:
[Link] = y
elif x == [Link]:
[Link] = y
else:
[Link] = y
[Link] = x
[Link] = y
def right_rotate(self, x):
y = [Link]
[Link] = [Link]
if [Link] != [Link]:
[Link] = x
[Link] = [Link]
if [Link] == None:
[Link] = y
elif x == [Link]:
[Link] = y
else:
[Link] = y
[Link] = x
[Link] = y
def inorder_traversal(self, node):
if node != [Link]:
self.inorder_traversal([Link])
print(f'{[Link]} ({[Link]}) ', end='')
self.inorder_traversal([Link])
# Example usage
rb_tree = RedBlackTree()
keys = [50, 30, 20, 40, 70, 60, 80]
for key in keys:
rb_tree.insert(key)
print("Inorder Traversal of Red-Black Tree:")
rb_tree.inorder_traversal(rb_tree.root)

OUTPUT
Inorder Traversal of Red-Black Tree:
20 (B) 30 (B) 40 (R) 50 (B) 60 (R) 70 (B) 80 (R)
RESULT:
Thus the python program to implement Red Black Tree was executed and verified
successfully.

AIM:
To write a python program for heap implementation.
ALGORITHM:
● buildMaxHeap() is used to convert the array into a max heap.
● heapify() is a helper function to maintain the heap property during the build
process.
● heapSort() is the main sorting function that uses the max heap structure.

[Link]: 6
HEAP IMPLEMENTATION

PROGRAM:
def buildMaxHeap(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
# Build max heap
buildMaxHeap(arr)
# Extract elements one by one
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # Swap
heapify(arr, i, 0)
# Example usage and result
arr = [12, 11, 13, 5, 6, 7]
print("Original array:", arr)
heapSort(arr)
print("Sorted array:", arr)

OUTPUT
Original array: [12, 11, 13, 5, 6, 7]
Sorted array: [5, 6, 7, 11, 12, 13]
RESULT:
Thus the heap implementation was written, executed and verified successfully.

AIM:
To write a python program for Fibonacci heap implement.
ALGORITHM:
Initialization:
● FibonacciNode class represents a node in the Fibonacci Heap.
● FibonacciHeap class represents the Fibonacci Heap itself.
● Each node has a key, degree, marked status, references to child, parent,
next, and prev nodes.
● The heap has a min_node representing the minimum node and keeps
track of the number of nodes.
Insertion (insert method):
● Inserts a new node with the given key into the heap.
● If the heap is empty, the new node becomes the min_node.
● Otherwise, the new node is linked into the circular doubly linked list
using the _link method, and if its key is smaller than the current
minimum, it becomes the new minimum.
Finding Minimum (minimum method):
● Returns the key of the minimum node in the heap.
Extracting Minimum (extractMin method):
● Removes and returns the node with the minimum key from the heap.
● If the minimum node has children, they are added to the root list.
● The minimum node is removed from the root list, and consolidation is
performed using the _consolidate method to ensure that there is at
most one tree of each degree.
Decreasing Key (decreaseKey method):
● Decreases the key of a node to a new value.
● If the new key is smaller than the current key, the node is cut from its
parent and possibly marked. Cascading cuts are performed using the
_cut and _cascading_cut methods.
Deletion (delete method):
● Deletes a node from the heap by decreasing its key to negative in 昀椀 nity
and then extracting the minimum.
Union (union method):
● Merges another Fibonacci Heap with the current heap by linking their
root lists.
Linking (_link method):

[Link]: 7
FIBONACCI HEAP IMPLEMENTATION

● Links two trees of the same degree together.

Cutting (_cut method):
● Cuts the link between a child and its parent, making the child a new
root.
Cascading Cut (_cascading_cut method):
● Ensures that no tree in the heap has lost two children by performing
cascading cuts.
Consolidation (_consolidate method):
● Consolidates trees of the same degree to ensure there is at most one
tree of each degree.
Example Usage and Output:
● The code includes an example where keys are inserted into the
Fibonacci Heap, the minimum key is printed, and then keys are
extracted in increasing order.
Feel free to use this explanation as a guide for your lab report or to ask any specific
questions you might have!

PROGRAM:
class FibonacciNode:
def __init__(self, key):
[Link] = key
[Link] = 0
[Link] = False
[Link] = None
[Link] = None
[Link] = self
[Link] = self
class FibonacciHeap:
def __init__(self):
self.min_node = None
self.num_nodes = 0
def insert(self, key):
new_node = FibonacciNode(key)
if self.min_node is None:
self.min_node = new_node
else:
self._link(self.min_node, new_node)
if key < self.min_node.key:
self.min_node = new_node
self.num_nodes += 1
def minimum(self):
return self.min_node.key if self.min_node else None
def extractMin(self):
min_node = self.min_node
if min_node:
if min_node.child:
child = min_node.child
while [Link]:
next_child = [Link]
min_node.child = next_child
self._add_node(child)
[Link] = None
child = next_child
prev_node = min_node.prev
next_node = min_node.next
prev_node.next = next_node
next_node.prev = prev_node
if min_node == min_node.next:
self.min_node = None
else:
self.min_node = next_node
self._consolidate()
self.num_nodes -= 1
return min_node.key if min_node else None
def decreaseKey(self, node, new_key):
if new_key > [Link]:
raise ValueError("New key is greater than current key")
[Link] = new_key
parent = [Link]
if parent and [Link] < [Link]:
self._cut(node, parent)
self._cascading_cut(parent)
if [Link] < self.min_node.key:
self.min_node = node
def delete(self, node):
[Link](node, float('-inf'))
[Link]()
def union(self, other_heap):
if other_heap.min_node:
if self.min_node:
self._link(self.min_node, other_heap.min_node)
if other_heap.min_node.key < self.min_node.key:
self.min_node = other_heap.min_node
else:
self.min_node = other_heap.min_node
self.num_nodes += other_heap.num_nodes
def _link(self, root1, root2):
[Link] = [Link]
[Link] = [Link]
[Link] = root2
[Link] = root1
def _add_node(self, node):
[Link] = node
[Link] = node
def _cut(self, child, parent):
if [Link] == child:
[Link] = None
else:
next_child = [Link]
prev_child = [Link]
next_child.prev = prev_child
prev_child.next = next_child
if [Link] == child:
[Link] = next_child
[Link] -= 1
self._add_node(child)
[Link] = None
[Link] = False
def _cascading_cut(self, node):
parent = [Link]
if parent:
if not [Link]:
[Link] = True
else:
self._cut(node, parent)
self._cascading_cut(parent)
def _consolidate(self):
max_degree = int(self.num_nodes**0.5) + 1
degree_array = [None] * max_degree
current = self.min_node
nodes = []
while [Link](current) and current != self.min_node:
current = [Link]
for node in nodes:
degree = [Link]
while degree_array[degree]:
other = degree_array[degree]
if [Link] > [Link]:
node, other = other, node
self._link(other, node)
degree_array[degree] = None
degree += 1
degree_array[degree] = node
self.min_node = None
for degree_node in degree_array:
if degree_node:
if self.min_node:
self._link(self.min_node, degree_node)
if degree_node.key < self.min_node.key:
self.min_node = degree_node
else:
self.min_node = degree_node
# Example usage and output for lab practice
fib_heap = FibonacciHeap()
keys = [4, 3, 7, 2, 8, 1, 6, 5]
print("Inserting keys into Fibonacci Heap:", keys)
for key in keys:
fib_heap.insert(key)
print("Minimum key in the Fibonacci Heap:", fib_heap.minimum())
print("Extracting Min from the Fibonacci Heap:")
while fib_heap.minimum() is not None:
print(fib_heap.extractMin())

OUTPUT
Inserting keys into Fibonacci Heap: [4, 3, 7, 2, 8, 1, 6, 5]
Minimum key in the Fibonacci Heap: 1
Extracting Min from the Fibonacci Heap:
1
2
3
4
5
6
7
8
RESULT:
Thus the Fibonacci heap implementation was written, executed and verified
successfully.
AIM:
To write a python program to implement graph traversal by using depth first
search.
ALGORITHM:
 The Graph class uses an adjacency list to represent the graph.
 The add_edge method adds edges to the graph.
 The dfs method performs Depth First Search starting from a given node.
 A stack is used to keep track of nodes to be visited.
 The algorithm explores as far as possible along each branch before from
collections.

[Link]: 8a
GRAPH TRAVERSALS (DEPTH FIRST SEARCH)

PROGRAM:
class Graph:
def __init__(self):
[Link] = defaultdict(list)
def add_edge(self, u, v):
[Link][u].append(v)
[Link][v].append(u)
def dfs(self, start):
visited = set() # To keep track of visited nodes
stack = [start] # Stack for DFS traversal
while stack:
current_node = [Link]()
if current_node not in visited:
print(current_node, end=" ")
[Link](current_node)
# Add adjacent nodes to the stack
[Link](neighbor for neighbor in [Link][current_node] if neighbor not in
visited)
# Example Usage and Output for Lab Practice
graph = Graph()
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 4)
graph.add_edge(2, 5)
graph.add_edge(3, 6)
graph.add_edge(3, 7)
print("Depth First Search (DFS) starting from node 1:")
[Link](1)

OUTPUT:
Depth First Search (DFS) starting from node 1:
1376254
RESULT:
Thus the python program to implement graph traversal by using depth first search
was
written and verified successfully.

AIM:
To write a program to implement graph traversals by using breadth first search.
ALGORITHM:
 The Graph class uses an adjacency list to represent the graph.
 The add_edge method adds edges to the graph.
 The bfs method performs Breadth First Search starting from a given node.
 A queue is used to keep track of nodes to be visited.
 The algorithm visits all neighbors of the current node before moving on to the
next level.
PROGRAM :

[Link]: 8b
GRAPH TRAVERSALS (BREADTH FIRST SEARCH)

from collections import defaultdict, deque

class Graph:
def __init__(self):
[Link] = defaultdict(list)
def add_edge(self, u, v):
[Link][u].append(v)
[Link][v].append(u)
def bfs(self, start):
visited = set() # To keep track of visited nodes
queue = deque([start]) # Queue for BFS traversal
while queue:
current_node = [Link]()
if current_node not in visited:
print(current_node, end=" ")
[Link](current_node)
# Add adjacent nodes to the queue
[Link](neighbor for neighbor in [Link][current_node] if neighbor not in
visited)
# Example Usage and Output for Lab Practice
graph = Graph()
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 4)
graph.add_edge(2, 5)
graph.add_edge(3, 6)
graph.add_edge(3, 7)
print("Breadth First Search (BFS) starting from node 1:")
[Link](1)
OUTPUT
Breadth First Search (BFS) starting from node 1:
1234567
35

RESULT:
Thus the python program to implement graph traversal by using breadth first
search was
written, executed and verified successfully.
[Link]: 9a
SPANNING TREE IMPLEMENTATION (KRUSKAL’S ALGORITHM)

AIM:
To write a python program to implement spanning tree implementation using
kruskal s ‟
algorithm.
ALGORITHM:
 The Graph class initializes the graph with a given number of vertices.
 The add_edge method adds edges to the graph.
 The find_parent and union methods are used for 昀椀 nding the parent and
union operations in the disjoint-set data structure.
 The kruskal method implements Kruskal's algorithm to 昀椀 nd the minimum
spanning tree.
 The example usage creates a graph and 昀椀 nds the minimum spanning tree
using Kruskal's algorithm.
PROGRAM:
from collections import defaultdict, deque
class Graph:

def __init__(self):
[Link] = defaultdict(list)
def add_edge(self, u, v):
[Link][u].append(v)
[Link][v].append(u)
def bfs(self, start):
visited = set() # To keep track of visited nodes
queue = deque([start]) # Queue for BFS traversal
while queue:
current_node = [Link]()
if current_node not in visited:
print(current_node, end=" ")
[Link](current_node)
# Add adjacent nodes to the queue
[Link](neighbor for neighbor in [Link][current_node] if neighbor not in
visited)
# Example Usage and Output for Lab Practice
graph = Graph()
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 4)
graph.add_edge(2, 5)
graph.add_edge(3, 6)
graph.add_edge(3, 7)
print("Breadth First Search (BFS) starting from node 1:")
[Link](1)
OUTPUT
Minimum Spanning Tree (Kruskal's Algorithm):
Edge: 2 - 3, Weight: 4
Edge: 0 - 3, Weight: 5
Edge: 0 - 1, Weight: 10
RESULT:
Thus the Spanning tree implementation using kruskal s algorithm was written, ‟
executed and verified successfully.

AIM:
To write a python program to implement spanning tree implementation using Prim
s ‟ algorithm.
ALGORITHM:
 The Graph class initializes the graph with a given number of vertices.
 The add_edge method adds edges to the graph.
 The prim method implements Prim's algorithm to 昀椀 nd the minimum spanning
tree.
 The algorithm maintains a set of vertices (mst_set) included in the MST and
uses a min-heap to select the next vertex to be included.
 The example usage creates a graph and 昀椀 nds the weight of the minimum
spanning tree using Prim's algorithm.
PROGRAM:
import heapq

[Link]: 9b
SPANNING TREE IMPLEMENTATION (PRIM’S ALGORITHM)
class Graph:
def __init__(self, vertices):
self.V = vertices
[Link] = [[] for _ in range(vertices)]
def add_edge(self, u, v, w):
[Link][u].append((v, w))
[Link][v].append((u, w))
def prim(self):
mst_set = set()
min_heap = [(0, 0)] # (key, vertex) - heap to store vertices with their key values
total_weight = 0
key_values = [float('inf')] * self.V
key_values[0] = 0
while len(mst_set) < self.V:
key, u = [Link](min_heap)
if u not in mst_set:
mst_set.add(u)
total_weight += key
for v, weight in [Link][u]:
if v not in mst_set and weight < key_values[v]:
key_values[v] = weight
[Link](min_heap, (weight, v))
return total_weight
# Example Usage and Output for Lab Practice
g = Graph(5)
g.add_edge(0, 1, 2)
g.add_edge(0, 3, 6)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 8)
g.add_edge(1, 4, 5)
g.add_edge(2, 4, 7)
g.add_edge(3, 4, 9)
print("Minimum Spanning Tree (Prim's Algorithm) Weight:", [Link]())
OUTPUT:
Minimum Spanning Tree (Prim's Algorithm) Weight: 16

RESULT:
Thus the Spanning tree implementation using prim’s algorithm was written,
executed and verified successfully.

AIM:
To write a pythan program to implement Dijkstra s Algorithm. ‟
ALGORITHM:
 The Graph class initializes the graph with a given number of vertices.
 The add_edge method adds edges to the graph.
 The dijkstra method implements Dijkstra's algorithm to Find the shortest
distances from a given source vertex.
 The algorithm uses a min-heap to e 昀케 ciently select the next vertex with the
smallest temporary distance.
 The example usage creates a graph and 昀椀 nds the shortest distances from a
speci 昀椀 ed starting vertex.

PROGRAM:
[Link]: 10a
SHORTEST PATH ALGORITHM (DIJKSTRA’S ALGORITHM)

import heapq
class Graph:
def __init__(self, vertices):
self.V = vertices
[Link] = [[] for _ in range(vertices)]
def add_edge(self, u, v, w):
[Link][u].append((v, w))
def dijkstra(self, start):
min_heap = [(0, start)] # (distance, vertex) - heap to store vertices with their
distances
distances = [float('inf')] * self.V
distances[start] = 0
while min_heap:
dist_u, u = [Link](min_heap)
for v, weight in [Link][u]:
new_dist = dist_u + weight
if new_dist < distances[v]:
distances[v] = new_dist
[Link](min_heap, (new_dist, v))
return distances
# Example Usage and Output for Lab Practice
g = Graph(6)
g.add_edge(0, 1, 4)
g.add_edge(0, 2, 2)
g.add_edge(1, 2, 5)
g.add_edge(1, 3, 10)
g.add_edge(2, 4, 3)
g.add_edge(3, 5, 7)
g.add_edge(4, 3, 1)
g.add_edge(4, 5, 8)
start_vertex = 0
shortest_distances = [Link](start_vertex)
print(f"Shortest Distances from Vertex {start_vertex}:")
for v, dist in enumerate(shortest_distances):
print(f"To Vertex {v}: {dist}")
OUTPUT
44

Shortest Distances from Vertex 0:

To Vertex 0: 0
To Vertex 1: 4
To Vertex 2: 2
To Vertex 3: 9
To Vertex 4: 5
To Vertex 5: 16
.
RESULT:
Thus the python program to implement Dijkstra’s Algorithm was executed and
verified successfully.

AIM:
To write a python program to implement Bellmann Ford algorithm.
ALGORITHM:
 The Graph class initializes the graph with a given number of vertices.
 The add_edge method adds edges to the graph.
 The bellman_ford method implements the Bellman-Ford algorithm to 昀椀 nd the
shortest distances from a given source vertex.
 The algorithm iterates through all edges multiple times to relax the path
distances.
 It also checks for negative cycles by iterating through all edges one more
time.

[Link]: 10b
SHORTEST PATH ALGARITHMS (BELLMANN FORD ALGORITHM)

PROGRAM:
class Graph:
def __init__(self, vertices):
self.V = vertices
[Link] = []
def add_edge(self, u, v, w):
[Link]((u, v, w))
def bellman_ford(self, start):
distances = [float('inf')] * self.V
distances[start] = 0
for _ in range(self.V - 1):
for u, v, weight in [Link]:
if distances[u] != float('inf') and distances[u] + weight < distances[v]:
distances[v] = distances[u] + weight
# Check for negative cycles
for u, v, weight in [Link]:
if distances[u] != float('inf') and distances[u] + weight < distances[v]:
raise ValueError("Graph contains a negative cycle")
return distances
# Example Usage and Output for Lab Practice
g = Graph(5)
g.add_edge(0, 1, 4)
g.add_edge(0, 2, 2)
g.add_edge(1, 2, 5)
g.add_edge(1, 3, 10)
g.add_edge(2, 4, 3)
g.add_edge(3, 5, 7)
g.add_edge(4, 3, 1)
g.add_edge(4, 5, 8)
start_vertex = 0
shortest_distances = g.bellman_ford(start_vertex)
print(f"Shortest Distances from Vertex {start_vertex}:")
for v, dist in enumerate(shortest_distances):
print(f"To Vertex {v}: {dist}")

OUTPUT
Shortest Distances from Vertex 0:
To Vertex 0: 0
To Vertex 1: 4
To Vertex 2: 2
To Vertex 3: 9
To Vertex 4: 5
To Vertex 5: 16
RESULT:
Thus the python program to implement Bellmann Ford Algorithm was written,
executed and verified successfully

AIM:
To write a python program to implement Matrix Chain Multiplication.
ALGORITHM:
 A chain of matrices to be multiplied is given as input.
 For a sequence A1,A2,A3,A4 of 4 matrices, there are 5 different orderings=5
different parenthesization.
o (A1,(A2(A3 A4)))
o (A1((A2 A3)A4))
o ((A1 A2)(A3 A4))
o ((A1(A2 A3))A4)
o (((A1 A2)A3)A4)
 Matrix_Multiply(A,B)
 If coloumns[A]!=rows[B]
 Then error “incomplete dimensions”
 Else for i <- 1 to rows[A]
 Do for j <- 1 to columns[B]
 Do c[I,j] <- 0
 For k<- 1 to columns[A]
 Do c[i,j]=C[i,j]+A[i,k]+B[i,j]
 Return c
 A parenthesizing of the chain of the matrices is obtained as output.
[Link]: 11
MATRIX CHAIN MULTIPLICATION

PROGRAM:
def matrix_chain_multiplication(p):
n = len(p) - 1 # Number of matrices
m = [[0] * (n + 1) for _ in range(n + 1)] # Table to store minimum multiplication
cost
s = [[0] * (n + 1) for _ in range(n + 1)] # Table to store split points
for length in range(2, n + 1):
for i in range(1, n - length + 2):
j = i + length - 1
m[i][j] = float('inf')
for k in range(i, j):
cost = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]
if cost < m[i][j]:
m[i][j] = cost
s[i][j] = k
return m, s
def print_optimal_parenthesization(s, i, j):
if i == j:
print(f"A{i}", end="")
else:
print("(", end="")
print_optimal_parenthesization(s, i, s[i][j])
print_optimal_parenthesization(s, s[i][j] + 1, j)
print(")", end="")
# Example Usage and Output for Lab Practice
matrix_dimensions = [30, 35, 15, 5, 10, 20, 25]
m_table, s_table = matrix_chain_multiplication(matrix_dimensions)
print("Minimum Multiplication Cost Table:")
for row in m_table:
print(row)
print("\nOptimal Parenthesization:")
print_optimal_parenthesization(s_table, 1, len(matrix_dimensions) - 1)
50

OUTPUT:
Minimum Multiplication Cost Table:
[0, 15750, 7875, 9375, 11875, 15125]
[0, 0, 2625, 4375, 7125, 10500]
[0, 0, 0, 750, 2500, 5375]
[0, 0, 0, 0, 1000, 3500]
[0, 0, 0, 0, 0, 5000]
[0, 0, 0, 0, 0, 0]
Optimal Parenthesization:
((A1(A2A3))((A4A5)A6))
RESULT:
Thus the python program to implement Matrix Chain Multiplication was written,
executed and
verified successfully.

AIM:
To write a python program to implement Activity Selection.
ALGORITHM:
 Sort the activities as per finishing time in ascending order
 Select the first activity
 Select the new activity if its starting time is greater than or equal to the
previously
selected
 activity
 REPEAT step 3 till all activities are checked.

PROGRAM:
[Link]: 12a
ACTIVITY SELECTION

def activity_selection(start, finish):

n = len(start)
activities = []
# Create a list of tuples (start_time, finish_time, activity_number)
for i in range(n):
[Link]((start[i], finish[i], i + 1))
# Sort activities based on finish times
[Link](key=lambda x: x[1])
# Select the first activity
selected_activities = [activities[0]]
# Select new activity if its start time is greater than or equal to the finish time of
the last
selected activity
for i in range(1, n):
if activities[i][0] >= selected_activities[-1][1]:
selected_activities.append(activities[i])
return selected_activities
# Example Usage and Output for Lab Practice
start_times = [1, 3, 0, 5, 8, 5]
finish_times = [2, 4, 6, 7, 9, 9]
selected_activities = activity_selection(start_times, finish_times)
print("Selected Activities:")
for activity in selected_activities:
print(f"Activity {activity[2]} (Start Time: {activity[0]}, Finish Time:
{activity[1]})")
OUTPUT:
Selected Activities:
Activity 3 (Start Time: 0, Finish Time: 6)
Activity 1 (Start Time: 1, Finish Time: 2)
Activity 4 (Start Time: 5, Finish Time: 7)
Activity 5 (Start Time: 5, Finish Time: 9)
RESULT:
Thus the python program to implement activity selection was executed and verified
successfully

AIM:
To write a python program to implement Huffman Coding
ALGORITHM:
 Sort the message ensemble by decreasing probability.
 N is the cardinal of the message ensemble (number of different messages).
 Compute the integer n_0 such as 2<=n_0<=D and (N-n_0)/(D-1) is integer.
 Select the n_0 least probable messages, and assign them each a digit code.
 Substitute the selected messages by a composite message summing their
probability, and
 re-order it.
 While there remains more than one message, do steps thru 8.
 Select D least probable messages, and assign them each a digit code.
 Substitute the selected messages by a composite message summing their
probability, and
 re-order it.
 The code of each message is given by the concatenation of the code digits of the
aggregate they've been put in
.

PROGRAM:
[Link]: 12b
HUFFMAN CODING

import heapq
from collections import defaultdict
class HuffmanNode:
def __init__(self, char, freq):
[Link] = char
[Link] = freq
[Link] = None
[Link] = None
def __lt__(self, other):
return [Link] < [Link]
def build_huffman_tree(freq_map):
priority_queue = [HuffmanNode(char, freq) for char, freq in freq_map.items()]
[Link](priority_queue)
while len(priority_queue) > 1:
left_node = [Link](priority_queue)
right_node = [Link](priority_queue)
internal_node = HuffmanNode(None, left_node.freq + right_node.freq)
internal_node.left = left_node
internal_node.right = right_node
[Link](priority_queue, internal_node)
return priority_queue[0]
def build_huffman_codes(node, code="", mapping=None):
if mapping is None:
mapping = {}
if [Link] is not None:
mapping[[Link]] = code
if [Link] is not None:
build_huffman_codes([Link], code + "0", mapping)
if [Link] is not None:
build_huffman_codes([Link], code + "1", mapping)
return mapping
def huffman_coding(text):
freq_map = defaultdict(int)
for char in text:
freq_map[char] += 1
root = build_huffman_tree(freq_map)
codes = build_huffman_codes(root)
encoded_text = "".join(codes[char] for char in text)
return encoded_text, codes
# Example Usage and Output for Lab Practice
text_to_encode = "huffman coding is fun"
encoded_text, huffman_codes = huffman_coding(text_to_encode)
print("Original Text:", text_to_encode)
print("Encoded Text:", encoded_text)
print("Huffman Codes:")
for char, code in huffman_codes.items():
print(f"{char}: {code}")

OUTPUT
Original Text: huffman coding is fun
Encoded Text:
010101110111111111011010110110001100111110001101101001011110111000
1110100
1111001010101101
Huffman Codes:
h: 010
u: 11000
f: 011
m: 1111
a: 00
n: 11001
c: 1110
o: 1101
d: 100
i: 0100
g: 11101
s: 1000
: 1010
1: 10110
1: 10111
1: 101110
0: 101111
RESULT:
Thus the python program to implement Huffman Coding was written, executed and
verified
successfully.