ANNA UNIVERSITY

UNIVERSITY COLLEGE OF ENGINEERING- DINDIGUL

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

CS3401 – ALGORITHM LABORATORY

Page | 1
 ANNA UNIVERSITY
UNIVERSITY COLLEGE OF ENGINEERING – DINDIGUL
DINDIGUL – 62422

BONAFIDE CERTIFICATE
This is to certify that is a bonafide record of work done by
Mr./Ms.________________________________________
in _____________________________________________
laboratory during the academic year 2022-20

University Registration no.:

Staff In charge Head of the Department

Submitted for the university Practical Examination held on __________________

INTERNAL EXAMINER EXTERNAL EXAMINER

Page | 2
PRACTICAL EXERCISES: 30 PERIODS
Searching and Sorting Algorithms
1. 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.
2. Implement recursive Binary Search. Determine the time required to search 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.
3. 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 occurrences of pat [ ] in txt [ ]. You may assume that n > m.
4. Sort a given set of elements using the Insertion sort and Heap sort methods and
determine the time required to sort the elements. Repeat the experiment for different
values of n, the number of elements in the list to be sorted and plot a graph of the time
taken versus n.

Graph Algorithms
1. Develop a program to implement graph traversal using Breadth First Search
2. Develop a program to implement graph traversal using Depth First Search
3. From a given vertex in a weighted connected graph, develop a program to find the
shortest paths to other vertices using Dijkstra’s algorithm.
4. Find the minimum cost spanning tree of a given undirected graph using Prim’s algorithm.
5. Implement Floyd’s algorithm for the All-Pairs- Shortest-Paths problem.
6. Compute the transitive closure of a given directed graph using Warshall's algorithm.

Algorithm Design Techniques

1. Develop a program to find out the maximum and minimum numbers in a given list of n
numbers using the divide and conquer technique.
2. Implement Merge sort and Quick sort methods to sort an array of elements and
determine the time required to sort. Repeat the experiment for different values of n, the
number of elements in the list to be sorted and plot a graph of the time taken versus n.

State Space Search Algorithms

1. Implement N Queens problem using Backtracking.

Approximation Algorithms Randomized Algorithms

1. Implement any scheme to find the optimal solution for the Traveling Salesperson problem
and then solve the same problem instance using any approximation algorithm and
determine the error in the approximation.
2. Implement randomized algorithms for finding the kth smallest number.

Page | 3
 INDEX
EXPT NAME OF THE EXPERIMENT PAGE DATE OF SIGNATURE
NO. NO. COMPLETION
1

10

11

12

13

14

15

Page | 4
 EXPT NO.: 01
LINEAR SEARCH
DATE :

Aim:
To write a python program to 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
Algorithm:
Linear Search (Array A, Value x)
Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit
Source Code:
def linear_Search(list1, n, key):
# Searching list1 sequentially
for i in range (0, n):
if (list1[i] == key):
return i
return -1

list1 = [1 ,3, 5, 4, 7, 9]
key = 7
n = len(list1)
res = linear_Search(list1, n, key)
if(res == -1):
print("Element not found")
else:
print("Element found at index: ", res)

Page | 5
Result:
Thus the python program for linear search algorithm was executed successfully and
the output was verified.

Page | 6
 EXPT NO.: 02
BINARY SEARCH
DATE :

Aim:
To write a python program to implement recursive Binary Search. Determine the
time required to search 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.
Algorithm:
Step 1: Compare x with the middle element.
Step 2: If x matches with the middle element, we return the mid index.
Step 3: Else If x is greater than the mid element, then x can only lie in the right half
subarray after the mid element. So, we recur for the right half.
Step 4: Else (x is smaller) recur for the left half.
Source Code:
# Python 3 program for recursive binary search.
# Returns index of x in arr if present, else -1
def binary_search(arr, low, high, x):
# Check base case
if high >= low:
mid = (high + low) // 2
# If element is present at the middle itself
if arr[mid] == x:
return mid
# If element is smaller than mid, then it can only be present in left subarray
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
# Else the element can only be present in right subarray
else:
return binary_search(arr, mid + 1, high, x)
else:
# Element is not present in the array
return -1

