ANNA UNIVERSITY,CHENNAI .

GKM
COLLEGE OF ENGINEERING AND TECHNOLOGY
(SPONSPERED BY SUGANTHI EDUCATIONAL TRUST)
(AN ISO ISO: 9001 :2005 CERTIFIDE, APPROVED BY AICTE ,AFFLIATED TO ANNA UNIVERSITY)
G.K.M NAGAR,New Perungalathur(Near Tambaram) Chennai-600 063.

ESTD.1996

(BACHELOR OF ENGINEERING)
COMPUTER SCIENCE AND ENGINEERING

LABORATORY RECORD

NAME : …………………………………….

REGISTER NUMBER : …………………………………….

SEMESTER : …………………………………….

YEAR : …………………………………….

BRANCH : ……………………………………..
 GKM
COLLEGE OF ENGINEERING AND TECHNOLOGY

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

BONAFIDE CERTIFICATE

REG NO:

Name of the lab

Department of Certified that this is a bonafide record of

the work done by of Class in the

Laboratory during the Year

Signature of Staff-in-Charge Head of the Department

Internal Examiner External Examiner

Name of the Examination : ………………………….

Register No : …………………………..
Date of the Examination : ………………………….
 INDEX
Exp. Date Name of the Experiment Page Marks Sign
No No
SEARCHING AND SORTING ALGORITHMS

01 Implement Linear Search. Determine the time required to search for an

element. Repeat the experiment for different values of n, the number
of elements in the list to be searched
and plot a graph of the time taken versus n.
02 Implement recursive Binary Search. Determine the
time required to search an [Link] the
experiment for different values of n, the number of
elements in the list to be searched and plot a graph of
the time taken versus n
03 Given a text txt [0...n-1] and a pattern pat [0...m-1],
write a function search (char pat [ ], chartxt [ ]) that
prints all occurrences of pat [ ] in txt [ ]. You may
assume that n > m.
04 Sort a given set of elements using the Insertion sort
and Heapsort methods and determine the time
required to sort theelements. Repeat the experiment
for different values of n, the number of elements in the
list to be sorted and plot a graph ofthe time taken
versus n.
GRAPH ALGORITHMS

05 Develop a program to implement graph traversal

using BreadthFirst Search

06 Develop a program to implement graph traversal

using DepthFirst Search
07 From a given vertex in a weighted connected graph,
develop aprogram to find the shortest paths to other
vertices using
Dijkstra’s algorithm
08 Find the minimum cost spanning tree of a given
undirectedgraph using Prim’s algorithm
09 Implement Floyd’s algorithm for the All-Pairs-
Shortest-Paths problem

10 Compute the transitive closure of a given directed

graph using Warshall's algorithm
 ALGORITHM DESIGN TECHNIQUES
11 Develop a program to find out the maximum and
minimum numbers in a given list of n numbers using
the divide and conquer technique

12 Implement Merge sort and Quick sort methods to

sort an arrayof elements and determine the time
required to sort. Repeat theexperiment for different
values of n, the number of elements inthe list to be
sorted and plot a graph of the time taken versus n.
13 STATE SPACE SEARCH ALGORITHMS
Implement N Queens problem using Backtracking

APPROXIMATION ALGORITHMS RANDOMIZED ALGORITHMS

14 Implement any scheme to find the optimal

solution for theTraveling Salesperson problem
and then solve the same problem instance using
any approximation algorithm and determine the
error in the approximation
15 Implement randomized algorithms for finding the
kth smallest number (C/C++/JAVA/ Python)

Staff-in-Charge Sign
 lOMoARcPSD|304 346 44

[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.
 lOMoARcPSD|304 346 44

Program (Linear Search):

import time
import [Link] as plt

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]()
 lOMoARcPSD|304 346 44

Output :

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

[2.6226043701171875e-06, 7.867813110351562e-06, 0.0027456283569335938,
0.000804901123046875, 0.028525352478027344, 0.10596990585327148]
Time taken to find 999999 in arr using linear search: 0.07597494125366211 seconds

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.
 lOMoARcPSD|304 346 44

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.
 lOMoARcPSD|304 346 44

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

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]()
 lOMoARcPSD|304 346 44

Output:

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

[3.5762786865234375e-06,3.337860107421875e-06,6.9141387939453125e-06,
1.049041748046875e-05, 1.4543533325195312e-05, 2.1457672119140625e-05]

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.
 lOMoARcPSD|304 346 44

[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.
 lOMoARcPSD|304 346 44

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}")

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")
 lOMoARcPSD|304 346 44

Output:

Time taken to find pattern

Pattern found at index 10
Time taken: 0.000444
second

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.
 lOMoARcPSD|304 346 44

[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.
 lOMoARcPSD|304 346 44

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]()
 lOMoARcPSD|304 346 44

Output:

n=10: 1.6927719116210938e-05 seconds

n=100: 0.0008394718170166016 seconds
n=1000: 0.1715688705444336 seconds
n=10000: 16.449705600738525 seconds

Result:
Thus, the program has been executed successfully and the output has been verified.
 lOMoARcPSD|304 346 44

[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
 lOMoARcPSD|304 346 44

Program (Heap sort):

import random
import time
import [Link] as plt

def heapify(arr, n, i):

largest = i
l=2*i+1
r=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]()
 lOMoARcPSD|304 346 44

Output:

n=1000: 0.07786297798156738 seconds

n=2000: 0.32976579666137695 seconds
n=3000: 0.7329976558685303 seconds
n=4000: 1.3388376235961914 seconds
n=5000: 2.0903823375701904 seconds

Result:
Thus, the program has been executed successfully and the output has been verified.
 lOMoARcPSD|304 346 44

