1.
linear search
import time
times = []
n = int(input("Enter number of test cases: "))
for i in range(n):
m = int(input("Enter number of elements: "))
a = []
print("Array elements for test case", i + 1, ":")
for j in range(m):
ab = int(input())
a.append(ab)
key = int(input("Enter a key to search: "))
f = 1
start = time.time()
for i in range(len(a)):
if a[i] == key:
print("Key is found at index:", i)
f = 0
break
if f == 1:
print("Key is not found")
end = time.time()
total = end - start
print("Total time taken:", total, "seconds")
times.append(total)
2.binary search
import time
times = []
n = int(input("Enter number of test cases: "))
for t in range(n):
m = int(input("Enter number of elements: "))
a = []
print("Array elements for test case", t + 1, ":")
for j in range(m):
ab = int(input())
a.append(ab)
a.sort()
print("Sorted array:", a)
key = int(input("Enter a key to search: "))
start = time.time() # start time
low = 0
high = len(a) - 1
found = False
while low <= high:
mid = (low + high) // 2
if a[mid] == key:
print("Key is found at index:", mid)
found = True
break
elif a[mid] < key:
low = mid + 1
else:
high = mid - 1
if not found:
print("Key is not found")
end = time.time()
total = end - start
print("Total time taken:", total, "seconds")
times.append(total)
3.bfs
graph = {
5: [3, 7],
3: [2, 4],
7: [8],
2: [],
4: [8],
8: []
}
visited = []
queue = []
def bfs(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("Breadth-First Search:")
bfs(visited, graph, 5)
4.dfs
graph = {
'5': ['3', '7'],
'3': ['2', '4'],
'7': ['8'],
'2': [],
'4': ['8'],
'8': []
}
visited = set()
def dfs(visited, graph, node):
if node not in visited:
print(node, end=" ")
visited.add(node)
for neighbour in graph[node]:
dfs(visited, graph, neighbour)
print("Depth-First Search:")
dfs(visited, graph, '5')
5.insertion sort
arr = [12, 45, 78, 96, 56, 77, 51, 8, 104, 96]
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j = j - 1
arr[j + 1] = key
insertion_sort(arr)
print("Sorted list:", arr)
5.heap sort
import time
import random
import matplotlib.pyplot as plt
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
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[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
sizes = [12, 7, 10, 25]
times = []
for n in sizes:
data = [random.randint(1, 100) for _ in range(n)]
start = time.time()
heap_sort(data)
end = time.time()
times.append(end - start)
print(f"Sorted list for n = {n}:", data)
plt.plot(sizes, times, marker='o', color='blue')
plt.xlabel("Number of elements (n)")
plt.ylabel("Time taken (seconds)")
plt.title("Heap Sort Time vs List Size")
plt.grid(True)
plt.show()
6.prims
import networkx as nx
G = nx.Graph()
nodes_list = [1, 2, 3, 4, 5, 6, 7]
G.add_nodes_from(nodes_list)
edges_list = [
(1, 2, 1), (1, 4, 4), (2, 3, 2), (2, 4, 6), (2, 5, 4),
(3, 5, 5), (3, 6, 6), (4, 5, 3), (4, 7, 4),
(5, 6, 8), (5, 7, 7), (6, 7, 3)
]
G.add_weighted_edges_from(edges_list)
mst = nx.minimum_spanning_tree(G, algorithm='prim')
print("Minimum Spanning Tree edges (sorted by weight):")
for edge in sorted(mst.edges(data=True), key=lambda x: x[2]['weight']):
print(edge)
7.warshalls
def warshalls_algorithm(graph):
n = len(graph)
transitive_closure = [row[:] for row in graph]
for k in range(n):
for i in range(n):
for j in range(n):
transitive_closure[i][j] = transitive_closure[i][j] or
(transitive_closure[i][k] and transitive_closure[k][j])
return transitive_closure
graph = [
[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 0, 0, 1],
[1, 0, 0, 0]
]
result = warshalls_algorithm(graph)
for row in result:
print(row)
9.nqueens
N = 8
def print_board(board):
for row in board:
print(" ".join(row))
print()
def is_safe(board, row, col):
for i in range(col):
if board[row][i] == 'Q':
return False
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 'Q':
return False
for i, j in zip(range(row, N), range(col, -1, -1)):
if board[i][j] == 'Q':
return False
return True
def solve(board, col):
if col >= N:
print_board(board)
return True
for i in range(N):
if is_safe(board, i, col):
board[i][col] = 'Q'
if solve(board, col + 1):
return True
board[i][col] = '0'
return False
board = [['0' for _ in range(N)] for _ in range(N)]
solve(board, 0)
10.kth randomized smallest num
import random
def quickselect(arr, k):
if len(arr) == 1:
return arr[0]
pivot = random.choice(arr)
low = [x for x in arr if x < pivot]
equal = [x for x in arr if x == pivot]
high = [x for x in arr if x > pivot]
if k <= len(low):
return quickselect(low, k)
elif k <= len(low) + len(equal):
return pivot
else:
return quickselect(high, k - len(low) - len(equal))
numbers = [12, 45, 78, 96, 56, 77, 51, 8, 104, 96]
k = 4
result = quickselect(numbers, k)
print(f"{k}th smallest number is:", result)
11.merge sort
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
merge_sort(left)
merge_sort(right)
i = j = k = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1
while i < len(left):
arr[k] = left[i]
i += 1
k += 1
while j < len(right):
arr[k] = right[j]
j += 1
k += 1
numbers = [12, 45, 78, 96, 56, 77, 51, 8, 104, 96]
merge_sort(numbers)
print("Sorted list is:", numbers)
12.quick sort
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
left = [x for x in arr[1:] if x < pivot]
right = [x for x in arr[1:] if x >= pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
numbers = [73, 42, 18, 85, 6, 97, 51, 24, 90, 13]
sorted_list = quick_sort(numbers)
print("Sorted list is:", sorted_list)
13.divide and conquer find max
def find_max(arr, low, high):
if low == high:
return arr[low]
mid = (low + high) // 2
max1 = find_max(arr, low, mid)
max2 = find_max(arr, mid + 1, high)
return max1 if max1 > max2 else max2
numbers = [12, 45, 78, 96, 56, 77, 51, 8, 104, 96]
result = find_max(numbers, 0, len(numbers) - 1)
print("Maximum number is:", result)
14.divide and conquer find min
def find_min(arr, low, high):
if low == high:
return arr[low]
mid = (low + high) // 2
min1 = find_min(arr, low, mid)
min2 = find_min(arr, mid + 1, high)
return min1 if min1 < min2 else min2
numbers = [12, 45, 78, 96, 56, 77, 51, 8, 104, 96]
result = find_min(numbers, 0, len(numbers) - 1)
print("Minimum number is:", result)
15. pair shortest path for the following graph
# Number of vertices
V = 4
# Representing the graph as an adjacency matrix
INF = float('inf')
graph = [
[0, 1, 8, INF], # from node 1 to others
[INF, 0, 1, INF], # from node 2 to others
[INF, INF, 0, 2], # from node 3 to others
[4, INF, 9, 0] # from node 4 to others
]
def floyd_warshall(graph):
# Number of vertices in graph
V = len(graph)
# Initialize distance matrix same as input graph matrix
dist = [row[:] for row in graph]
# Applying Floyd Warshall
for k in range(V):
for i in range(V):
for j in range(V):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
# Print the shortest distance matrix
print("All Pairs Shortest Path Matrix:")
for row in dist:
print(["INF" if x == INF else x for x in row])
floyd_warshall(graph)