# Test array
arr = [ 2, 3, 4, 10, 40 ]
x = 10
# Function call
result = binary_search(arr, 0, len(arr)-1, x)
if result != -1:
print("Element is present at index", str(result))
else:
print("Element is not present in array")

Page | 7
Result:
Thus the python program for recursive binary search algorithm was executed
successfully and the output was verified.

Page | 8
EXPT NO.: 03
PATTERN SEARCH
DATE :

Aim:
To write a python program to 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 occurrences of pat [ ] in txt [ ].
You may assume that n > m.
Algorithm:
Step 1: We start the comparison of pat[j] with j = 0 with characters of the current
window of text.
Step 2: We keep matching characters txt[i] and pat[j] and keep incrementing i and j
while pat[j] and txt[i] keep matching.
Step 3: When we see a mismatch
1) We know that characters pat[0..j-1] match with txt[i-j…i-1] (Note that j
starts with 0 and increments it only when there is a match).
2) We also know (from the above definition) that lps[j-1] is the count of
characters of pat[0…j-1] that are both proper prefix and suffix.
3) From the above two points, we can conclude that we do not need to match
these lps[j-1] characters with txt[i-j…i-1] because we know that these
characters will anyway match. Let us consider the above example to
understand this.
Source Code:
# Python3 program for KMP Algorithm
def KMPSearch(pat, txt):
M = len(pat)
N = len(txt)
# create lps[] that will hold the longest prefix suffix
# values for pattern
lps = [0]*M
j = 0 # index for pat[]
# Preprocess the pattern (calculate lps[] array)
computeLPSArray(pat, M, lps)
i = 0 # index for txt[]
while (N - i) >= (M - j):
if pat[j] == txt[i]:
i += 1
j += 1
if j == M:
print("Found pattern at index " + str(i-j))
j = lps[j-1]
# mismatch after j matches
elif i < N and pat[j] != txt[i]:
# Do not match lps[0..lps[j-1]] characters,
# they will match anyway

Page | 9
 if j != 0:
j = lps[j-1]
else:
i += 1

def computeLPSArray(pat, M, lps):

len = 0 # length of the previous longest prefix suffix
lps[0] = 0 # lps[0] is always 0
i=1
# the loop calculates lps[i] for i = 1 to M-1
while i < M:
if pat[i] == pat[len]:
len += 1
lps[i] = len
i += 1
else:
# This is tricky. Consider the example.
# AAACAAAA and i = 7. The idea is similar
# to search step.
if len != 0:
len = lps[len-1]
# Also, note that we do not increment i here
else:
lps[i] = 0
i += 1
txt = "ABABDABACDABABCABAB"
pat = "ABABCABAB"
KMPSearch(pat, txt)

Result:
Thus the python program for Pattern search algorithm was executed successfully
and the output was verified.

Page | 10
EXPT NO.: 04
INSERTION SORT AND HEAP SORT
DATE :

Aim:
To write a python program to sort a given set of elements using the Insertion sort
and Heap sort methods and determine the time required to sort the elements. Repeat the
experiment for different values of n, the number of elements in the list to be sorted and plot
a graph of the time taken versus n.
Algorithm:
Insertion sort:
Step 1: Start the program
Step 2: Iterate from arr[1] to arr[N] over the array.
Step 3: Compare the current element (key) to its predecessor.
Step 4: If the key element is smaller than its predecessor, compare it to the
elements before. Move the greater elements one position up to make space for
the swapped element.
Step 5: Stop the program.
Heap Sort:
Step 1: Start the program
Step 2: Build a max heap from the input data.
Step 3: At this point, the maximum element is stored at the root of the heap.
Replace it with the last item of the heap followed by reducing the size of the
heap by 1. Finally, heapify the root of the tree.
Step 5: Repeat step 2 while the size of the heap is greater than 1.
Step 5: Stop the program

Source Code:
Insertion Sort:
# Python program for implementation of Insertion Sort
# Function to do insertion sort
def insertionSort(arr):
# Traverse through 1 to len(arr)
for i in range(1, len(arr)):
key = arr[i]
# Move elements of arr[0..i-1], that are
# greater than key, to one position ahead
# of their current position
j = i-1
while j >= 0 and key < arr[j] :
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key

