.

O
.
•/ S”
ESTD. 2001

PRATHYUSHA ENGINEERING COLLEGE

DEPARTMENT OF COMPUTER SCIENCE A HB GINEERING

LAB MANU

CS3401-ALGO S LABORATORY

(ReguléiJon 2021, IV Semester)

(Even Semester)

» \ACADEMIC YEAR: 2023 — 2024

PREPARED BY
S.FAMITHA,
Assistant Professor / CSE
 1. SEARCHING AND SORTING ALGORITHMS

a. Implement I.inear 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.

Write a Python program to search an element using Linear search method

and plot a graph of the time taken versus n.

“
1. Start from the first element of the list and compare e Search element.
2. If the Search element is found, return the index of
-
3. If the Search element is not found, move to the t element and repeat
the comparison.
4. Repeat this rent is found or the end of
the
proi list is
5. reached. If the urn -1 to indicate that
the
Search eli
The algorithm to pa rersus n for linear search is as

Initia n irray time taken to store the time taken to perform

linear sq fo ’ferent values of n.
r inge 1 to n, do the following:
a. Generate a list of i elements.
b. Record the start time start time just before performing linear search on
the list.
c.Perform linear search on the list.
d.Record the end time end time just after performing linear search on
the list.
e. Calculate the time taken as time taken[i] - end time - start time.
3. Plot a graph with n on the x-axis and time taken on the y-axis.

1
 import matplotlib.pyplot as plt
def linear search(arr, x):
for i in range(len(arr)):
if arr[i] -- x:
return i
return - l
arr - [ 2, 3, 4, 10. 40 ]

# Function call
result - linear search(arr, x)

