lOMoARcPSD|30434644

[Link] SEARCHING AND SORTING ALGORITHMS

Implement Linear Search. Determine the time required to
search for an element. Repeat the experiment for different
DATE: values of n, the number of elements in the list to besearched
and plot a graph of the time taken versus n.

Aim:
To implement Linear Search, measure its time complexity for searching an element,
Vary the input size by changing the number of elements in the list, and plot a graph to
visualizethe relationship between time taken and input size

Algorithm:

1. Start with the first element of the list.

2. Compare the element with the value being searched for.
3. If the element matches, return the index.
4. If the element does not match, move to the next element and repeat steps 2-3.
5. If the end of the list is reached and no match is found, return -1.

Note:
This code first implements the linear_search function which takes a list arr and an
element x as input and returns the index of x in arr if it exists, otherwise returns -1. The
function measure_time takes a number n as input and returns the time taken to search for an
element that is not in the list of n elements. The main block of code then creates a list of
n_values, each representing the number of elements in the list, and measures the time taken to
search for an element in each of these lists. Finally, it plots the graph of the time taken versus
n.
Program (Linear Search):

import time
import [Link] as plt # Plotting the graph

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

def linear_search(arr, x):

for i in range(len(arr)):
if arr[i] == x:
return i
return -1

def measure_time(n):
arr = [i for i in range(n)]
start_time = [Link]()
linear_search(arr, n + 1)
return [Link]() -
start_time

def time_taken(arr, x):

start_time = [Link]()
linear_search(arr, x) return
[Link]() - start_time

if name == ' main ':

n_values = [10, 100, 1000, 10000, 100000, 1000000]
times = [measure_time(n) for n in n_values]

print(n_values)
print(times)

# Example usage of time_taken function

arr = [i for i in range(1000000)]
x = 999999
print(f"Time taken to find {x} in arr using linear search: {time_taken(arr, x)} seconds")