Page | 11
# Driver code to test above
arr = [12, 11, 13, 5, 6]
insertionSort(arr)
for i in range(len(arr)):
print ("% d" % arr[i])
Heap Sort:
# Python program for implementation of heap Sort
# To heapify subtree rooted at index i.
# n is size of heap
def heapify(arr, N, i):
largest = i # Initialize largest as root
l = 2 * i + 1 # left = 2*i + 1
r = 2 * i + 2 # right = 2*i + 2
# See if left child of root exists and is
# greater than root
if l < N and arr[largest] < arr[l]:
largest = l
# See if right child of root exists and is
# greater than root
if r < N and arr[largest] < arr[r]:
largest = r
# Change root, if needed
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # swap
# Heapify the root.
heapify(arr, N, largest)

# The main function to sort an array of given size

def heapSort(arr):
N = len(arr)
# Build a maxheap.
for i in range(N//2 - 1, -1, -1):
heapify(arr, N, i)
# One by one extract elements
for i in range(N-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # swap
heapify(arr, i, 0)

# Driver's code
if __name__ == '__main__':
arr = [12, 11, 13, 5, 6, 7]

# Function call

Page | 12
 heapSort(arr)
N = len(arr)
print("Sorted array is")
for i in range(N):
print("%d" % arr[i], end=" ")

Result:
Thus the python program for Pattern search algorithm was executed successfully
and the output was verified.

Page | 13
EXPT NO.: 05
BREADTH FIRST SEARCH
DATE :

Aim:
To write a python program to develop a program to implement graph traversal using
Breadth First Search.
Algorithm:
Step 1: Consider the graph you want to navigate.
Step 2: Select any vertex in your graph, say v1, from which you want to traverse
the graph.
Step 3: Examine any two data structure for traversing the graph
Visited array (size of the graph)
Queue data structure
Step 4: Starting from the vertex, you will add to the visited array, and afterward,
you will v1’s adjacent vertices to the queue data structure.
Step 5: Now, using the FIFO concept, you must remove the element from the
queue, put it into the visited array, and then return to the queue to add the adjacent
vertices of the removed element.
Step 6: Repeat step 5 until the queue is not empty and no vertex is left to be
visited.

Source Code:
graph = {
'5' : ['3','7'],
'3' : ['2', '4'],
'7' : ['8'],
'2' : [],
'4' : ['8'],
'8' : []
}

visited = [] # List for visited nodes.

queue = [] #Initialize a queue
def bfs(visited, graph, node): #function for BFS
visited.append(node)
queue.append(node)
while queue: # Creating loop to visit each node
m = queue.pop(0)
print (m, end = " ")
for neighbour in graph[m]:
if neighbour not in visited:
visited.append(neighbour)

Page | 14
 queue.append(neighbour)

# Driver Code
print("Following is the Breadth-First Search")
bfs(visited, graph, '5') # function calling

Result:
Thus the python program for breadth first search algorithm was executed
successfully and the output was verified.

Page | 15
EXPT NO.: 06
DEAPTH FIRST SEARCH
DATE :

Aim:
To write a python program to develop a program to implement graph traversal using
Depth First Search.
Algorithm:
Step 1: Start by putting any one of the graph’s vertices at the back of the queue.
Step 2: Now take the front item of the queue and add it to the visited list.
Step 3: Create a list of that vertex's adjacent nodes. Add those which are not within
the visited list to the rear of the queue.
Step 4: Keep continuing steps two and three till the queue is empty.
Step 5: Stop the program
Source Code:
# Using a Python dictionary to act as an adjacency list
graph = {
'5' : ['3','7'],
'3' : ['2', '4'],
'7' : ['8'],
'2' : [],
'4' : ['8'],
'8' : []
}
visited = set() # Set to keep track of visited nodes of graph.
def dfs(visited, graph, node): #function for dfs
if node not in visited:
print (node)
visited.add(node)
for neighbour in graph[node]:
dfs(visited, graph, neighbour)
# Driver Code
print("Following is the Depth-First Search")
dfs(visited, graph, '5')

Result:
Thus the python program for depth first search algorithm was executed successfully
and the output was verified.

Page | 16
EXPT NO.: 07
DIJKSTRA’S ALGORITHM
DATE :

Aim:
To write a python program from a given vertex in a weighted connected graph, develop a
program to find the shortest paths to other vertices using Dijkstra’s algorithm.

Algorithm:
Step 1: Mark the source node with a current distance of 0 and the rest with infinity.
Step 2: Set the non-visited node with the smallest current distance as the current
node.
Step 3: For each neighbor, N of the current node adds the current distance of the
adjacent node with the weight of the edge connecting 0->1. If it is smaller than the current
distance of Node, set it as the new current distance of N.
Step 4: Mark the current node 1 as visited.
Step 5: Go to step 2 if there are any nodes are unvisited.
Source Code:
# Python program for Dijkstra's single
# source shortest path algorithm. The program is
# for adjacency matrix representation of the graph
class Graph():
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for column in range(vertices)]
for row in range(vertices)]
def printSolution(self, dist):
print("Vertex \t Distance from Source")
for node in range(self.V):
print(node, "\t\t", dist[node]

# A utility function to find the vertex with

# minimum distance value, from the set of vertices
# not yet included in shortest path tree
def minDistance(self, dist, sptSet):
# Initialize minimum distance for next node
min = 1e7
# Search not nearest vertex not in the
# shortest path tree
for v in range(self.V):
if dist[v] < min and sptSet[v] == False:
min = dist[v]
min_index = v
return min_index
# Function that implements Dijkstra's single source
# shortest path algorithm for a graph represented

Page | 17
 # using adjacency matrix representation
def dijkstra(self, src):
dist = [1e7] * self.V
dist[src] = 0
sptSet = [False] * self.V
for cout in range(self.V):
# Pick the minimum distance vertex from
# the set of vertices not yet processed.
# u is always equal to src in first iteration
u = self.minDistance(dist, sptSet)
# Put the minimum distance vertex in the
# shortest path tree
sptSet[u] = True
# Update dist value of the adjacent vertices
# of the picked vertex only if the current
# distance is greater than new distance and
# the vertex in not in the shortest path tree
for v in range(self.V):
if (self.graph[u][v] > 0 and
sptSet[v] == False and
dist[v] > dist[u] + self.graph[u][v]):
dist[v] = dist[u] + self.graph[u][v]
self.printSolution(dist)

# Driver program
g = Graph(9)
g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]
]
g.dijkstra(0)

