TAGORE ENGINEERING COLLEGE

Rathinamangalam, Chennai-127.

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

CS3401 ALGORITHMS LABORATORY

2021 REGULATION

NAME : ________________________________

REG NO : ____________________________________

BRANCH : _________________________________

YEAR : ____________________________________

SEMESTER : ___________________________________

Anna University :: Chennai

 TAGORE ENGINEERING COLLEGE
RATHINAMANGALAM, CHENNAI-600127

LABORATORY RECORD

UNIVERSITY REGISTER NO.

Certified that this is the bonafide record of work done by

Mr. /Ms. of

Department in the Laboratory

and submitted for University Practical Examination conducted on

at TAGORE ENGINEERING COLLEGE, CHENNAI-127.

Record Marks .

Lab In-charge Principal Head of the Department

External Examiner Internal Examiner

 VISION

To create an environment which is conducive to produce competent Computer Science Engineers

through quality education and research-oriented education and equip them for the needs of the industry and
society.

MISSION

The Department strives to contribute to the expansion of knowledge in the discipline of

Computer Science and Engineering by

 Adopting an efficient teaching learning process in concurrence with increasing industrial demands.
 Ensuring technical proficiency, facilitating to pursue higher studies and carry out Research &
Development activities.
 Developing problem solving and analytical skills with deep knowledge in thorough understandingof
basic sciences
 and Computer Science Engineering.
 Infusing managerial and entrepreneurship skills to become ethical, socially responsible, and
competitive professionals.

PROGRAM SPECIFIC OBJECTIVES (PSOs)

1. Exhibit design and programming skills to build and automate business solutions using cutting edge
technologies

2. Strong theoretical foundation leading to excellence and excitement towards research, to provide elegant
solutions to complex problems.

3. Ability to work effectively with various engineering fields as a team to design, build and develop system
applications.
PROGRAM OUTCOMES POs

Engineering Graduates will be able to:

1. Engineering knowledge: Apply the knowledge of mathematics, science, engineering fundamentals

and an engineering specialization to the solution of complex engineering problems.

2. Problem analysis: Identify, formulate, review research literature, and analyze complex engineering
problems reaching substantiated conclusions using first principles of mathematics, natural sciences,
and engineering sciences.

3. Design/development of solutions: Design solutions for complex engineering problems and design
system components or processes that meet the specified needs with appropriate consideration for the
public health and safety, and the cultural, societal, and environmental considerations.
 4. Conduct investigations of complex problems: Use research-based knowledge and research methods
including design of experiments, analysis and interpretation of data, and synthesis of theinformation
to provide valid conclusions.

5. Modern tool usage: Create, select, and apply appropriate techniques, resources, and modern
engineering and IT tools including prediction and modeling to complex engineering activities with an
understanding of the limitations.

6. The engineer and society: Apply reasoning informed by the contextual knowledge to assess societal,
health, safety, legal and cultural issues and the consequent responsibilities relevant to the professional
engineering practice.

7. Environment and sustainability: Understand the impact of the professional engineering solutions in
societal and environmental contexts, and demonstrate the knowledge of, and need for sustainable
development.

8. Ethics: Apply ethical principles and commit to professional ethics and responsibilities and normsof
the engineering practice.

9. Individual and team work: Function effectively as an individual, and as a member or leader in
diverse teams, and in multidisciplinary settings.

10. Communication: Communicate effectively on complex engineering activities with the engineering
community and with society at large, such as, being able to comprehend and write effective reports
and design documentation, make effective presentations, and give and receive clear instructions.

11. Project management and finance: Demonstrate knowledge and understanding of the engineering
and management principles and apply these to one‘s own work, as a member and leader in a team, to
manage projects and in multidisciplinary environments.

12. Life-long learning: Recognize the need for, and have the preparation and ability to engage in
independent and life-long learning in the broadest context of technological change

Course Outcomes

CO1: Analyze the efficiency of algorithms using various frameworks

CO2: Apply graph algorithms to solve problems and analyze their efficiency.
CO3: Make use of algorithm design techniques like divide and conquer, dynamic programming
andgreedy techniques to solve problems
CO4: Use the state space tree method for solving problems.
CO5: Solve problems using approximation algorithms and randomized algorithms
 TABLE OF CONTENTS
Ex.No. Date Title of the Experiments Page No. Marks Signature

1
Implement linear search

2 Implement recursive binary search

3 String matching algorithm