[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.
 lOMoARcPSD|304 346 44

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]:
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)
 lOMoARcPSD|304 346 44

Output:

Following is Breadth First Traversal starting from

vertex 2:Time taken to run BFS:
2 0 3 1 Time taken: 0.0016477108001708984

Result:
Thus, the program has been executed successfully and the output has been verified.
 lOMoARcPSD|304 346 44

[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.
 lOMoARcPSD|304 346 44

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")
 lOMoARcPSD|304 346 44

Output:

Following is DFS from (starting from vertex 2)

Timeof my program:
2 0 1 3 Time taken: 0.0019555091857910156 seconds

Result:
Thus, the program has been executed successfully and the output has been verified.
 lOMoARcPSD|304 346 44

[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.
 lOMoARcPSD|304 346 44

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,
# 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 = {
 lOMoARcPSD|304 346 44

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))
# 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))
 lOMoARcPSD|304 346 44

Output:

The shortest distances from vertex 0 to all other vertices are: [0, 4, 12, 19, 21, 11, 9, 8, 14]
Timetaken by dijkstra function:
Time taken by dijkstra function: 1.8596649169921875e-05 seconds
 lOMoARcPSD|304 346 44

Result:
Thus, the program has been executed successfully and the output has been verified.
 lOMoARcPSD|304 346 44

[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
 lOMoARcPSD|304 346 44

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):
[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")
 lOMoARcPSD|304 346 44

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)
[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)
 lOMoARcPSD|304 346 44

Output:

Time of my
programEdge
Weight
0-1 2
1-2 3
0-3 6
1-4 5
Time taken: 0.0037267208099365234

Result:
Thus, the program has been executed successfully and the output has been verified
 lOMoARcPSD|304 346 44

[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.
 lOMoARcPSD|304 346 44

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 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))
 lOMoARcPSD|304 346 44

Output:

[[0, 5, 15, 10], [20, 0, 10, 5], [30, 35, 0, 40], [15, 20, 5, 0]] time
of my program
4.506111145019531
e-05

Result:
Thus, the program has been executed successfully and the output has been verified.
 lOMoARcPSD|304 346 44

[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.
 lOMoARcPSD|304 346 44

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

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))
 lOMoARcPSD|304 346 44

Output:

[[1, 1, 1, 1], [0, 1, 1, 1], [0, 0, 1, 1], [0, 0, 0, 1]] Time

taken to compute transitive
closure:
2.4557113647460938e05

Result:
Thus, the program has been executed successfully and the output has been verified.
 lOMoARcPSD|304 346 44

[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.
 lOMoARcPSD|304 346 44

Program (Divide and conquer technique):

import time

def findMinMax(arr, low, high):

if low == high:
return 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))
 lOMoARcPSD|304 346 44

Output:

Minimum: 1
Maximum: 10
timeof my
program
Time taken: 1.239776611328125e-05

Result:
Thus, the program has been executed successfully and the output has been verified.
 lOMoARcPSD|304 346 44

[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 sorted
DATE: 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.
 lOMoARcPSD|304 346 44

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)

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
 lOMoARcPSD|304 346 44

# 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)
 lOMoARcPSD|304 346 44

Output:
[100, 1000, 5000, 10000, 50000, 100000]
[0.00030517578125, 0.0035512447357177734, 0.020572662353515625,
0.04424095153808594, 0.26787829399108887, 0.5633130073547363]

Result:
Thus, the program has been executed successfully and the output has been verified.
 lOMoARcPSD|304 346 44

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
DATE: be 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 sub-
arrays 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.
 lOMoARcPSD|304 346 44

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
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]()
 lOMoARcPSD|304 346 44

Output:
[100, 200, 500, 1000, 2000, 5000, 10000]
[1.0728836059570312e-05, 1.3828277587890625e-05, 4.3392181396484375e-05,
7.200241088867188e-05, 0.00014543533325195312, 0.00128936767578125,
0.0007746219635009766]

Result:
Thus, the program has been executed successfully and the output has been verified.
 lOMoARcPSD|304 346 44

[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)
 lOMoARcPSD|304 346 44

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:
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)
 lOMoARcPSD|304 346 44

Output:

Q-------
------Q-
----Q---
-------Q
-Q------
---Q----
-----Q--
--Q-----

Time taken: 0.01543879508972168

Result:
Thus, the program has been executed successfully and the output has been verified.
 lOMoARcPSD|304 346 44

APPROXIMATION ALGORITHMS RANDOMIZED

[Link]: 14
ALGORITHMS
Implement any scheme to find the optimal solution for the
Traveling Salesperson problem and then solve the same
DATE:
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 approximation
solution 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 programming
approach.
13. Create a numpy array named "graph" that represents the distance matrix between the
cities.
14. Print the optimal solution, the approximation solution using the nearest neighbor
heuristic, 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.
 The function tsp_nn takes a graph and n
 lOMoARcPSD|304 346 44

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
 lOMoARcPSD|304 346 44

n=4
graph = [Link]([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]])

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")
 lOMoARcPSD|304 346 44

Output:

Optimal Solution: 80.0

Approximation: 80
Error: 0.0 %
Time taken: 0.00017547607421875 seconds

Result:
Thus, the program has been executed successfully and the output has been verified.
 lOMoARcPSD|304 346 44

[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.
 lOMoARcPSD|304 346 44

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 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)
 lOMoARcPSD|304 346 44

Output:

QuickSelect: 5
Reservoir
Sampling: 8Time
of my program
QuickSelect Time:
1.621246337890625e-05Time of my
program
Reservoir Sampling Time: 1.2159347534179688e-05

Result:
Thus, the program has been executed successfully and the output has been verified.
lOMoARcPSD|304 346 44