Result:
Thus the python program for depth first search algorithm was executed successfully
and the output was verified.

Page | 18
 EXPT NO.: 08
PRIM’S ALGORITHM
DATE :

Aim:
To write a python program to find the minimum cost spanning tree of a given
undirected graph using Prim’s algorithm.
Algorithm:
Step 1: Determine an arbitrary vertex as the starting vertex of the MST.
Step 2: Follow steps 3 to 5 till there are vertices that are not included in the MST
(known as fringe vertex).
Step 3: Find edges connecting any tree vertex with the fringe vertices.
Step 4: Find the minimum among these edges.
Step 5: Add the chosen edge to the MST if it does not form any cycle.
Step 6: Return the MST and exit
Source Code:
# Prim's Algorithm in Python
INF = 9999999
# number of vertices in graph
N=5
#creating graph by adjacency matrix method
G = [[0, 19, 5, 0, 0],
[19, 0, 5, 9, 2],
[5, 5, 0, 1, 6],
[0, 9, 1, 0, 1],
[0, 2, 6, 1, 0]]
selected_node = [0, 0, 0, 0, 0]
no_edge = 0
selected_node[0] = True
# printing for edge and weight
print("Edge : Weight\n")
while (no_edge < N - 1):

minimum = INF
a=0
b=0
for m in range(N):
if selected_node[m]:
for n in range(N):
if ((not selected_node[n]) and G[m][n]):
# not in selected and there is an edge
if minimum > G[m][n]:
minimum = G[m][n]
a=m
b=n

Page | 19
 print(str(a) + "-" + str(b) + ":" + str(G[a][b]))
selected_node[b] = True
no_edge += 1

Result:
Thus the python program for depth first search algorithm was executed successfully
and the output was verified.