print(”Element is not present in array

print(”Element is present at index",

result)
[10, 20, 50, 100, 200, SOA, 1000]
1.0f175, 0.0150]
time = [0.0001, 0.0003, 0.0005, 0.0015,
plt.plot(n, time)
plt.x1abe1('Number of Elements’)
plt.y1abe1('Time Taken’)
plt.title('Time Complexity of Search')
p1t.show()

Output:

Time Com pl ex ity of Line a r gea rch

2
b. 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.

Write a Python program to search an element using Binary search method and
plot a graph of the time taken versus n.

1. Given a sorted list of elements, start by finding the middle element.

2. Compare the search element with the middle element.
3. If the search element is equal to the middle element,
index of the middle
return element.
4. If the search element is less than the middle eleme epeat the process on the left
half of the list (before the middle element)
e
5. If the search element is greater than the element, repeat the process on the
right half of the list (afier the middle ent).
6. Repeat steps l and 2 until either.tha . earch element is found or the list has
been fully searched and the searc sent is not present.
7. If the search element und, return -1 to indicate that the element is not
is present in the list.
Note: The list must bend in ascending or descending order for binary search to work.

The algorithm to p graph of the time taken versus n for linear search is as follows:

1. Initializ an array time taken to store the time taken to perform binary search
for different values of n.
2. For i in the range 1 to n, do the following:
a. Generate a sorted list of i elements.
b. Record the start time start time just before performing binary search on
the list.
c. Perform binary search on the list.
d. Record the end time end time just after performing binary search on the list.
e. Calculate the time taken as time taken[i] - end time - start time.
3. Plot a graph with n on the x-axis and time taken on the y-axis.

3
def binary search(arr, x):
low - 0
high - len(arr) - I
mid - 0
while low <- high:
mid - (high + low) // 2
lI Check if x is present at mid
if arr[mid] < x:
low - mid + I
# If x is greater, ignore lefi half
elif arr[mid] > x:
high - mid - 1

# If x is smaller, ignore right half

else:
return mid
# If we reach here, then the elemen no
return -I
# Test array
arr - [2, 3, 4, 10, 40]
x - 10
# Function call
result - binary s
if result !- -1:
print(”Element is present at index", str(result))
else:
print(”Element is not present in array”)
import matplot1ib.pyplot as plt
# X-axis for time
complexity X -
[0,1,2,3,4,5,6.7,5,9,10]
# Y-axis values for time complexity
Y - [0,1,4,9,16,25,36,49,G4,S l, 100]
# Plot the graph

4
plt.plot(X,Y)
# Set the x-axis label
plt.x1abel('Input Size (n)’)
# Set the y-axis label
plt.ylabel('Tone Complexity (n^2)')
# Title of the graph
plt.title('Time complexity graph of Binary search')
# Show the plot
p1t.show()

k Figure 1

Time complexity graph of Binary search

100

80

40
20

0 2 4 10

S
c. 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.

Write a Python program for pattern matching.

Algorithm:
1. Given a target string text and a pattern string pattern, initialize two pointers, i and j, to
traverse both strings.
2. Compare the characters of the target string and pattern string at the current positions of

a. If the characters match, move both pointers to the next ions

b. If the characters do not match, reset j to the st tion of the pattern
string and move i to the next position in the tar tring.
3. Repeat steps 2 until either j has reached the endattern string (indicating a
match) or i has reached the end of the target (indicating no match).
4. Ifj has reached the end of the pattern s turn the index in the target string where
the match starts. If i has reached th the target string, return -1 to indicate
that the pattern is not present in the string.

def search(pat, txt):

M - 1en(pat)
N - len(
e( M + 1):

for j in range(M):
if txt[i + j] !- pat[j]:
break
ifj -- M - 1:
print("Pattern found at index ", i)
txt - "AABAACAADAABAAABAA"
pat - "AABA"
search(pat, txt)

6
Output:
Pattern found at index
0 Pattern found at
index 9 Pattern found at
index 13

7
d. 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.

i) Insertion Sort:

Write a Python program to sort the element using insertion sort method and
plot a graph of the time taken versus n.

1. Given an array of elements start with the second element.

F'or each element in the array, compare it with the ele to its lefi, swapping
it with the element to its lefi until it is in its coi p ion in the sorted
portion of the array.
3. Repeat steps 2 for all elements in the

The algorithm to plot a graph in ne taken versus n for insertion sort is

as follows:
1. Initialize an array to store the time taken to perform insertion sort for
time different values
of
2. For i in the rang o n, do the following:
a. a list of i elements.
ie start time start time just before performing insertion sort on the
list.
c. Perform insertion sort on the list.
d. Record the end time end time just after performing insertion .sort on
the list.
e. Calculate the time taken as time taken[i] - end time - start time.
3. Plot a graph with n on the x-axis and time taken on the y-axis. This will give
you the graph of the time taken versus n for insertion sort.
Program:
# Function to do insertion sort
def insertionSort(arr):
lI Traverse through 1 to 1en(arr)
for i in range(1, len(arr)):
key - arr[i]
# Move elements of arr[0..i-I], that
are # greater than key, to one position
ahead # of their current position

while j >-0 and key < arr[j] :

arr[j+1] - key
# Driver code to test above

- int(input(”Enter number of ele

for i in range(0, n):
element - int(input(”Enter elerr
e
arr.append(element)
insertionSort(arr)
print (”Sorted array
for i in range(len(
print ( % d"

x - [2, 3, 4, 5, 6, 7, S, 9, 10]
y - [0, 0, 0.1, 0.3, 0.5, 0.7. 1.0, 1.3, 1.5]
plt.plot(x, y)
plt.x1abel(’Size of
array')
plt.ylabel(’Complexity')
plt.title('Time Complexity of Insertion Sort')
plt.show()

9
 “ *'9ure

Time Complexity of Insertion Sort

.00

50

00

Heap Sort:
Aim:
Write a Python program to sort the elements g heap sort method and plot
a graph of the time taken versus n.

Algorithm:
1. Build a max-heap from the ay of elements.
in
2. ) of the heap with the last element of the
Swap the root (maximum v heap.
3. Discard the last he heap, which is now in its correct position in
eleme the
sorred array. “
4. Rebuild the leap, excluding the last
element.
5. Repeat to 4 until all elements are in their correct positions in the
sorted

The algorithm to plot a graph of the time taken versus n for heap sort is as
follows:
1. Initialize an array time taken to store the time taken to perform heap sort
for different values of n.
2. For i in the range 1 to n, do the following:
a. Generate a list of i elements.
b. Record the start time start time just before performing heap sort on the list.
c. Perform heap sort on the list.
d. Record the end time end time just afier performing heap sort on the list.
e. Calculate the time taken as time taken[i] - end time - start time.
10
 3. Plot a graph with n on the x-axis and time taken on the y-axis. This will give
you the graph of the time taken versus n for heap sort.

def heapSorr(arr):
n - len(arr)
for i in range(n, -1, -I):
heapify(arr, n, i)
for i in range(n-I, 0, -I):
arr[i], arr[0] - arr[0], arr[i]
heapify(arr, i, 0)
arr - [ 12, 11, 13, 5. 6, 7]

n - len(arr)
print (”Sorted array is
for i in range(n):

import timeit
import matplotlib.pyplot as plt
# list of integers to be sorted
list length -
I ,50f100,60000]
[10000,20000,300f1
r each
\ list
time_taken - [) .M
oug
h
length))
:
# code snippef to be executed only once
setup code - "'
from heapq import heappush, heappop
from random import randint”’
# code snippet whose execution time is to be measured
test code - "'
l - [)

11
Output:

HeapSort
004

0.03

* 0.02

0.01

10000 20000 30000 40000 50000 60000

12
 2. GRAPH ALGORITHMS:
a. Develop a program to implement graph traversal using Breadth
First Search from collections import defaultdict

Write a Python program to perform graph traversal using Breadth First Search

1. Create an empty queue and push the starting node onto it.
2. Repeat the following steps until the queue is empty:
a. Dequeue a node from the queue and mark it as visited.
b. For each unvisited neighbor of the current node, mark it as visited
and enqueue it.
3. Once the queue is empty, the algorithm is complete.

class Graph:
def init (self):
self.graph - defaultdict(list)
def addEdge(self, u, v):
self.graph[u].append(v)
def BFS(self, start):
visited - let .graph)
[False] queue -
[]
queue.appen rt)
visited - True
wht1+true:
start - queue.pop(0)
print(start, end-" ”)
for i in self.graph[start]:
if not visited[i]:
queue.append(i
) visited[i] -

True

g - Graph()
g.addEdge(0, I)
g.addEdge(0, 2)
13
 g.addEdge( 1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
print("Following is Breadth First Traversal” " (starting from vertex
2)") g.BFS(2)

Output:
Following is Breadth First Traversal (starting from vertex
2) 2 0 3 I

14
 b. Develop a program to implement graph traversal using Depth First

Program:

Write a Python program to perform graph traversal using depth First Search

Algorithm:
1. Create a stack and push the starting node onto it.

2. Repeat the following steps until the stack is empty:

Pop a node from the stack and mark it as visited.

b. e, as visited and

Once the stack is empty, the algorithm is .“

# define a graph
graph - {
'A' : ['B','C'],
'B' : ['D'. 'E'],
'C' : ['F’],

visited
# Set to keep track of visited nodes.
'

print("The DFS Traversal : Node visited order

is") def dfs(visited, graph, node):
if node not in visited: # if the node is not visited then visit it and add it to the
visited set.
print (node) # print the node.
visited.add(node) # add the node to the visited set.
for neighbour in graph[node] : # for each neighbour of the current node do
a recursive call.
dfs(visited, graph, neighbour) # recursive call.
15
Output:
The DFS Traversal : Node visited order is
A

B
D

E
F
C

16
 c. From a given vertex in a weighted connected graph, develop a
program to find the shortest pathsto other vertices using Dijkstra's
algorithm.

Write a Python program to find the shortest paths to other vertices using
Dijkstra's algorithm in a weifgted graph.

Algorithm:
1. Create a set S to keep track of visited vertices, and initialize it with the
starting vertex.
2. Create a priority queue Q to keep track of unvisited vertic
distances, and initialize it with the starting vertex and a dance of 0.
3. Repeat the following steps until Q is empty:
Dequeue the vertex u with the minimu tance from Q.
ii. Add u to S.
iii. For each neighbor v of u:
iv. If v is already in ! tins
v. If the distance to thro h is less than its current distance, update its

4. Once Q is empty, th res to all vertices have been determined.

graph -
?':1),
'B’:J " '" 2,
'C’: (’A': I, 'B': 2, 'D': 4, ’E': 8},
'D': {’B': I, 'C': 4, 'E': 3, 'F’: 6},
'E’: ('C': 8, 'D': 3},
'F': {’D': 6)

def
dijkstra(graph,start,goal):
shortest distance - ( )

17
predecessor - { }
unseenNodes - graph

18
 infinity -
99999 path - []
for node in unseenNodes:
shortest distance[node] - infinity
shortest distance[start] - 0
while unseenNodes:
minNode -
None
for node in
unseenNodes: if
minNode is None:
minNode - node
elif shortest distance[node] < shortest distance[minNode]
minNode
for enrich one, weignt in grapnt mine one j.itemst):
if weight + shortest distance[minNode] <
.shortest distance[childNode]:
shortest distance[childNode] - " + shortest distance[minNode]
predecessor[childNode] -
unseenNodes.pop(minNode) -
currentNode - goal
while currentNode
!-
try:
path.insert entNode)
curre e-
predecessor[currentNode] exe
eyError:
print(’Path not reachable')
break
path.insert(0,start)
if shortest distance[goal] !- infinity:
print(’Shortest distance is ' + str(shortest distance[goal]))
print(’And the path is ' + str(path))
dijkstra(graph, 'A', 'F')
Output:
Shortest distance is 10
And the path is ['A', 'C', 'B', 'D', 'F']
d. Find the minimum cost spanning tree of a given undirected graph using
Prim's algorithm.

Write a Python program to Find the minimum cost spanning tree of a

given undirected graph using Prim's algorithm.

Algorithm:
1. Create a set V to keep track of visited vertices, and initialize it with
an arbitrary starting vertex.
2. Create a priority queue Q to keep track of unvisited verti their distances
to V, and initialize it with all vertices adjacent to the
vertex.
3. Repeat the following steps until V contains all ver
i. Dequeue the vertex u with the minimu tance from Q.
ii. Add u to V.
iii. For each unvisited neighbor v
iv. If v is already in V,
v. If the distance i thro h is less than its current distance in
Q, update its d .’ in Q.
4. Once V contains imum cost spanning tree has been
all constructed.
Program:
v=
grap ›, 0],

[0, 3, 0, 0, 7],
[6, 8, 0, 0, 9],
[0, 5, 7, 9, 0]]
def minKey(key, nistset):
# Initialize min
value min -
float('ink)
for v in range(V):

19
if key[v] < min and mstSet[v] --
False: min - key[v]

20
 min index - v
return min index
def primMST(graph):
key [float('infi)] *
V parent - [None] *
V
key[0] 0
mstset = [False] * V
parent[0] - - l
for cout in range(V):
u - minKey(key, mstset)
mstSet[u] - True
for v in range(V):
if graph[u][v] > 0 and mstSet[v] -- False and graph[u]
key [v]:
keyl•l - graph[ullv]
parent[v]

u print("Edge \tWeight")
for i in range(l,V):
print(parent[i],"-”,i,"\t",graph nt[i]
]) g - primMST(graph)

Edge ht
0- I
I-2
0-3 6
1—4 5

21
e. Implement Floyd's algorithm for the All-Pairs- Shortest-Paths problem.

Write a Python program to find all pairs — Shortest paths problem using
Floyd's algorithm

1. Create a table of distances between every pair of vertices in G

2. Initialize the shortest path table to be the same as the distance table
3. For k - 0 to k- l
i. For each pair of vertices (u, v) in G
ii. For each vertex w in the set of vertices V
iii. Set the shortest path between u and v to the min m of the current
shortest path and the sum of between u and w and
the w and v.
4. Return the shortest path table.

graph - [[0, 5, 9, 7],

[4, 0, 2, 8],
[3, 2, 0, I],
[6, 5, 2, 0]]
n - len(graph)
dist - [[float(’infi in range(n)] for j in
range(n)] for i in rangers
foi e(n)
[j] aph[i][j]
for k in
range(n): for i
in range(n):
for j in range(n):
dist[i][j) - min(dist[i](j], dist[i][k] + dist[k][j])
print(dist)

Output:
[[0, 5, 7, 7], [4, 0, 2, 3], [3, 2, 0, 1], [5, 4, 2, 0]]

22
f. Compute the transitive closure of a given directed graph using
Warshall's algorithm.

Write a Python program to compute the transitive closure of a directed

graph using Warshall's algorithm
Algorithm:
1. Create an adjacency matrix of the graph.
2. Initialize the matrix with the values of the graph.
3. For each vertex v, set the value of the matrix at row v and column v to 1.
4. For each pair of vertices (u, v), if there is an edge froi oust the value of
the matrix at row u and column v to 1.
5. For each triplet of vertices (u, v, w), if the value of uitrix at row u and
column v is 1 and the value of the matrix at round column w is 1, set
the
W

6. R!pedof hp 5 Until nd More dn e’ c ie. The matrix now contains the

transitive closure of the graph.

#De ne the graph

r
' A': QB', 'cJ, ,'?'“
'B’: [’C',

#Define a function to compute the transitive closure

def transitive closure(graph):
#Initialize the transitive closure matrix with 0s
closure matrix - [[0 for j in range(len(graph))] for i in range(len(graph))]
#Fill the closure matrix with I s for direct paths
for i in range(len(graph)):
for j in graph[list(graph.keys())[i]]:

23
closure matrix[i][list(graph.keys()). index(j)] - I

24
 #Compute the transitive closure using Warshall's algorithm
for k in range(len(graph)):
for i in range(len(graph)):
for j in range(len(graph)):
closure matrix[i][j] - closure matrix[i][j] or (closure nuitrix[i][k] and
closure matrix[k][j])
#Print the transitive closure matrix
for row in closure matrix:
print(row)
#Call the
transitive closure(graph)
function

[0, l, 1, 1]
[0, 0, 1, 1]
[0, 0, 1, 1]
[0, 0, 1, 1]

25
 3. ALGORITHM DESIGN TECHNIQUES:
a. Develop a program to find out the maximum and minimum numbers in a
given list of n numbersusing the divide and conquer technique.

Write a Python program to find out the maximum and minimum

numbers in a given list of n numbersusing the divide and conquer technique.

def find_max_min(numbers):

left_max, lefi _min(numbers[:mid])

right max, r min - find max min(numbers[mid:])
returned(lefi max, right max), min(left min, right min))
dri de
n bers - [3, 5, 2, 8, 1, 4, IO]
max num, min num - find max min(numbers)
print("Maximum number is:", max num)
print("Minimum number is:", min num)

Maximum number is: 10

Minimum number is: 1

26
b. 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 inthe list to be sorted and plot a graph of
the time taken versus n.

b.i ) Merge sort:

Write a Python program to sort the elements using merge sort and plot a
graph to the time taken versus n

Algorithm:
Merge Sorr is a divide and conquer algorithm. It input array in
two halve.s, calls itself for the two halves and then merges t wo sorred
halves.
1. Divide the unsorted array into n partitions, each ition contains 1 element.
2. Repeatedly merge partitioned units to prod ew sublists until there is only
l sublist remaining. This will be the sorted.
3. Compare the first element of the en t with the first element of the sublist to
its right.
4. Merge the two sublists by paring each element of the sublist and placing
the smaller element into thy w sublist.
5. Repeat step 3 and Oil all sublists are merged into a single sorted sublist.

Program:y
impo ime
imporr matplotlib
def merge sort(arr):
if len(arr) ml:
mid - len(arr)//2
L - arr[:mid]
R - arr[mid:]
merge sort(L)
merge .sort(R)

27
i- j- k- 0

28
 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+=l
k+—I
while i <
len(L): arr[k]
- L[i]

while j < len(R):

arr[k] - R[j]

n - [1000, 2000, 4000, 5000]

time taken - []
for i in n:
arr - [i for i in
range(i)] start time -
time.t merge sort(arr I
“ end
time .time()

time append(end time - start time)

impo atplotlib.pyplot as plt
plt.plot(n, time_taken)
plt.xlabe1(’Number of elements in the list')
plt.ylabel('Time taken to sort’)
plt.title(’Merge Sort')
plt.show()

29
 Merge Sort
0.010
0.008

0.006

0.004

0.002

0.000
1000 2000 3000 4000 5000 6000 7000 8000

30
b.ii) Quick Sort:

Write a Python program to sort the elements using quick sort and plot a
graph to the time taken versus n

1. Select a pivot element from the array.

2. Partition the array into two sub-arrays. The elements in the first sub-array
are less than the pivot element, while the elements in the second sub-
array are greater than the pivot element.
3. Recursively sort the sub-arrays created in Step 2.
4. Join the sub-arrays and the pivot element together to the sorted array.

import time
import matplotlib.pyplot as plt
def quick sort(arr):
if len(arr) <- 1:
return arr
pivot - arr[len(arr)//
lefi - [x for x in ar ñ < pivot]
middle - [x fork arr if x -- pivot]
right - [x in arr if x > pivot]
returned sort(lefi) + nuddle + quick sorr(right)
Gen ate an array of random numbers
arr - [5, 6, 7, S, 1, 2, 12, 14]
# Calculate the time taken to sort the array
start - time.time()
sorted arr - quick
sort(arr) end - time.time()
# Print the sorted array
print(”Sorted array:”, sorted arr)
# Calculate and print the time taken to sort the array
print(”Time taken:", end - start, "seconds”)

31
 # Plot a graph of the time taken versus n
n values - [ l0, 100, 1000, 10000]
time values - []
for n in n values:
arr - [i for i in range(n)]
start - time.time()
sorted arr - quick sort(arr)
end - time.time()
time values.append(end - start)
plt.plot(n values, time values)
plt.xlabel("n")
plt.ylabel("Time taken”)
plt.title("Quicksort”)
plt.show()

Output:

Quicksor
t
0150
.0125
.010D
0075

.0030
0025
.0000
D 2000 4000 6000 8D0O

l0ODO

32
 4. STATE SPACE SEARCH ALGORITHMS:
a. Implement N Queens problem using Backtracking.

Write a Python program to solve N- Queens problem using backtracking.

// Create an empty array of size n

// Create a function to check if a queen can be placed in a given row

and column

// Create a function to place a queen in a given row and column

// Create a function to remove a queen from a given row and umn

// Function to check if a queen can be placed in a row and column

func canPlaceQueen(row, col int, board[][] ipt Vol (

// Check if any other queen is the same row

p for i :- 0; i < len(board);

if boarc

false

// Check if other queen is placed in the same

column for J< len(board); i++ (

if board[i][col] -- l

// Check if any other queen is placed in the diagonal

for i, j :- row, col; i >- 0 && j >- 0; i, j - i-1, j- l {

if board[i][j] -- 1 {

return false

for i, j :- row, col; i < len(board) && j >- 0; i, j i+1, j-1

( if board[i][j] -- l

return false

return true }

33
 // Function to place a queen in a given row and column

func placeQueen(row, col int, board[][] int) {

board[row][col] - 1 )

// Function to remove a queen from a given row and column

func removeQueen(row, col int, board[][] int) {

board[row][col] - 0 }

// Function to solve the n queens problem using backtracking

func solveNQueens(board[][] int) bool (

if len(board) -— 0 (

return true

for i :- 0; i < len(board); i++ (

for j :- 0; j < len(board); j+

if canPlaceQue j, board)

pl een(i, j, board)

soiveNQueens(board)
{

return true

# N-Queens problem using Backtracking

# global variable for bo:ird
board - []
# function to print the
board def print
board(board):
for i in range(len(board)):
for j in range(len(board[0])):
print(board[i][j], end - " ")
34
print()

35
# function to cheek if a queen can be placed in a position
def is_safe(board, row, col):
# check row
for i in range(col):
if board[row][i] ==
1: return False
# check upper diagonal
for i, j in zip(range(row, -1, -1), range(col, -1, -
1)): if board[i][j] == 1:
return False
# check lower diagonal
for i, j in zip(range(row, 1en(board)), range(col, -1, -
I)): if board[i][j] == 1:
return False
return True
# function to solve the N-Queens problem
def so1ve_n_queens(board, col):
# base case
if col >= len(board):
return True
# iterate through all
for i in range(Ie d)):
if is_safe , i,
col):
card[i][col] = 1
# recur to place rest of the queens
if solve n queens(board, eo1+ I) == True:
return True
# backtrack
board[i][col] =
0
return
False # driver
code
if name —— " main
36
” # size of board

37
n - int(input(”Enter the size of board:
”)) # create an empty board
board - [[0 for j in range(n)] for i in range(n)]
if solve n queens(board, 0) -- False:
print(”Solution does not exist")
else:
print_board(board)

Enter the size of board: 4

0010
1000
000 I
0100

38
5. APPROXIMATION ALGORITHMS RANDOMIZED ALGORITHMS:

a. 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

Write a Python program to find the optimal solution for the Travelling
Salesperson problem using approximation algorithm and determine the error in

Initialize the solution with the first city as the ’

starti oint.
2. Calculate the distance from the curre o her cities.
3. Select the nearest city from the curre it it as visited.
4. Calculate the total distance travell
5. Repeat steps 2-4 until all cities
6. Calculate the total distance
7 Compare the total c’ any velled with the optimal .solution.
s If the total distance tr e 1 I is less than the optimal solution, then the
current solution is the ximate solution.
9. If the total ce travelled is more than the optimal solution, then repeat steps 2-
7 usin erent starting city.

llimporting
libraries imporr
nuinpy as np
imporr math
#defining the distance matrix
dist matrix - np.array([[0, IO, 15, 20],
[l0, 0, 35, 25],

39
[IS, 35, 0, 30],
[20, 25, 20, 0]])

40
lldefining the cost matrix
cost matrix - np.array([[0, 10, 15, 20],
[ l0, 0, 35, 25],
[l5, 35, 0, 30],
[20, 25. 20, 0]])
lldefining the number of
cities num cities - 4
#defining the optimal solution function
def opt solution(dist matrix, cost matrix, num cities):
#initializing the cost matrix
cost matrix - np.zeros((num cities, num cities))
#initializing the visited array
visited - [False] * num cities
#initializing the current city
current_city - 0
#initializing the total
cost total cost - 0
#updating the visited
array visited[current city]
- Tri #looping through
the cry
for i in range(num c’ s - I ):
#initial n cost
#i co ing the
ath.inf
next
city t city
#looping through the
cities for j in range(num
cities):
#checking if the city has been visited
if visited[j] -— False:
#checking if the cost is less than min cost
if cost matrix[current city][j] < min cost:
#updating the min cost
min cost - cost matrix[current city][j]
#updatinO the next city
41
 next city - j
#updating the total cost
total_cost +- min_cost
#updating the visited array
visited[next city] - True
#updating the current city
current city - next city
#returninO the total cost
return total cost

#calculating the optimal solution

opt sol - opt so1ution(dist matrix, cost matrix, num citie
#printing the optimal solution
print("Optimal Solution: ", opt sol)
#defining the approximation
algorithm def approx_‹
#initializii
cost cities))
matr
#initializii

#initializii u c’
current city -
#initializi total cost

vis d city] - True

for i in range(num cities - I):
#initializing the min cost
win cost - math.inf
#initializing the next city
next city - 0
#looping through the cities
for j in range(num cities):
if visited[j] == False:
if dist matrix[current city][j] < min cost:

42
 #updating the min cost
min cost - dist matrix[current city][j]
#updatinO the next city
next city - j
total_cost +- min cost
#updating the visited array
visited[next_city] - True
#updating the current city
current city - next city
#returning the total cost
return total cost
approx sol - approx algorithm(dist matrix, cost matrix, nu ities)
Sprinting the approximated solution
print("Approximated Solution:
#calculating the error
error - opt sol - approx sol
Sprinting the error

Output:

43
 b Implement randomized algorithms for finding the k" smallest number.

Write a Python program to find the kth smallest number using randomized
algorithm

1. Create an array of size n, where n is the number of elements in the array.

2. Randomly select an element from the array and store it in a variable.

3. Compare the randomly selected element with the kth smallest element.

4. If the randomly selected element is smaller than the kth smallest element,
then replace the kth smallest element with the randomly selected cient.

5. Repeat steps 2-4 until the kth smallest element is founds

import random
def kthSmallest(arr,
k):
n - len(arr)
temp - arr[:k] x
rando (
m
range n :
’ c):
n
if arr[i] < temp[j):
temp[j] -
arr[i]
break
return temp[k - 1]
# Driver Code
arr - [12, 3, 5, 7, 19]
k- 2
print(”K'th siTiallest element is", kthSma1lest(arr, k))

Output:
K'th smallest element is 5

44