4 Insertion sort and Heap sort

5 Implement Breadth First Search

6 Implement Depth First Search

7 Implement Dijkstra’s algorithm

8 Implement Prim’s algorithm

9 Implement Floyd’s algorithm

10 Warshall's algorithm

11 Minimum and Maximum number

using the divide and conquer
technique
12 Merge sort and Quick sort

13 Implement N Queens problem

14 Implement Traveling Salesman

problem using Approximation
algorithm
15 Implement randomized algorithms
for finding the kth smallest
number
Ex.No: 1 IMPLEMENT LINEAR SEARCH
Date:

AIM:

To implement Linear search and determine the time required to search an element and
plot a graph of time Taken versus n.

ALGORITHM:

Step 1: Start.

Step 2: Define linear search function.

Step 3: Define run-experiment to find the time taken.

Step 4: Create an array with number of elements in the list to find the time taken.

Step 5: Plot the time taken vs n using pyplot.

Step 6: Stop.

PROGRAM:

import time

import matplotlib.pyplot as plt

def linear_search(arr,x):

for i in range(len(arr)):

if arr[i]==x:

return i

return-1

def run_experiment(n):
 arr=list(range(n))

x=n-1

start=time.time()

result=linear_search(arr,n)

end=time.time()

print(n,”:”,end-start,”is the time taken”)

return(end-start)

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

times=[run_experiment (n)for n in ns]

plt.plot(ns,times)

plt.xlabel(“n”)

plt.ylabel(“times(n)”)

plt.title(“Time taken for linear search”)

plt.show()

OUTPUT:

Result:

Thus the program has been executed successfully

Ex.No:2 IMPLEMENT RECURSIVE BINARY SEARCH
Date:

AIM:

To implement recursive binary search and determine the time required to search an
element and plot a graph of time Taken versus n.

ALGORITHM:

Step1: Start.

Step 2: Define recursive binary search.

Step 3: Import time module to determine the time taken to search an element.

Step 4: Plot the time taken vs n using pyplot.

Step 5: Stop.

PROGRAM:

import time

import matplotlib.pyplot as plt

def binary_search(arr,low,high,x):

if low<=high:

mid=(low+high)//2

if (arr[mid]==x):

return mid

elifarr[mid]<x:

return binary_search(arr,mid+1,high,x)

else:

return binary_search(arr,low,mid-1,x)
 else:

return -1

def run_experiment(n):

arr=list(range(n))

x=n-1

start_time=time.time()

result=binary_search(arr,0,n-1,x)

end_time=time.time()

print(n,”:”,end_time-start_time,”is the time taken”)

return (end_time-start_time)

ns=[10,100,1000,10000,100000]

times=[run_experiment(n) for n in ns]

plt.plot(ns,times)

plt.xlabel(“n”)

plt.ylabel(“times(s)”)

plt.title(“time taken for binary search”)

plt.show()
OUTPUT:

RESULT:

Thus the implementation of binary search has been executed successfully.

Ex.No:3

Date:

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.

AIM:

To write a program for a text txt[0…n-1] and a pattern pat[0…m-1], using a function
search(char pat[], char txt[]) that prints all occurences of pat[] in txt[].

ALGORITHM:

Step 1: Start.

Step 2: Get the text string and pattern string.

Step 3: Perform search operations.

Step 4: Print the pattern found.

Step 5: Stop.

PROGRAM:

def search(pat,txt):

M=len(pat)

N=len(txt)

for I in range(N-M+1):

j=0

while(j<M)

if(txt[i+j]!=pat[j]):

break

j+=1
 if(j==M)

print(“Pattern found at index”, i)

if__name__=='__main__':

txt= “AABAACAADAABAAABAA”

pat= “AABA”

search(pat,txt)

OUTPUT:

Pattern found at index 0

Pattern found at index 9

Pattern found at index 12

RESULT:

The program to implement txt and pat using a function search(char pat[],char txt[]) is
executed successfully.
Ex.No:4 INSERTION SORT & HEAP SORT
Date:

AIM:
To write a program to sort a given set of elements using insertion sort and heap sort and to
determine time requited for sorting pot a graph of time taken vs n.

ALGORITHM:

Step 1: Start.
Step 2: Create the array for sorting.
Step 3: Perform insertion sort and heap sort.
Step 4: Display the time requited for sorting.
Step 5: Plot the graph for time taken vs n.
Step 6: End.