Page | 20
 EXPT NO.: 09
FLOYD’S ALGORITHM FOR THE ALL-
DATE : PAIRS- SHORTEST-PATHS PROBLEM
Aim:
To write a python program to Implement Floyd’s algorithm for the All-Pairs-
Shortest-Paths problem.
Algorithm:
Step 1: Initialize the solution matrix same as the input graph matrix as a first step.
Step 2: Then update the solution matrix by considering all vertices as an intermediate
vertex.
Step 3: The idea is to one by one pick all vertices and updates all shortest paths which
include the picked vertex as an intermediate vertex in the shortest path.
Step 4: When we pick vertex number k as an intermediate vertex, we already have
considered vertices {0, 1, 2, .. k-1} as intermediate vertices.
Step 5: For every pair (i, j) of the source and destination vertices respectively, there are
two possible cases.
• k is not an intermediate vertex in shortest path from i to j. We keep
the value of dist[i][j] as it is.
• k is an intermediate vertex in shortest path from i to j. We update
the value of dist[i][j] as dist[i][k] + dist[k][j] if dist[i][j] > dist[i][k] +
dist[k][j]
Source Code:
# Floyd Warshall Algorithm in python
# The number of vertices
nV = 4
INF = 999
# Algorithm implementation
def floyd_warshall(G):
distance = list(map(lambda i: list(map(lambda j: j, i)), G))
# Adding vertices individually
for k in range(nV):
for i in range(nV):
for j in range(nV):
distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
print_solution(distance)
# Printing the solution
def print_solution(distance):
for i in range(nV):
for j in range(nV):
if(distance[i][j] == INF):
print("INF", end=" ")
else:

Page | 21
 print(distance[i][j], end=" ")
print(" ")
G = [[0, 3, INF, 5],
[2, 0, INF, 4],
[INF, 1, 0, INF],
[INF, INF, 2, 0]]
floyd_warshall(G)

Result:
Thus the python program for Floyd’s algorithm was executed successfully and the
output was verified.

Page | 22
EXPT NO.: 10

DATE :
WARSHALL'S ALGORITHM
Aim:
To write a python program to compute the transitive closure of a given directed
graph using Warshall's algorithm.
Algorithm:
Step 1: Start the program
Step 2: Instead of an integer resultant matrix (dist[V][V] in floyd warshall), we can
create a Boolean reach-ability matrix reach[V][V] (we save space). The value reach[i][j] will
be 1 if j is reachable from i, otherwise 0.
Step 3: Instead of using arithmetic operations, we can use logical operations. For
arithmetic operation ‘+’, logical and ‘&&’ is used, and for a ‘-‘, logical or ‘||’ is used. (We
save time by a constant factor. Time complexity is the same though)
Step 4: Stop the program
Source Code:
# Python program for transitive closure using Floyd Warshall Algorithm
#Complexity : O(V^3)
from collections import defaultdict
#Class to represent a graph
class Graph:
def __init__(self, vertices):
self.V = vertices
# A utility function to print the solution
def printSolution(self, reach):
print ("Following matrix transitive closure of the given graph ")
for i in range(self.V):
for j in range(self.V):
if (i == j):
print ("%7d\t" % (1),end=" ")
else:
print ("%7d\t" %(reach[i][j]),end=" ")
print()

# Prints transitive closure of graph[][] using Floyd Warshall algorithm

def transitiveClosure(self,graph):
reach =[i[:] for i in graph]
for k in range(self.V):
# Pick all vertices as source one by one
for i in range(self.V):
# Pick all vertices as destination for the
# above picked source

Page | 23
 for j in range(self.V):
# If vertex k is on a path from i to j,
# then make sure that the value of reach[i][j] is 1
reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])
self.printSolution(reach)
g= Graph(4)

graph = [[1, 1, 0, 1],

[0, 1, 1, 0],
[0, 0, 1, 1],
[0, 0, 0, 1]]
#Print the solution
g.transitiveClosure(graph)

Result:
Thus the python program for Warshall's algorithm was executed successfully and the
output was verified.

Page | 24
EXPT NO.: 11 MAXIMUM AND MINIMUM NUMBERS USING
THE DIVIDE AND CONQUER TECHNIQUE
DATE :