[Link](n_values, times) [Link]('n -

number of elements in list')
[Link]('Time taken (in seconds)')
[Link]('Linear search performance')
[Link]()
Output :

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

Result:
Thus the python program to implement Linear Search, measure its time complexity for
searching an element, vary the input size by changing the number of elements in the list, and plot a
graph to visualize the relationship between time taken and input size has been executed successfully
and the output has been verified.
Implement recursive Binary Search. Determine the time
[Link]
required to search an [Link] the experiment for
different values of n, the number of elements in the list to be
DATE: searched and plot a graph of the time taken versus n.
Aim:
To implement recursive Binary Search, measure its time complexity for searching an
element and plot a graph of time taken versus different values of n, the number of elements in
the list.

Algorithm:
1. Start with the middle element of the list
2. If the middle element matches the element being searched, return the index of the
middle element
3. If the middle element is greater than the element being searched, recursively call the
function on the left half of the list
4. If the middle element is less than the element being searched, recursively call the
function on the right half of the list
5. If the element is not found, return -1

Note:
This code first defines a function binary_search_recursive that performs a recursive
binary search in a list. Then, it defines a function measure_time that measures the time taken
to search for an element in a list of size n. The n_values list contains different values of n to
be tested, and the time_values list contains the corresponding time taken to search for an
element. Finally, the code plots a graph of time_values versus n_values using matplotlib. The
graph shows the performance of the recursive binary search algorithm for different values of
n.
Program (Binary Search):

import time import

[Link] as plt

def binary_search_recursive(arr, x, left, right):

if right >= left: mid =
(left + right) // 2

if arr[mid] == x:
return mid

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

elif arr[mid] > x: return

binary_search_recursive(arr, x, left, mid-1)

else: return binary_search_recursive(arr, x, mid+1,

right)

else:
return -1

def measure_time(n):
arr = [i for i in range(1, n + 1)] x = arr[-1]
# searching for the last element start =
[Link]()
binary_search_recursive(arr, x, 0, len(arr) - 1)
end = [Link]()
return end - start

n_values = [10, 100, 1000, 10000, 100000, 1000000]

time_values = [measure_time(n) for n in n_values]
print(n_values)
print(time_values)
[Link](n_values,
time_values)
[Link]('log')
[Link]('Number of elements (log scale)')
[Link]('Time taken (seconds)')
[Link]('Recursive Binary Search Performance')
[Link]()
Output:

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

Result:
Thus the python program to implement recursive Binary Search, measure its time
complexity for searching an element and plot a graph of time taken versus different values of n by
changing the number of elements in the list has been executed successfully and the output has
been verified.

[Link]
Given a text txt [0...n-1] and a pattern pat [0...m-1], write a
function search (char pat [ ],char txt [ ]) that prints all
DATE: occurrences of pat [ ] in txt [ ]. You may assume that n > m.

Aim:
To write a function "search" that takes a pattern and a text as input, and outputs all
occurrences of the pattern in the text.

Algorithm:
1. Initialize an empty list to store the indices where the pattern occurs in the text.
2. Loop through each character in the text. For each character, check if the substring
starting at that character matches the pattern.
3. If there is a match, append the starting index of the substring to the list of occurrences.
4. Continue looping through the text until all possible substrings have been checked.
5. Return the list of indices where the pattern occurs in the text.

Note:
In this implementation, the search function takes two parameters, pattern and text, and
performs a straightforward search for all occurrences of the pattern in the text. The outer loop
goes through all possible starting positions of the pattern in the text, and the inner loop
compares the characters of the pattern and the text starting from the current position. If all
characters match, the pattern is found and its starting position is printed.
Program (Pattern Search):

import time

def search(pattern,
text): m =
len(pattern) n =
len(text)

for i in range(n - m + 1):

j = 0 while j < m and text[i + j] ==
pattern[j]:
j += 1
if j == m:
print(f"Pattern found at index {i}")

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

def time_taken(pattern, text):

print("Time taken to find
pattern") start = [Link]()
search(pattern, text) end =
[Link]() return end - start

text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
time = time_taken(pattern, text)
print(f"Time taken: {time:.6f} seconds")
Output:

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

Result:
Thus the python program to write a function "search" that takes a pattern and a text as
input, and outputs all occurrences of the pattern in the text has been executed successfully and
the output has been verified.
[Link]:4a Sort a given set of elements using the Insertion sort and
determine the time required tosort the elements. Repeat the
experiment for different values of n, the number of elements in
DATE:
the list to be sorted and plot a graph of the time taken versus n.
Aim :
To Develop a program to implement Insertion sort and determine the time required to
sort the elements.

Algorithm:

1. Iterate over the array from the second element to the end (i = 1 to n-1).
2. For each element, compare it to the elements before it (j = i-1 to 0).
3. If the current element is smaller, swap it with the element before it.
4. Repeat step 3 until the current element is no longer smaller than the previous element.
5. Repeat steps 2-4 for all elements in the array.

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

Program (Insertion sort):

import random
import time

def insertion_sort(arr):
for i in range(1, len(arr)): j = i - 1
while j >= 0 and arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j] j
-= 1

# Generate random lists of different sizes and sort them with insertion
sort n_values = [10, 100, 1000, 10000] # Different values of n times = []
for n in n_values: arr = [[Link](0, 1000) for _ in range(n)]
start_time = [Link]()
insertion_sort(arr) end_time =
[Link]() elapsed_time = end_time -
start_time [Link](elapsed_time)
print(f"n={n}: {elapsed_time}
seconds")

# Plot the time taken versus n

import [Link] as
plt [Link](n_values, times)
[Link]('n') [Link]('Time
(seconds)') [Link]()
Output:

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

[Link]:4b Sort a given set of elements using the Heap sort and determine
the time required to sortthe elements. Repeat the experiment
for different values of n, the number of elements inthe list to be
DATE: sorted and plot a graph of the time taken versus n.
Aim:
To Develop a program to implement Heap sort and determine the time required to sort
the elements.

Algorithm:

1. Build a max heap from the given array

2. Swap the root element with the last element of the array
3. Remove the last element from the heap (it is now in its correct position)
4. Heapify the remaining array to maintain the heap property
5. Repeat steps 2-4 until the entire array is sorted

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

Program (Heap sort):

import random import time

import [Link] as
plt

def heapify(arr, n, i):

largest = i
l=2*i+1r=2*i+2
if l < n and arr[largest] <
arr[l]: largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)

def heap_sort(arr): n = len(arr)

for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)

n_values = [1000, 2000, 3000, 4000, 5000] times =

[] for n in n_values: arr = [[Link](1,
10000) for _ in range(n)]
start_time = [Link]()
heap_sort(arr) end_time =
[Link]() [Link](end_time
- start_time)
[Link](n_values, times)
[Link]('n') [Link]('Time (s)')
[Link]('Heap sort time
complexity') [Link]()
Output:

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

[Link]
GRAPH ALGORITHMS
Develop a program to implement graph traversal using Breadth
DATE: First Search

Aim:
To Develop a program to implement graph traversal using Breadth First Search

Algorithm:
1. Initialize a queue to store the nodes to be visited.
2. Mark the starting node as visited and add it to the queue.
3. While the queue is not empty, repeat the following: a. Dequeue a node from the queue
and process it. b. For each adjacent node that has not been visited, mark it as visited
and add it to the queue.
4. Repeat step 3 until all nodes have been visited.

Note:
In the code above, the Graph class has an instance variable graph which is a default
dictionary representing the edges of the graph. The add_edge method adds an edge to the
graph and the BFS method performs a breadth-first search starting from a given source vertex
s. The method uses a queue to keep track of the vertices to visit and marks the visited vertices
in the visited list to ensure that each vertex is visited only once. The output of the program is
a breadth-first traversal of the graph starting from vertex 2.
Program (Breadth First Search):

import time
from collections import defaultdict

class Graph:
def init (self): [Link] =
defaultdict(list)

def add_edge(self, u, v):

[Link][u].append(v)

def BFS(self, s): visited = [False] *

(len([Link]))
queue = []
[Link](s)
visited[s] = True while
queue: s =
[Link](0) print(s,
end=" ") for i in
[Link][s]:

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

if not visited[i]:
[Link](i
) visited[i] =
True

def time_taken(self, s):

print("Time taken to run
BFS:") start_time = [Link]()
[Link](s) end_time =
[Link]() return end_time -
start_time

if name == ' main

': g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3) print("Following is Breadth First Traversal
starting from vertex 2:") time_taken = g.time_taken(2) print("Time
taken: ", time_taken)
Output:

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

[Link]
Develop a program to implement graph traversal using Depth First
Search
DATE:

Aim:
To Develop a program to implement graph traversal using Depth First Search

Algorithm:

1. Create an empty stack and mark all vertices as unvisited.

2. Choose a starting vertex and mark it as visited.
3. Push the starting vertex onto the stack.
4. While the stack is not empty, do the following: a. Pop a vertex from the stack and visit
it. b. For each unvisited neighbor of the popped vertex, mark it as visited and push it
onto the stack.
5. Repeat step 4 until the stack is empty and all vertices have been visited.

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

Program (Depth First Search):

import time

class Graph:
def init (self, num_vertices): self.num_vertices =
num_vertices self.adj_list = [[] for _ in
range(num_vertices)]

def add_edge(self, v, w):

self.adj_list[v].append(w
)
self.adj_list[w].append(v
)

def DFS(self, vertex, visited):

visited[vertex] = True
print(vertex, end=' ') for v
in self.adj_list[vertex]: if
not visited[v]:
[Link](v, visited)

def time_taken(graph, vertex):

print("Time of my program:") start =
[Link]() visited = [False] *
graph.num_vertices
[Link](vertex, visited) end =
[Link]() return end - start

if name == " main

": g = Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3) print("Following is DFS from
(starting from vertex 2)") print("Time taken:",
time_taken(g, 2), "seconds")

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

[Link]
From a given vertex in a weighted connected graph, develop a
program to find the shortest paths to other vertices using
DATE: Dijkstra’s algorithm.

Aim:
To develop a program to find the shortest paths to other vertices using Dijkstra’s
algorithm.

Algorithm:
1. Create a graph data structure to represent the vertices and edges of the graph.
2. Initialize the distances to all vertices as infinity, except for the source vertex, which is
set to 0.
3. Initialize an empty set of visited vertices.
4. While there are still unvisited vertices: a. Select the unvisited vertex with the smallest
known distance from the source. b. For the current vertex, examine its adjacent
vertices and calculate their distances from the source through the current vertex. c. If
the calculated distance is less than the previously known distance, update the distance.
d. Mark the current vertex as visited.
5. Return the calculated distances to all vertices.

Note:
In this implementation, graph is a dictionary where the keys are vertices and the
values are dictionaries mapping neighbors to their distances from the key vertex. The dijkstra
function takes the graph and the start vertex as input and returns a list of the shortest distances
from the start vertex to all.
Program (Dijkstra’s algorithm):

import heapq
import time

def dijkstra(graph, start):

# Initialize distances to all vertices as infinity (we use float('inf'))
distances = [float('inf')] * len(graph)
# Set the distance from the start vertex to itself as 0
distances[start] = 0
# Create a min heap with (distance, vertex) tuples
heap = [(0, start)]
# Continue looping until heap is empty
while heap:
# Pop the vertex with the minimum distance from the heap
dist, curr = [Link](heap)
# If the distance of the popped vertex is larger than its current distance,

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

# it means we have already processed a shorter path to this vertex and we can skip
it if dist > distances[curr]: continue
# Loop over all neighbors of the current vertex
for neighbor, weight in graph[curr].items():
# Calculate the new distance to the neighbor through the current vertex
new_dist = dist + weight
# If the new distance is shorter than the current distance to the neighbor,
# update the distance and push the neighbor onto the
heap if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
[Link](heap, (new_dist,
neighbor)) # Return the final list of distances to all
vertices return distances

def time_taken(graph, start): print("Time

taken by dijkstra function:") start_time
= [Link]()
dijkstra(graph, start)
end_time = [Link]()
return end_time -
start_time

if name == " main ":

# Define the weighted graph as an adjacency list where the keys are vertices and the values
are dictionaries
# mapping neighbors to their distances from the key vertex
graph = {
0: {1: 4, 7: 8},
1: {0: 4, 2: 8, 7: 11},
2: {1: 8, 3: 7, 8: 2, 5: 4},
3: {2: 7, 4: 9, 5: 14},
4: {3: 9, 5: 10},
5: {2: 4, 3: 14, 4: 10, 6: 2},
6: {5: 2, 7: 1, 8: 6},
7: {0: 8, 1: 11, 6: 1, 8: 7},
8: {2: 2, 6: 6, 7: 7}
}
# Specify the start vertex
start = 0
# Call the dijkstra function to get the shortest distances from the start vertex to all other
vertices distances = dijkstra(graph, start)
# Print the result
print("The shortest distances from vertex {} to all other vertices are: {}".format(start,
distances))

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

# Call the time_taken function to get the time taken by the dijkstra function
time_taken = time_taken(graph, start)
# Print the time taken
print("Time taken by dijkstra function: {} seconds".format(time_taken))

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

[Link]: 8
Find the minimum cost spanning tree of a given undirected
graph using Prim’s algorithm.
DATE:

Aim:
To find the minimum cost spanning tree of a given undirected graph using Prim’s
algorithm.

Algorithm:
1. Initialize a set of visited vertices and a priority queue.
2. Choose a starting vertex arbitrarily and add it to the visited set.
3. For each adjacent vertex of the starting vertex, add an edge to the priority queue with
its weight as the key.
4. While the priority queue is not empty: a. Extract the edge with the smallest weight
from the priority queue. b. If both vertices of the edge are not in the visited set, add
them to the visited set and add all of their adjacent edges to the priority queue. c. Add
the extracted edge to the minimum cost spanning tree.
5. Return the minimum cost spanning tree.

Note:
 The class Graph is defined with a constructor that takes the number of vertices as an input
and initializes a default dictionary to store the graph.
 The method addEdge adds edges to the graph.
 The method primMST implements Prim's algorithm to find the minimum cost spanning
tree.
 It initializes the key list with the maximum possible integer value and sets the value of
key[0] to 0. This means that node 0 is the starting node.
 It also initializes the parent list with None values, mstSet list with False values, and cout
to 0.
 In each iteration of the loop, the node with the minimum value in the key list that is not in
mstSet is selected and added to mstSet.
 The adjacent nodes of the selected node are then checked, and if the key
Program (Prim’s algorithm):

from collections import defaultdict

import sys import time

class Graph:
def init (self, vertices): self.V
= vertices [Link] =
defaultdict(list)

# Add edges to the graph def

addEdge(self, u, v, w):

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

[Link][u].append((v, w))
[Link][v].append((u, w))

# Find the minimum cost spanning tree using Prim's algorithm

def primMST(self):
key = [[Link]] *
self.V parent = [None] *
self.V key[0] = 0 mstSet =
[False] * self.V

for cout in range(self.V): u =

[Link](key, mstSet)
mstSet[u] = True

for v, weight in [Link][u]:

if mstSet[v] == False and key[v] >
weight: key[v] = weight parent[v] = u
[Link](parent)

def minKey(self, key,

mstSet): min = [Link]
for v in range(self.V):
if key[v] < min and mstSet[v] ==
False: min = key[v] min_index = v
return min_index

def printMST(self, parent):

print("Edge \tWeight")
for i in range(1, self.V): print(parent[i], "-", i, "\t",
[Link](i, parent[i]))

def getWeight(self, i, parent):

for v, weight in [Link][i]:
if v == parent:
return weight

def time_taken(graph):
print("Time of my
program") s = [Link]()
[Link]() return
[Link]() - s

g = Graph(5)
[Link](0, 1, 2)
[Link](0, 3, 6)

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

[Link](1, 2, 3)
[Link](1, 3, 8)
[Link](1, 4, 5)
[Link](2, 4, 7)
[Link](3, 4, 9)

t = time_taken(g)
print("Time taken:", t)

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

[Link]: 9
Implement Floyd’s algorithm for the All-Pairs- Shortest
Paths problem.
DATE:

Aim:
To Implement Floyd’s algorithm for the All-Pairs- Shortest-Paths problem.

Algorithm:
1. Initialize a 2D array dist[V][V] where V is the number of vertices in the graph. Set all
elements to infinity except for the diagonal which is set to 0.
2. For each edge (u, v) in the graph, set dist[u][v] to the weight of the edge.
3. For k from 1 to V: a. For i from 1 to V: i. For j from 1 to V: Update dist[i][j] as dist[i]
[k]
+ dist[k][j] if dist[i][k] + dist[k][j] < dist[i][j].
4. The final dist matrix contains the shortest path distances between all pairs of vertices.

Note:
 The function floydWarshall takes a 2D matrix graph as input and returns a 2D matrix
representing the shortest distances between all pairs of vertices.
 V is the number of vertices in the graph.
 dist is a 2D matrix that stores the intermediate distances between vertices. It is initialized
as a copy of the input graph.
 The algorithm uses three nested loops, where k is the intermediate vertex and i and j are
the source and destination vertices, respectively.
 In each iteration, the distance dist[i][j] is updated if a shorter path is found through the
intermediate vertex k. The new distance is calculated as dist[i][j] = min(dist[i][j], dist[i]
[k]+ dist[k][j]).
 The final 2D matrix dist represents the shortest distances between all pairs of vertices.
Program (Floyd’s algorithm):

import time import

[Link] as plt

def floydWarshall(graph):
V = len(graph)
dist = list(map(lambda i : list(map(lambda j : j, i)), graph))

for k in range(V):
for i in range(V):
for j in range(V):
dist[i][j] = min(dist[i][j], dist[i][k]+ dist[k][j])
return dist

def time_taken(graph):
print("time of my

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

program") s = [Link]()
floydWarshall(graph)
return [Link]() - s

graph = [[0, 5, 99999, 99999],

[50, 0, 15, 5],
[30, 99999, 0, 99999],

[15, 99999, 5, 0]]

print(floydWarshall(graph))

print(time_taken(graph))

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

[Link]: 10
Compute the transitive closure of a given directed graph using
Warshall's algorithm
DATE:

Aim:
To Compute the transitive closure of a given directed graph using Warshall's algorithm

Algorithm:
1. Import necessary modules, time and [Link].
2. Define the function transitiveClosure that takes a graph as input.
3. Find the number of vertices in the graph and initialize a reach list of the same size as
the graph.
4. Iterate over k, i, and j from 0 to V-1.
5. Update the reach matrix by setting reach[i][j] to true if either reach[i][j] is already true
or there exists a path from i to j through k.
6. Return the reach matrix.

Note:
 The function transitiveClosure takes a 2D matrix graph as input and returns a 2D matrix
representing the transitive closure of the graph.
 V is the number of vertices in the graph.
 reach is a 2D matrix that stores the intermediate reachability between vertices. It is
initialized as a copy of the input graph.
 The algorithm uses three nested loops, where k is the intermediate vertex and i and j are
the source and destination vertices, respectively.
 In each iteration, the reachability reach[i][j] is updated if a path from i to j can be found
through the intermediate vertex k. The new reachability is calculated as reach[i][j] =
reach[i][j] or (reach[i][k] and reach[k][j]).
 The final 2D matrix reach represents the transitive closure of the graph, where reach[i][j]
= 1 if there exists a directed path from vertex i to vertex j, and reach[i][j] = 0 otherwise.
Program (Warshall's algorithm):

import time import

[Link] as plt

def transitiveClosure(graph):
V = len(graph)
reach = list(map(lambda i : list(map(lambda j : j, i)), graph))

for k in range(V):
for i in range(V):
for j in range(V): reach[i][j] = reach[i][j] or (reach[i][k]
and reach[k][j]) return reach

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

def time_taken(graph): print("Time taken to

compute transitive closure:") start = [Link]()
transitiveClosure(graph) end = [Link]() return
end - start

# Example usage
graph = [[1, 1, 0, 1],
[0, 1, 1, 0],
[0, 0, 1, 1],
[0, 0, 0, 1]]

print(transitiveClosure(graph))
print(time_taken(graph))

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

[Link]: 11
ALGORITHM DESIGN TECHNIQUES
Develop a program to find out the maximum and minimum numbers
DATE: in a given list of n numbers using the divide and conquer technique

Aim:
To Develop a program to find out the maximum and minimum numbers in a given list
of n numbers using the divide and conquer technique

Algorithm:
1. Divide the list into two halves, L1 and L2.
2. Recursively find the maximum and minimum values of L1 and L2.
3. Compare the maximum and minimum values of L1 with the maximum and minimum
values of L2.
4. The maximum value of the two lists is the maximum value of the original list.
5. The minimum value of the two lists is the minimum value of the original list.

Note:
 The findMinMax function takes as input a list of numbers arr and the indices low and
high which represent the current sublist for which we want to find the minimum and
maximum numbers.

 If the low and high indices are equal, it means the sublist has only one element, which is
both the minimum and the maximum.

 If the low and high indices differ by 1, it means the sublist has two elements, and we
return the minimum and the maximum of these two elements.

 If the sublist has more than two elements, we find the middle index mid and recursively
call findMinMax on the left sublist (from low to mid) and the right sublist (from mid + 1
to high). The minimum and maximum of the entire sublist will be the minimum of the
two minimums and the maximum of the two maximums, respectively.

 The findMaxMin function is a wrapper function that initializes the low and high indices
and calls the findMinMax function for the entire list.

 This implementation has a time complexity of O(n), which is faster than linear search and
is efficient for large lists.
Program (Divide and conquer technique):

import time

def findMinMax(arr, low, high):

if low == high: return

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

arr[low], arr[high] if low + 1

== high:
return (min(arr[low], arr[high]), max(arr[low],
arr[high])) mid = (low + high) // 2 min1, max1 =
findMinMax(arr, low, mid) min2, max2 = findMinMax(arr,
mid + 1, high) return (min(min1, min2), max(max1, max2))

def findMaxMin(arr):
n = len(arr) return
findMinMax(arr, 0, n - 1)

def time_taken(arr): print("time of my

program") s = [Link]() min_val,
max_val = findMaxMin(arr) return
[Link]() - s

# Test the function with a sample array

arr = [3, 5, 2, 1, 4, 6, 8, 9, 10, 7]
print("Minimum: ", findMaxMin(arr)[0])
print("Maximum: ", findMaxMin(arr)
[1])

# Measure the time taken to find the minimum and maximum values
print("Time taken: ", time_taken(arr))

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

[Link]: 12a Implement Merge sort methods to sort an array of elements and
determine the timerequired to sort. Repeat the experiment for
different values of n, the number of elements in the list to be
DATE: sorted and plot a graph of the time taken versus n.
Aim:
To Implement Merge sort methods to sort an array of elements and determine the time
required to sort.

Algorithm:
1. If the array has only one element or is empty, return the array (it is already sorted).
2. Divide the array into two halves.
3. Recursively sort the left half of the array using Merge sort.
4. Recursively sort the right half of the array using Merge sort.
5. Merge the two sorted halves back into a single sorted array.

Note:
 We start by defining the merge_sort function which takes in an array and returns the
sorted array using the merge sort algorithm.
 In the main program, we create a list n_values which contains different values of n,
the number of elements in the list to be sorted.
 We then create an empty list merge_sort_times to store the time taken for sorting the
list using the merge sort method for each value of n.
 For each value of n in n_values, we generate a random list of that length, and record
the time before and after sorting the list using merge_sort. The difference between the
two times gives us the time taken to sort the list.
 We then plot a graph of time taken versus n by calling the plot_graph function,
passing n_values and merge_sort_times as arguments.
 The graph shows the relationship between the number of elements in the list and the
time taken to sort the list using the merge sort method.
Program (Merge sort):

import random import time

import [Link] as
plt

# Merge sort function

def merge_sort(arr):
if len(arr) > 1: mid
= len(arr)//2 L =
arr[:mid] R =
arr[mid:]

merge_sort(L)
merge_sort(R)

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

i=j=k=0

while i < len(L) and j < len(R):

if L[i] < R[j]:
arr[k] = L[i] i
+= 1 else:
arr[k] = R[j]
j += 1
k += 1

while i <
len(L): arr[k]
= L[i] i += 1
k += 1

while j <
len(R): arr[k]
= R[j] j += 1
k += 1
return arr

# Function to measure time taken for merge

sort def time_taken(arr): start_time =
[Link]() merge_sort(arr) return [Link]() -
start_time
# Plotting the time taken versus n for merge sort method def
plot_graph(n_values, merge_sort_times): [Link](n_values,
merge_sort_times, label = "Merge sort") [Link]("Number
of elements in the list (n)") [Link]("Time taken (in
seconds)")
[Link]("Merge sort")
[Link]() [Link]()

if name == ' main ':

n_values = [100, 1000, 5000, 10000, 50000, 100000] merge_sort_times =
[time_taken([[Link](0, 100) for i in range(n)]) for n in n_values] print(n_values)
print(merge_sort_times)
plot_graph(n_values, merge_sort_times)

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

Implement Quick sort methods to sort an array of elements

[Link]: 12b
and determine the timerequired to sort. Repeat the experiment
for different values of n, the number of elements in the list to be
DATE: sorted and plot a graph of the time taken versus n.
Aim:
To Implement Quick sort methods to sort an array of elements and determine the time
required to sort.

Algorithm:
1. Choose a pivot element from the array. This can be any element, but commonly the
middle element is chosen.
2. Partition the array such that all elements less than the pivot are on the left of the pivot
and all elements greater than the pivot are on the right of the pivot.
3. Recursively apply steps 1-2 to the sub-arrays formed by the partition until the
subarrays have only one element or are empty.

Note:
 The function quick_sort takes an array arr, the start index start and end index end as
arguments. It calls partition to determine the pivot and then calls quick_sort recursively
on the left and right sub-arrays.
 The function partition takes an array arr, the start index start and end index end as
arguments. It selects the last element as the pivot, partitions the array around the pivot,
and returns the pivot index.
 The function time_quick_sort takes the number of elements n as an argument, creates an
array of n elements in decreasing order, calls quick_sort, and returns the time taken.
 The n_values list contains the different values of n for which the experiment is repeated.
 The times list stores the time taken for each value of n.
 Finally, the graph of Time taken versus n is plotted using matplotlib.
Program (Quick sort):

import time import

[Link] as plt

def quick_sort(arr, start, end): if

start < end: pivot = partition(arr,
start, end) quick_sort(arr, start,
pivot - 1)
#quick_sort(arr, pivot + 1, end)

def partition(arr, start, end):

pivot = arr[end] i = start
- 1 for j in range(start,
end):
if arr[j] <= pivot:
i += 1

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

arr[i], arr[j] = arr[j], arr[i]

arr[i + 1], arr[end] = arr[end], arr[i + 1]
return i + 1

def time_quick_sort(n): arr = [i

for i in range(n, 0, -1)]
start_time = [Link]()
quick_sort(arr, 0, n - 1) return
[Link]() - start_time

n_values = [100, 200, 500, 1000, 2000, 5000,

10000] times = [] for n in n_values:
[Link](time_quick_sort(n))
print(n_values) print(times)
[Link](n_values, times)
[Link]("Number of elements
(n)") [Link]("Time taken (s)")
[Link]()

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

[Link]: 13
STATE SPACE SEARCH ALGORITHMS
Implement N Queens problem using Backtracking.
DATE:

Aim:
To Implement N Queens problem using Backtracking.

Algorithm:
1. Start with an empty chessboard of size N x N.
2. Place a queen in the first column of the first row.
3. Move to the next column and try to place a queen in the first row.
4. If a queen can be placed in the current cell without conflicting with any previously
placed queens, move to the next column and repeat step 3.
5. If all the rows have been tried and a queen cannot be placed in the current column
without conflict, backtrack to the previous column and remove the queen from the last
row where it was placed.
6. Move the queen one row down in the previous column and try to place it again.
7. Repeat steps 4 to 6 until all possible solutions have been found or all possibilities have
been exhausted.

Note :
 The function print_board takes a board and prints it to the console. If a cell has a value of
1, it prints "Q", else it prints "-".
 The function is_safe takes a board, the current row and col as arguments and returns True
if it's safe to place a Queen in the current cell, else returns False. It checks the current
row, the current column and the two diagonals to ensure that there are no other Queens in
the same row, column or diagonal.
 The function solve_n_queens takes a board and the current col as arguments and returns
True if a solution is found, else returns False. For each row, it checks if it's safe to place a
Queen in the current cell. If it is, it places a Queen, moves to the next column, and calls
solve_n_queens recursively. If a solution is not found, it backtracks by marking the cell as
empty (0) and moving to the next row.
 The function n_queens takes n as an argument and initializes a 2D board of size n * n
with all cells marked as empty (0). If solve_n_queens returns True, it calls print_board to
print the solution, else it prints "Solution does not exist".
 Finally, the n-Queens problem is solved for n = 8 by calling n_queens(n)
Program (N Queens):

import time def

print_board(board):
for i in range(len(board)):
for j in range(len(board)):
if board[i][j] == 1:
print("Q ", end="")
else:

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

print("- ", end="")

print()
def is_safe(board, row, col):
for i in range(col):
if board[row][i] == 1:
return False
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False
for i, j in zip(range(row, len(board), 1), range(col, -1, -1)):
if board[i][j] == 1:
return False
return True
def solve_n_queens(board, col):
if col >= len(board):
return True
for i in range(len(board)):
if is_safe(board, i, col): board[i]
[col] = 1 if
solve_n_queens(board, col + 1):
return True
board[i][col] = 0
return False
def n_queens(n): board = [[0 for i in range(n)]
for j in range(n)]
start_time = [Link]() if
solve_n_queens(board, 0):
print_board(board)
else:
print("Solution does not exist")
end_time = [Link]() print("Time taken:
", end_time - start_time)

n=8
n_queens(n)

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

[Link]: APPROXIMATION ALGORITHMS RANDOMIZED

14 ALGORITHMS
Implement any scheme to find the optimal solution for the

DATE: Traveling Salesperson problem and then solve the same

problem instance using any approximation
algorithmand determine the error in the approximation.
Aim:
To Implement any scheme to find the optimal solution for the Traveling Salesperson
problem.

Algorithm:
1. Create a function named "tsp_dp" that takes two arguments: "graph" and "n".
2. Create a numpy array named "dp" that is a matrix of size (1<<n, n) with all elements
initialized to infinity.
3. Initialize dp[1][0] to 0.
4. Use two nested loops to iterate through all possible subsets of vertices in "mask" and
all possible ending vertices in "i".
5. Inside the nested loops, use another loop to iterate through all possible starting
vertices in "j" and update dp[mask][i] if necessary.
6. Return the minimum cost of traveling through all the vertices in "graph" using the
dynamic programming approach.
7. Create a function named "tsp_nn" that takes two arguments: "graph" and "n".
8. Implement the nearest neighbor heuristic to find a suboptimal solution to the TSP.
9. Create a function named "tsp_error" that takes two arguments: "graph" and "n".
10. Calculate the error percentage between the optimal solution and the
approximationsolution using the nearest neighbor heuristic.
11. Create a function named "time_taken" that takes two arguments: "graph" and "n".
12. Measure the time taken to find the optimal solution using the dynamic
programmingapproach.
13. Create a numpy array named "graph" that represents the distance matrix between
thecities.
14. Print the optimal solution, the approximation solution using the nearest
neighborheuristic, the error percentage, and the time taken to find the optimal
solution.

Note:
 The function tsp_dp takes a graph and n as arguments and returns the optimal solution for
the TSP using Dynamic Programming. It creates a 2D dp array with dimensions (1 << n,
n) where 1 << n is a bitmask representation of all possible subsets of nodes and n is the
number of nodes. The initial value of dp[1][0] is set to 0, representing the starting node.
For each bitmask mask, it iterates over all nodes i and checks if the node is present in the
mask. If it is, it then iterates over all nodes j and updates the value of dp[mask][i] with the
minimum value of the current value and dp[mask ^ (1 << i)][j] + graph[j][i].
 Finally, it returns the minimum value of dp[(1 << n) - 1][i] + graph[i][0] for all nodes i.

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

 The function tsp_nn takes a graph and n

Program (Traveling Salesperson
problem): import numpy as np import time

def tsp_dp(graph, n):

dp = [Link]((1 << n, n)) *
[Link] dp[1][0] = 0 for mask in
range(1, 1 << n): for i in
range(n):
if not (mask & (1 << i)):
continue
for j in range(n):
if i == j or not (mask & (1 << j)):
continue
dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + graph[j][i])
return min([dp[(1 << n) - 1][i] + graph[i][0] for i in range(n)])

def tsp_nn(graph, n):

visited = [0] * n
visited[0] = 1 curr
= 0 ans = 0 for i in
range(n - 1): next =
-1 for j in range(n):
if visited[j] == 0 and (next == -1 or graph[curr][j] < graph[curr][next]):
next = j
ans += graph[curr]
[next] curr = next
visited[curr] = 1
ans += graph[curr][0]
return ans

def tsp_error(graph, n): opt =

tsp_dp(graph, n) approx =
tsp_nn(graph, n) return
(approx - opt) / opt * 100

def time_taken(graph, n):

start = [Link]()
tsp_dp(graph, n) end =
[Link]() return end
- start
n=4
graph = [Link]([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]])

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

print("Optimal Solution:", tsp_dp(graph, n))

print("Approximation:", tsp_nn(graph, n))
print("Error:", tsp_error(graph, n), "%") print("Time
taken:", time_taken(graph, n), "seconds")

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

[Link]: 15
Implement randomized algorithms for finding the kth smallest number
DATE:

Aim:
To Implement randomized algorithms for finding the kth smallest number.

Algorithm:
1. Start
2. Initialize the array "arr" and value of k
3. Define the function "quick_select(arr, k)" which takes an array and k value as input
and implements Quickselect algorithm to find the kth smallest element in the array
4. Define the function "reservoir_sampling(arr, k)" which takes an array and k value as
input and implements Reservoir Sampling algorithm to randomly select k items from
the array
5. Define the function "time_taken(func, arr, k)" which takes a function, array and k
value as input and calculates the time taken by the function to execute on the array
6. Call the quick_select() and reservoir_sampling() functions with "arr" and "k" as
arguments and print the results
7. Call the time_taken() function with quick_select() and reservoir_sampling() functions
and print the execution time of each function
8. End

Note:
 The function quick_select takes an arr and k as arguments and returns the kth smallest
number using QuickSelect. It selects a random pivot element from the arr, splits the arr
into two parts based on the pivot, and recursively calls the quick_select on either the left
or right part based on the value of k. If k is less than or equal to the length of the left part,
it calls quick_select on the left part. If k is greater than the length of arr minus the length
of the right part, it calls quick_select on the right part. If k is between these two values,
the pivot is returned as the kth smallest number.
 The function reservoir_sampling takes an arr and k as arguments and returns the kth
smallest number using Reservoir Sampling. It creates a reservoir array of size k and fills it
with the first k elements of arr. Then, for each subsequent element i in arr, it generates a
random number j from 0 to i. If j is less than k, it updates the jth element in the reservoir
with the current element arr[i]. Finally, it returns the k-1th element in the reservoir as the
kth smallest number.
Program (Randomized algorithms):

import random
import time

def quick_select(arr, k): pivot =

[Link](arr) left = [x for x
in arr if x < pivot] right = [x for

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

x in arr if x > pivot] if k <=

len(left): return quick_select(left,
k)
elif k > len(arr) - len(right): return
quick_select(right, k - (len(arr) - len(right)))
else: return
pivot

def reservoir_sampling(arr,
k): reservoir = arr[:k] for i
in range(k, len(arr)): j =
[Link](0, i) if j <
k:
reservoir[j] = arr[i]
return reservoir[k-1]

def time_taken(func, arr, k):

print("Time of my
program") start = [Link]()
func(arr, k) end =
[Link]() return end - start

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

k=5
print("QuickSelect:", quick_select(arr, k))
print("Reservoir Sampling:", reservoir_sampling(arr, k))

quickselect_time = time_taken(quick_select, arr, k)

print("QuickSelect Time:", quickselect_time)

reservoir_time = time_taken(reservoir_sampling, arr, k)

print("Reservoir Sampling Time:", reservoir_time)

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

[Link]: 16
PROGRAMS BEYOND SYLLABUS
Knuth-Morris-Pratt (KMP) algorithm
DATE:

Aim:
To implement the Knuth-Morris-Pratt (KMP) algorithm.

Algorithm:
1. First, create a prefix array to store the longest proper prefix of the pattern that is also a
suffix of its first i characters.
2. Initialize two pointers, i and j, to 0, which will track the current indices of the text and
pattern, respectively.
3. While i is less than the length of the text, do the following: a. If the character at index
i in the text matches the character at index j in the pattern, increment both i and j. b. If
j is equal to the length of the pattern, then a match has been found at index i-j. Store
this index and continue searching for other matches. c. If the character at index i in the
text does not match the character at index j in the pattern and j is not 0, update j to be
the value of the prefix array at index j-1 and continue comparing. d. If the character at
index i in the text does not match the character at index j in the pattern and j is 0,
increment i and continue searching.

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

Program (KMP algorithm):

def compute_lps(pattern): lps = [0] *

len(pattern) j = 0 for i in range(1,
len(pattern)): while j > 0 and pattern[j] !
= pattern[i]: j = lps[j-1]
if pattern[j] ==
pattern[i]: j += 1 lps[i] =
j
return lps

def kmp_search(text,
pattern): lps =
compute_lps(pattern) i = 0
j = 0 while i < len(text):
if text[i] ==
pattern[j]: i += 1 j
+= 1 if j ==
len(pattern):
return i - j
elif j > 0:
j = lps[j-1]
else:
i += 1
return -1
text = "ababcababaad" pattern = "ababa"
result = kmp_search(text, pattern) if result
!= -1: print(f"Pattern found at index
{result}")
else:
print("Pattern not found")

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

[Link]: 17
Naive string matching algorithm
DATE:

Aim:
To implement the Naive string matching algorithm.

Algorithm:

1. Start with text and pattern as inputs.

2. Initialize n to the length of text, and m to the length of pattern.
3. Initialize an empty list called positions to store the starting positions of pattern in text.
4. Loop over the indices i of text from 0 to n-m.
a. Initialize a counter j to 0.
b. Loop over the indices k of pattern from 0 to m-1.
i. If text[i+k] != pattern[k], break out of the loop.
ii. Otherwise, increment j by 1.
c. If j equals m, append i to positions.
5. Return positions.

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

Program (Naive string matching algorithm):

def naive_string_matching(text,
pattern): n = len(text) m = len(pattern)
positions = []

for i in range(n-m+1): j = 0 while j < m

and text[i+j] == pattern[j]: j += 1
if j == m:
[Link](i)

return positions

text = "ababcabcabababd" pattern = "ababd"

positions = naive_string_matching(text,
pattern) print("Pattern found at positions:",
positions)

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

[Link]: 18
Rabin Karp algorithm
DATE:

Aim:
To implement the Rabin Karp algorithm.

Algorithm:

1. Calculate the hash value of the pattern to be searched.

2. Calculate the hash value of the first substring of the same length in the text.
3. Compare the hash values of the pattern and the substring. If they are equal, compare
the pattern and the substring character by character.
4. If the pattern and the substring match, return the index of the substring in the text.
5. If the pattern and the substring do not match, calculate the hash value of the next
substring of the same length in the text.
6. Repeat steps 3-5 until the end of the text is reached or a match is found.

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

Program (Rabin Karp algorithm):

d = 10

def search(pattern, text, q):

m = len(pattern)
n = len(text)
p=
0t=
0h
=1i
=0

j=0

for i in range(m-1):
h = (h*d) % q

# Calculate hash value for pattern and

text for i in range(m): p = (d*p +
ord(pattern[i])) % q t = (d*t +
ord(text[i])) % q

# Find the match for i

in range(n-m+1): if p
== t:
for j in range(m):
if text[i+j] != pattern[j]:
break

j += 1 if
j == m:
print("Pattern is found at position: " + str(i+1))

if i < n-m: t = (d*(t-ord(text[i])*h) +

ord(text[i+m])) % q

if t < 0:
t = t+q

text = "ABCCDDAEFG"
pattern = "CDD"
q = 13
search(pattern, text, q)

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

[Link]: 19
From a given vertex in a weighted connected graph, develop a
program to find the shortest paths to other vertices using
DATE: Bellman Ford algorithm.

Aim:
To develop a program to find the shortest paths to other vertices using Bellman Ford
algorithm.

Algorithm:
1. Initialize the distance of the source vertex to itself as 0, and the distance of all other
vertices to infinity.
2. Repeat the following steps for V-1 times, where V is the number of vertices in the
graph:
a. For each edge (u, v) with weight w, update the distance of v as min(distance[v],
distance[u]+w).
3. After V-1 iterations, if there is any improvement in the distances, then the graph
contains a negative-weight cycle.
4. If there is no negative-weight cycle, then the distances obtained after V-1 iterations
are the shortest paths from the source vertex to all other vertices.

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

Program (Bellman Ford algorithm):

def bellman_ford(graph, source): distances

= {v: float('inf') for v in graph}
distances[source] = 0 for i in
range(len(graph)-1): for u in graph:
for v, w in graph[u].items():
if distances[u] != float('inf') and distances[u]+w < distances[v]:
distances[v] = distances[u]+w
for u in graph:
for v, w in graph[u].items():
if distances[u] != float('inf') and distances[u]+w <
distances[v]: print("Graph contains negative-weight cycle")
return
print("Shortest paths from source vertex",
source) for v in graph: print(v, distances[v])

graph = {
'A': {'B': 6, 'D': 1},
'B': {'C': 5},
'C': {'D': 5},
'D': {}, }
bellman_ford(graph,
'A')

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

[Link]: 20
Find the minimum cost spanning tree of a given undirected
graph using Kruskal’s algorithm.
DATE:

Aim:
To find the minimum cost spanning tree of a given undirected graph using Kruskal’s
algorithm.

Algorithm:

1. Create a priority queue to store all the edges in the graph sorted by their weights.
2. Create a set to keep track of the visited vertices.
3. Initialize a variable 'MST' to an empty list to store the minimum cost spanning tree.
4. Repeat until MST has V-1 edges, where V is the total number of vertices in the graph:
a. Remove the smallest weight edge from the priority queue. b. Check if the edge
connects two vertices that are not in the same set, i.e., there is no cycle formed. c. If
there is no cycle, add the edge to the MST and merge the two sets.
5. Return MST.

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

Program (Kruskal’s algorithm):

class Graph:

def init (self, vertices):

self.V = vertices
[Link] = []

def addEdge(self, u, v, w):

[Link]([u, v, w])

def find(self, parent, i):

if parent[i] != i:
parent[i] = [Link](parent, parent[i])
return parent[i]

def union(self, parent, rank, x, y):

if rank[x] < rank[y]:
parent[x] = y
elif rank[x] > rank[y]:
parent[y] = x
else:
parent[y] = x
rank[x] += 1

def KruskalMST(self):
result = []
i=0
e=0
[Link] = sorted([Link],key=lambda item: item[2])
parent = [] rank = [] for
node in range(self.V):
[Link](node)
[Link](0)
while e < self.V - 1: u,
v, w = [Link][i]
i=i+1
x = [Link](parent, u)
y = [Link](parent,
v) if x != y:
e=e+1
[Link]([u, v, w])
[Link](parent, rank, x, y)
minimumCost = 0 print("Edges in the
constructed MST") for u, v, weight in

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

result: minimumCost += weight

print("%d -- %d == %d" % (u, v,
weight))
print("Minimum Spanning Tree",
minimumCost) if name == ' main ': g =
Graph(4)
[Link](0, 1, 10)
[Link](0, 2, 6)
[Link](0, 3, 5)
[Link](1, 3, 15)
[Link](2, 3, 4)

[Link]()

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])

 lOMoARcPSD|30434644

Downloaded by CSESTAFF10 SAI KIRUTHIGA (csestaff10@[Link])