PROGRAM:

import time
import matplotlib.pyplot as plt
import random
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j=i-1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
def heap_sort(arr):
n = len(arr)
def heapify(arr, n, i):
largest = i
l = 2*i + 1
r = 2*i + 2
if l < n and arr[l] > arr[largest]:
largest = l
if r < n and arr[r] > arr[largest]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
for i in range(n//2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
def measure_sort_time(sort_func, arr):
start_time = time.time()
sort_func(arr)
end_time = time.time()
return end_time - start_time
def create_random_list(n):
return [random.randint(1, 1000) for _ in range(n)]
n_values = [10, 100, 1000, 10000]
insertion_times = []
heap_times = []
for n in n_values:
arr = create_random_list(n)
insertion_time = measure_sort_time(insertion_sort, arr)
 heap_time = measure_sort_time(heap_sort, arr)
insertion_times.append(insertion_time)
heap_times.append(heap_time)
print(f"n = {n}: Insertion sort took {insertion_time} seconds, Heap sort took {heap_time}
seconds")
plt.plot(n_values, insertion_times, label="Insertion sort")
plt.plot(n_values, heap_times, label="Heap sort")
plt.xlabel("n")
plt.ylabel("Time (s)")
plt.legend()
plt.show()

OUTPUT:
RESULT:
Thus, the program has been executed successfully.
Ex. No:5 GRAPH TRAVERSAL - BREADTH FIRST SEARCH

Date:

AIM:

To implement graph traversal using Breadth First Search.

ALGORITHM:

Step 1: Start.

Step 2: Put any one of the graph’s vertices at the back of the queue.

Step 3: Take the front item of the queue and add it to the visited list.

Step 4: Create a list of that vertex's adjacent nodes. Add those which are not within the visited
list tothe rear of the queue.

Step 5: Keep continuing steps two and three till the queue is empty.

Step 6: Stop.

PROGRAM:

graph = eval(input(“Enter your graph:”))

node=input(“Enter your starting node:”)

visited = []

queue = []

defbfs(visited, graph, node):

visited.append(node)

queue.append(node)

while queue:
 m = queue.pop(0)

print (m, end =” ”)

for neighbour in graph[m]:

if neighbour not in visited:

visited.append(neighbour)

queue.append(neighbour)

print(“BFS:”)

bfs(visited, graph, node)

OUTPUT:

RESULT:

Thus, graph traversal using Breadth First Search has been implemented successfully.
Ex. No:6 GRAPH TRAVERSAL - DEPTH FIRST SEARCH

Date:

AIM:

To implement graph traversal using Depth First Search.

ALGORITHM:

Step 1: Start.

Step 2: Put any one of the graph's vertex on top of the stack.

Step 3: Take the top item of the stack and add it to the visited list of the vertex.

Step 4: Create a list of that adjacent node of the vertex. Add the ones which aren't in the
visited list of vertexes to the top of the stack.

Step 5: Keep repeating steps 2 and 3 until the stack is empty.

Step 6: Stop.

PROGRAM:

graph = eval(input(“Enter your graph:”))

node = input(“Enter your starting node:”)

visited = set()

defdfs(visited, graph, node):

if node not in visited:

print (node, end=“ “)

visited.add(node)

for neighbour in graph[node]:

 dfs(visited, graph, neighbour)

print(“DFS:”)

dfs(visited, graph, node)

OUTPUT

RESULT:

Thus, graph traversal using Depth First Search has been implemented successfully.
Ex.No: IMPLEMENTATION OF DIJKSTRA’S ALGORITHM

Date:

AIM:

To implement a python program to find the shortest paths to other vertices using
dijkstra’s algorithm.

ALGORITHM:

Step 1: Start.

Step 2: Mark all vertex as unvisited.

Step 3: Mark source vertex as 0 and other vertex as infinity.

Step 4: Calculate the path length of all neighbor nodes from current adding the weight
of edges.

Step 5: Now new path is smaller than previous path then replace it.

Step 6: Mark the current vertex as visited after moving to its neighbor.

Step 7: Choose the path which is having smallest path length and go to step 3.

Step 8: Repeat the steps until all vertices are visited.

Step 9: Stop.

PROGRAM:

def dijkstra(graph, start):

dist = {vertex: float('inf') for vertex in graph}

dist[start] = 0

unvisited = set(graph.keys())

while unvisited:

c_v = min(unvisited, key=lambda vertex: dist[vertex])

unvisited.remove(c_v)

for neighbor, weight in graph[c_v].items():

new_distance = dist[c_v] + weight

if new_distance < dist[neighbor]:

dist[neighbor] = new_distance

return dist

graph = {

'A': {'B': 10, 'C': 3},

'B': {'C': 1, 'D': 2},

'C': {'B': 4, 'D': 8, 'E': 2},

'D': {'E': 7},

'E': {'D': 9}

start = 'A'

dist = dijkstra(graph, start)

print(dist)
OUTPUT:

RESULT:

Thus, the implementation of dijkstra’s algorithm has been executed successfully.

Ex.No:8 IMPLEMENTATION OF PRIMS ALGORITHM

Date:

AIM:

To implement the prim’s algorithm for undirected graph.

ALGORITHM:

Step 1: Start

Step 2: Initialize an empty MST.

Step 3: Choose any vertex v to start with.

Step 4: Create a priority queue Q and add all edges incident to v to Q, with their weights
as keys.

Step 5: Mark v as visited.

Step 6: While Q is not empty:

i. Remove the edge with minimum weight from Q.

ii. If both vertices of the edge are visited, ignore the edge and continue to the next one.

Iii. Otherwise, mark the unvisited vertex as visited, add the edge to the MST, and add all
edges incident to the new vertex to Q.

Step 7: Return the MST.

Step 8: Stop

PROGRAM:

INF = 9999999

N=5

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

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]):

if minimum > G[m][n]:

minimum = G[m][n]

a=m

b=n

print(str(a) + "-" + str(b) + ":" + str(G[a][b]))

selected_node[b] = True

no_edge += 1
OUTPUT:

RESULT:

Thus the program was implemented successfully.

Ex.No:9 IMPLEMENT FLOYD’S ALGORITHM FOR THE ALL-PAIRS

Date: SHORTEST-PATHS PROBLEM

AIM:

To implement Floyd’s algorithm for the All-Pairs-Shortest-Paths problem.

ALGORITHM:

Step 1:Start

Step 2: Consider the intermediate nodes.

Step 3: Traverse through each of the intermediates i.e from vertex to destination.

Step 4: Once all the nodes are traversed, compare and select the shortest path.

Step 5: End

PROGRAM:

def floyd(graph):

n = len(graph)

dist = [[float('inf') for _ in range(n)] for _ in range(n)]

for i in range(n):

for j in range(n):

if i == j:

dist[i][j] = 0

elif graph[i][j] != 0:

dist[i][j] = graph[i][j]

for k in range(n):

for i in range(n):
 for j in range(n):

intermediate_dist = dist[i][k] + dist[k][j]

if intermediate_dist<dist[i][j]:

dist[i][j] = intermediate_dist

return dist

graph = [

[0, 3, float('inf'), 5],

[2, 0, float('inf'), 4],

[float('inf'), 1, 0, float('inf')],

[float('inf'), float('inf'), 2, 0]

output=floyd(graph)

print(output)

OUTPUT:

RESULT:

The program to implement Floyd’s algorithm for the All-Pairs-Shortest-Paths problemhas

been executed successfully.
Ex.No:10 WARSHALL ALGORITHM

Date:

AIM:

To write a python program to implement Warshall Algorithm.

ALGORITHM:

Step 1: Start

Step 2: Define transitive_closure function with the steps involved in warshall.

Step 3: Declare the graph variable in matrix form

Step 4: Pass the variable as paramater to the defined function

Step 5: Print the output

Step 6: Stop

PROGRAM:

def t_closure(graph):

n=len(graph)

closure=[[0 for j in range(n)] for i in range(n)]

for i in range(n):

for j in range(n):

closure[i][j]=graph[i][j]

for k in range(n):

for i in range(n):

for j in range(n):

closure[i][j]=closure[i][j]or(closure[i][k]and closure[k[j])

return closure

graph=([0,1,0,0],[0,0,1,0],[0,0,0,1],[1,0,0,0])
 closure=t_closure(graph)

print(closure)

OUTPUT:

RESULT:

Thus the program to implement warshall algorithm was implemented succussfully.

Ex.No:11 DEVELOP A PROGRAM TO FIND MAXIMUM AND MINIMUM
Date: NUMBER IN A LIST USING DIVIDE AND CONQUER TECHNIQUE

AIM:
To write a program to find maximum and minimum numbers in a given list.

ALGORITHM:

Step 1: Start

Step 2: Create a function to find max and min

Step 3: Satisfy both the primary cases,

1. List contains only one element

2. List contains only two elements

Step 4: If the list has more than 2 elements then execute the function recursively

Step 5: Return min and max

Step 6: Create a list and pass it to the created function

Step 7: Stop

PROGRAM:

import sys

# Divide and conquer solution to find the minimum and maximum number in a list

def findMinAndMax(nums, left, right, min=sys.maxsize, max=-sys.maxsize):

# if the list contains only one element

if left == right: # common comparison

if min >nums[right]: # comparison 1

min = nums[right]

if max <nums[left]: # comparison 2

 max = nums[left]

return min, max

# If the list contains only two elements

if right - left == 1:

if nums[left] <nums[right]:

if min >nums[left]:

min = nums[left]

if max <nums[right]:

max = nums[right]

else:

if min >nums[right]:

min = nums[right]

if max <nums[left]:

max = nums[left]

return min, max

# find the middle element

mid = (left + right) // 2

# recur for the left sublist

min, max = findMinAndMax(nums, left, mid, min, max)

# recur for the right sublist

min, max = findMinAndMax(nums, mid + 1, right, min, max)

return min, max

if __name__ == '__main__':

nums = [7, 2, 9, 3, 1, 6, 7, 8, 4]
 # initialize the minimum element by INFINITY and the

# maximum element by -INFINITY

(min, max) = findMinAndMax(nums, 0, len(nums) - 1)

print("The minimum element in the list is", min)

print("The maximum element in the list is", max)

OUTPUT:

RESULT:

Thus, the program to implement divide and conquer technique has been executed
successfully.
Ex.No:12

Date:

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.

AIM:

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:

Step 1: Start

Step 2: import required packages

Step 3: Create functions for Quick sort and merge sort algorithms

Step 4: Test the algorithms for different values of n

Step 5: Plot the graph for time taken versus n

Step 6: Stop

PROGRAM:

import time

import matplotlib.pyplot as plt

def merge_sort(arr):

if len(arr) <= 1:

return arr

mid = len(arr) // 2

left_arr = arr[:mid]

right_arr = arr[mid:]

left_arr = merge_sort(left_arr)
 right_arr = merge_sort(right_arr)

return merge(left_arr, right_arr)

def merge(left_arr, right_arr):

result = []

i=j=0

while i < len(left_arr) and j < len(right_arr):

if left_arr[i] < right_arr[j]:

result.append(left_arr[i])

i += 1

else:

result.append(right_arr[j])

j += 1

result += left_arr[i:]

result += right_arr[j:]

return result

def quick_sort(arr):

if len(arr) <= 1:

return arr

pivot = arr[len(arr)//2]

left_arr = []

right_arr = []

equal_arr = []

for element in arr:

if element < pivot:

left_arr.append(element)
 elif element > pivot:

right_arr.append(element)

else:

equal_arr.append(element)

return quick_sort(left_arr) + equal_arr + quick_sort(right_arr)

n_values = [100, 1000, 5000, 10000, 50000]

merge_sort_times = []

quick_sort_times = []

for n in n_values:

arr = [i for i in range(n, 0, -1)]

start_time = time.time()

sorted_arr = merge_sort(arr)

end_time = time.time()

merge_sort_times.append(end_time - start_time)

start_time = time.time()

sorted_arr = quick_sort(arr)

end_time = time.time()

quick_sort_times.append(end_time - start_time)

plt.plot(n_values, merge_sort_times, label='Merge Sort')

plt.plot(n_values, quick_sort_times, label='Quick Sort')

plt.xlabel('Number of Elements (n)')

plt.ylabel('Time Taken (Seconds)')

plt.legend()

plt.show()
OUTPUT:

RESULT:

Thus the python program for quick sort and merge sort has been executed successfully
Ex.No:13 N QUEEN PROBLEM USING BACKTRACKING
Date:

AIM:
To write a program to implement N Queen problem using Backtracking.

ALGORITHM:

Step 1: Start.
Step 2: Initialize an empty chessboard of size NxN.
Step 3: Start with the leftmost column and place a queen in the first row of that
column.

Step 4: Move to the next column and place a queen in the first row of that column.

Step 5: 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 6: If all N queens have been placed, print the solution.

Step 7: 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 8: Remove the queen from the previous column and move it down one row.
Step 9: Repeat steps 4-7 until all possible configurations have been tried.

Step 10: stop.

PROGRAM:

import numpy as cp
from itertools import permutations
def queen(a):
for cl in permutations(range(a)):
mtrx = np.zeros(a*a).reshape(a,a)
check =0
 for i in range(a):
if check != i*(i-1)/2:
break
for j in range(1,a):
if i >= j:
if cl[i] == cl[i-j]+j or cl[i] == cl[i-j]-j:
check = 0
break
else:
check += 1
else:
continue
if check == a*(a-1)/2:
for r in range(a):
mtrx[r][cl[r]] = 1
yield mtrx
else:
pass
num = int(input())
print(f"Input: {num}\a") print("solution:\a")
for m in queens(num):
print(m,"\a")
OUTPUT:

RESULT:
Thus, the implementation of N Queen problem using Backtracking has been executed
successfully.
Ex.No:14
Date:

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

AIM:

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

Step 2 : import required modules in the program

Step 3: Find the optimal solution for Travelling Salesperson problem

Step 4: Solve the same problem using approximation algorithm

Step 5: Determine the error in the approximation

Step 6 : Stop

PROGRAM:

import sys
def tsp_optimal_solution(distances):
n = len(distances)
visited = set()
optimal_cost = 0
optimal_path = [0]
visited.add(0)
while len(visited) < n:
min_distance = sys.maxsize
min_index = -1
for i in range(n):
if i not in visited and distances[optimal_path[-1]][i] < min_distance:
min_distance = distances[optimal_path[-1]][i]
min_index = i
 visited.add(min_index)
optimal_path.append(min_index)
optimal_cost += min_distance
optimal_path.append(0)
optimal_cost += distances[optimal_path[-2]][0]
return optimal_cost, optimal_path

def tsp_approx_solution(distances):
n = len(distances)
visited = set()
approx_cost = 0
approx_path = [0]
visited.add(0)
while len(visited) < n:
min_distance = sys.maxsize
min_index = -1
for i in range(n):
if i not in visited and distances[approx_path[-1]][i] < min_distance:
min_distance = distances[approx_path[-1]][i]
min_index = i
visited.add(min_index)
approx_path.append(min_index)
approx_cost += min_distance
approx_path.append(0)
approx_cost += distances[approx_path[-2]][0]
return approx_cost, approx_path

def calculate_error(approx_cost, optimal_cost):

return (approx_cost - optimal_cost) / optimal_cost

if __name__ == '__main__':
distances = [[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]]
optimal_cost, optimal_path = tsp_optimal_solution(distances)
print("Optimal Solution:")
print("The optimal path is:", optimal_path)
print("The optimal cost is:", optimal_cost)
approx_cost, approx_path = tsp_approx_solution(distances)
 print("\nApproximated Solution:")
print("The approximated path is:", approx_path)
print("The approximated cost is:", approx_cost)
error = calculate_error(approx_cost, optimal_cost)
print("\nError in approximation is:", error)

OUTPUT:

RESULT :

Thus the python program for travelling salesperson problem has been executed
successfully.
Ex.No:15 IMPLEMENT RANDOMIZED ALGORITHMS FOR FINDING THE

Date : KTH SMALLEST NUMBER

AIM:

To Implement randomized algorithms for finding the kth smallest number.

ALGORITHM:

Step 1 : Start

Step 2 : Choose a random pivot element from the array.

Step 3: Partition the array into two sub-arrays: elements less than the pivot and elements
greater than the pivot.

Step 4: If the pivot element is the kth smallest element, return it.

If the pivot element is larger than the kth smallest element, recursively apply the
algorithm to the left sub-array.

If the pivot element is smaller than the kth smallest element, recursively apply the
algorithm to the right sub-array.

Step 5 : Stop

PROGRAM:

import random

def kth_smallest(arr, k):

pivot = random.choice(arr)

left = [x for x in arr if x < pivot]

right = [x for x in arr if x > pivot]

if k <= len(left):

return kth_smallest(left, k)

elif k > len(arr) - len(right):

return kth_smallest(right, k - (len(arr) - len(right)))

else:
 return pivot

# Example usage

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

k=3

result = kth_smallest(arr, k)

print(f"The {k}th smallest element in {arr} is {result}.")

OUTPUT:

RESULT :

Thus the python program for randomized algorithms for finding the kth smallest number
has been executed successfully.