Aim:
To write a python program 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:
Step 1: Start the program.
Step 2: Divide array by calculating mid index i.e. mid = l + (r — l)/2
Step 3: Recursively find the maximum and minimum of left part by calling the same
function i.e. leftMinMax[2] = minMax(X, l, mid)
Step 4: Recursively find the maximum and minimum for right part by calling the same
function i.e. rightMinMax[2] = minMax(X, mid + 1, r)
Step 5: Finally, get the overall maximum and minimum by comparing the min and
max of both halves.
Step 6: Stop.
Source Code:
# Python program of above implementation
# structure is used to return two values from minMax()
class pair:
def __init__(self):
self.min = 0
self.max = 0
def getMinMax(arr: list, n: int) -> pair:
minmax = pair()
# If there is only one element then return it as min and max both
if n == 1:
minmax.max = arr[0]
minmax.min = arr[0]
return minmax
# If there are more than one elements, then initialize min
# and max
if arr[0] > arr[1]:
minmax.max = arr[0]
minmax.min = arr[1]
else:
minmax.max = arr[1]
minmax.min = arr[0]
for i in range(2, n):

Page | 25
 if arr[i] > minmax.max:
minmax.max = arr[i]
elif arr[i] < minmax.min:
minmax.min = arr[i]
return minmax

# Driver Code
if __name__ == "__main__":
arr = [1000, 11, 445, 1, 330, 3000]
arr_size = 6
minmax = getMinMax(arr, arr_size)
print("Minimum element is", minmax.min)
print("Maximum element is", minmax.max)

Result:
Thus the python program for finding maximum and minimum numbers in a given list
of n numbers using the divide and conquer technique was executed successfully and the
output was verified.

Page | 26
EXPT NO.: 12
MERGE SORT AND QUICK SORT
DATE :

Aim:
To write a python program to implement Merge sort and Quick sort methods to sort
an array of elements and determine the time required to sort. Repeat the experiment for
different values of n, the number of elements in the list to be sorted and plot a graph of the
time taken versus n.
Algorithm:
Merge Sort:
step 1: start
step 2: declare array and left, right, mid variable
step 3: perform merge function.
if left > right
return
mid= (left+right)/2
mergesort(array, left, mid)
mergesort(array, mid+1, right)
merge(array, left, mid, right)
step 4: Stop
Quick Sort:
Step 1: Create a recursive function (say quicksort()) to implement the quicksort.
Step 2: Partition the range to be sorted (initially the range is from 0 to N-1) and
return the correct position of the pivot (say pi).
• Select the rightmost value of the range to be the pivot.
• Iterate from the left and compare the element with the pivot and
perform the partition as shown above.
• Return the correct position of the pivot.
Step 3: Recursively call the quicksort for the left and the right part of the pi.
Source Code:
Merge Sort:
# MergeSort in Python
def mergeSort(array):
if len(array) > 1:
# r is the point where the array is divided into two subarrays
r = len(array)//2
L = array[:r]
M = array[r:]
# Sort the two halves
mergeSort(L)
mergeSort(M)
i=j=k=0
# Until we reach either end of either L or M, pick larger among
Page | 27
 # elements L and M and place them in the correct position at A[p..r]
while i < len(L) and j < len(M):
if L[i] < M[j]:
array[k] = L[i]
i += 1
else:
array[k] = M[j]
j += 1
k += 1
# When we run out of elements in either L or M,
# pick up the remaining elements and put in A[p..r]
while i < len(L):
array[k] = L[i]
i += 1
k += 1
while j < len(M):
array[k] = M[j]
j += 1
k += 1

# Print the array

def printList(array):
for i in range(len(array)):
print(array[i], end=" ")
print()

# Driver program
if __name__ == '__main__':
array = [6, 5, 12, 10, 9, 1]

mergeSort(array)

print("Sorted array is: ")

printList(array)
Quick Sort:
# Quick sort in Python
# function to find the partition position
def partition(array, low, high):
# choose the rightmost element as pivot
pivot = array[high]
# pointer for greater element
i = low - 1
# traverse through all elements
# compare each element with pivot
for j in range(low, high):

Page | 28
 if array[j] <= pivot:
# if element smaller than pivot is found
# swap it with the greater element pointed by i
i=i+1
# swapping element at i with element at j
(array[i], array[j]) = (array[j], array[i])
# swap the pivot element with the greater element specified by i
(array[i + 1], array[high]) = (array[high], array[i + 1])
# return the position from where partition is done
return i + 1

# Function to perform quicksort

def quicksort(array, low, high):
if low < high:
# Find pivot element such that
# element smaller than pivot are on the left
# element greater than pivot are on the right
pi = partition(array, low, high)
# Recursive call on the left of pivot
quicksort(array, low, pi - 1)
# Recursive call on the right of pivot
quicksort(array, pi + 1, high)a

# Driver code
if __name__ == '__main__':
array = [10, 7, 8, 9, 1, 5]
N = len(array)
# Function call
quicksort(array, 0, N - 1)
print("Sorted array:")
for x in array:
print(x, end=" ")

Result:
Thus the python program Merge sort and Quick sort methods for was executed
successfully and the output was verified.

Page | 29
 EXPT NO.: 13
N Queens problem using
DATE : Backtracking
Aim:
To write a python program to implement N Queens problem using Backtracking.
Algorithm:
Step 1: Initialize an empty chessboard of size NxN.
Step 2: Start with the leftmost column and place a queen in the first row of that
column.
Step 3: Move to the next column and place a queen in the first row of that column.
Step 4: Repeat step 3 until either all N queens have been placed or it is impossible
to place a queen in the current column without violating the rules of the problem.
Step 5: If all N queens have been placed, print the solution.
Step 6: If it is not possible to place a queen in the current column without violating
the rules of the problem, backtrack to the previous column.
Step 7: Remove the queen from the previous column and move it down one row.
Step 8: Repeat steps 4-7 until all possible configurations have been tried.
Source Code:
# Python program to solve N Queen
# Problem using backtracking
global N
N=4
def printSolution(board):
for i in range(N):
for j in range(N):
print (board[i][j],end=' ')
print()

# A utility function to check if a queen can

# be placed on board[row][col]. Note that this
# function is called when "col" queens are
# already placed in columns from 0 to col -1.
# So we need to check only left side for
# attacking queens
def isSafe(board, row, col):
# Check this row on left side
for i in range(col):
if board[row][i] == 1:
return False
# Check upper diagonal on left side
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False

Page | 30
 # Check lower diagonal on left side
for i, j in zip(range(row, N, 1), range(col, -1, -1)):
if board[i][j] == 1:
return False
return True

def solveNQUtil(board, col):

# base case: If all queens are placed
# then return true
if col >= N:
return True
# Consider this column and try placing
# this queen in all rows one by one
for i in range(N):
if isSafe(board, i, col):
# Place this queen in board[i][col]
board[i][col] = 1

# recur to place rest of the queens

if solveNQUtil(board, col + 1) == True:
return True
# If placing queen in board[i][col
# doesn't lead to a solution, then
# queen from board[i][col]
board[i][col] = 0
# if the queen can not be placed in any row in
# this column col then return false
return False

# This function solves the N Queen problem using

# Backtracking. It mainly uses solveNQUtil() to
# solve the problem. It returns false if queens
# cannot be placed, otherwise return true and
# placement of queens in the form of 1s.
# note that there may be more than one
# solutions, this function prints one of the
# feasible solutions.
def solveNQ():
board = [ [0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
if solveNQUtil(board, 0) == False:
print ("Solution does not exist")
return False
printSolution(board)

Page | 31
 return True
# driver program to test above function
solveNQ()

Result:
Thus the python program Merge sort and Quick sort methods was executed
successfully and the output was verified.

Page | 32
EXPT NO.: 14
TRAVELING SALESPERSON
DATE : PROBLEM
Aim:
To write a python program to implement any scheme to find the optimal solution for
the Traveling Salesperson problem and then solve the same problem instance using any
approximation algorithm and determine the error in the approximation.
Algorithm:
Step 1: Start on an arbitrary vertex as current vertex.
Step 2: Find out the shortest edge connecting current vertex and an unvisited
vertex V.
Step 3: Set current vertex to V.
Step 4: Mark V as visited.
Step 5: If all the vertices in domain are visited, then terminate.
Step 6: Go to step 2.
Step 7: The sequence of the visited vertices is the output of the algorithm.
Source Code:
# Python3 program to implement traveling salesman
# problem using naive approach.
from sys import maxsize
from itertools import permutations
V=4

# implementation of traveling Salesman Problem

def travellingSalesmanProblem(graph, s):

# store all vertex apart from source vertex

vertex = []
for i in range(V):
if i != s:
vertex.append(i)

# store minimum weight Hamiltonian Cycle

min_path = maxsize
next_permutation=permutations(vertex)
for i in next_permutation:
# store current Path weight(cost)
current_pathweight = 0
# compute current path weight
k=s
for j in i:
current_pathweight += graph[k][j]

Page | 33
 k=j
current_pathweight += graph[k][s]
# update minimum
min_path = min(min_path, current_pathweight)
return min_path

# Driver Code
if __name__ == "__main__":
# matrix representation of graph
graph = [[0, 10, 15, 20], [10, 0, 35, 25],
[15, 35, 0, 30], [20, 25, 30, 0]]
s=0
print(travellingSalesmanProblem(graph, s))

Result:
Thus the python program to find the optimal solution for the Traveling Salesperson
problem to find the optimal solution for the Traveling Salesperson problem was executed
successfully and the output was verified.
Page | 34
EXPT NO.: 15
FINDING THE K TH SMALLEST
DATE : NUMBER
Aim:
To write a python program to implement randomized algorithms for finding the kth
smallest number.
Algorithm:
Step 1: find the k'th element in A using 'selection algorithm', let it be 'z'
Step 2: initialize an empty list 'L'
Step 3: initialize counter<-0
Step 4: for each element in A:
4.1: if element < z:
4.1.1: counter<-counter + 1 ; L.add(element)
Step 5: for each element in A:
5.1: if element == z AND count < k:
5.1.1: counter<-counter + 1 ; L.add(element)
Step 6: return L
Source Code:
# Python3 implementation to solve k queries
# for given n ranges
# Structure to store the
# start and end point
class Interval:
def __init__(self, s, e):
self.s = s
self.e = e
# Python3 implementation to solve k queries
# for given n ranges
# Structure to store the
# start and end point
class Interval:
def __init__(self, s, e):
self.s = s
self.e = e

# Function to find Kth smallest number in a vector

# of merged intervals
def kthSmallestNum(merged: list, k: int) -> int:
n = len(merged)
# Traverse merged[] to find
# Kth smallest element using Linear search.
for j in range(n):

Page | 35
 if k <= abs(merged[j].e - merged[j].s + 1):
return merged[j].s + k - 1
k = k - abs(merged[j].e - merged[j].s + 1)
if k:
return -1

# To combined both type of ranges,

# overlapping as well as non-overlapping.
def mergeIntervals(merged: list, arr: list, n: int):

# Sorting intervals according to start

# time
arr.sort(key = lambda a: a.s)
# Merging all intervals into merged
merged.append(arr[0])
for i in range(1, n):
# To check if starting point of next
# range is lying between the previous
# range and ending point of next range
# is greater than the Ending point
# of previous range then update ending
# point of previous range by ending
# point of next range.
prev = merged[-1]
curr = arr[i]
if curr.s >= prev.s and curr.s <= prev.e and\
curr.e > prev.e:
merged[-1].e = curr.e
else:
# If starting point of next range
# is greater than the ending point
# of previous range then store next range
# in merged[].
if curr.s > prev.e:
merged.append(curr)

# Driver Code
if __name__ == "__main__":
arr = [Interval(2, 6), Interval(4, 7)]
n = len(arr)
query = [5, 8]
q = len(query)
# Merge all intervals into merged[]
merged = []
mergeIntervals(merged, arr, n)
# Processing all queries on merged
# intervals

Page | 36
 for i in range(q):
print(kthSmallestNum(merged, query[i]))

Result:
Thus the python program to implement randomized algorithms for finding the kth
smallest number was executed successfully and the output was verified.

Page | 37