1. Implement the binary search algorithm in C and analyse its time complexity.
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
arr = [1, 3, 5, 7, 9]
target = 7
index = binary_search(arr, target)
print("Found at index:" if index != -1 else "Not found", index)
Output:
Found at index: 3
2. 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.
import time
import matplotlib.pyplot as plt
import random
def linear_search(arr, target):
for i, val in enumerate(arr):
if val == target:
return i
return -1
ns = [1000, 2000, 4000, 8000, 16000]
times = []
for n in ns:
arr = list(range(n))
target = n - 1 # Worst case
start = time.time()
linear_search(arr, target)
end = time.time()
times.append(end - start)
plt.plot(ns, times, marker='o')
plt.xlabel("Number of elements (n)")
plt.ylabel("Time taken (seconds)")
plt.title("Linear Search Time vs n")
plt.show()
3. Implement Insertion sort and 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.
import time
import random
import matplotlib.pyplot as plt
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 -= 1
arr[j + 1] = key
ns = [100, 200, 400, 800, 1600]
times = []
for n in ns:
arr = [random.randint(1, 10000) for _ in range(n)]
start = time.time()
insertion_sort(arr)
end = time.time()
times.append(end - start)
plt.plot(ns, times, marker='o')
plt.xlabel("Number of elements (n)")
plt.ylabel("Time taken (seconds)")
plt.title("Insertion Sort Time vs n")
plt.show()
4. 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.
def search(pat, txt):
m, n = len(pat), len(txt)
for i in range(n - m + 1):
if txt[i:i+m] == pat:
print(f"Pattern found at index {i}")
txt = "ABABDABACDABABCABAB"
pat = "ABABCABAB"
search(pat, txt)
Output:
Pattern found at index 10
5. Develop a program to implement graph traversal using Breadth First Search.
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
vertex = queue.popleft()
print(vertex, end=' ')
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
graph = {
0: [1, 2],
1: [0, 3],
2: [0, 4],
3: [1],
4: [2]
bfs(graph, 0)
Output:
01234
6. Write a C program to implement the depth first search algorithm for a graph and analyse
its time complexity.
def dfs(graph, vertex, visited=None):
if visited is None:
visited = set()
visited.add(vertex)
print(vertex, end=' ')
for neighbor in graph[vertex]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
graph = {
0: [1, 2],
1: [0, 3],
2: [0, 4],
3: [1],
4: [2]
dfs(graph, 0)
Output:
0 1324
7.Develop a program to find the shortest paths to other vertices using Dijkstra’s
algorithm.
import heapq
def dijkstra(graph, start):
distances = {v: float('inf') for v in graph}
distances[start] = 0
heap = [(0, start)]
while heap:
current_distance, current_vertex = heapq.heappop(heap)
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(heap, (distance, neighbor))
return distances
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
print(dijkstra(graph, 'A'))
output:
{'A': 0, 'B': 1, 'C': 3, 'D': 4}
8. Develop a program to implement Floyd’s algorithm for the All-Pairs- Shortest-
Paths problem
def floyd_warshall(graph):
dist = {u: dict(graph[u]) for u in graph}
for k in graph:
for i in graph:
for j in graph:
dist[i][j] = min(dist[i].get(j, float('inf')),
dist[i].get(k, float('inf')) + dist[k].get(j, float('inf')))
return dist
graph = {
'A': {'A':0, 'B':3, 'C':float('inf'), 'D':5},
'B': {'A':2, 'B':0, 'C':float('inf'), 'D':4},
'C': {'A':float('inf'), 'B':1, 'C':0, 'D':float('inf')},
'D': {'A':float('inf'), 'B':float('inf'), 'C':2, 'D':0}
distances = floyd_warshall(graph)
for u in distances:
print(f"{u}: {distances[u]}")
output:
A: {'A': 0, 'B': 3, 'C': 7, 'D': 5}
B: {'A': 2, 'B': 0, 'C': 6, 'D': 4}
C: {'A': 3, 'B': 1, 'C': 0, 'D': 7}
D: {'A': 5, 'B': 6, 'C': 2, 'D': 0}
9. Implement prims algorithm for finding the minimum spanning tree of an
undirected graph.
import heapq
def prim(graph, start):
mst = []
visited = set([start])
edges = [(cost, start, to) for to, cost in graph[start].items()]
heapq.heapify(edges)
while edges:
cost, frm, to = heapq.heappop(edges)
if to not in visited:
visited.add(to)
mst.append((frm, to, cost))
for to_next, cost_next in graph[to].items():
if to_next not in visited:
heapq.heappush(edges, (cost_next, to, to_next))
return mst
graph = {
0: {1: 2, 3: 6},
1: {0: 2, 2: 3, 3: 8, 4: 5},
2: {1: 3, 4: 7},
3: {0: 6, 1: 8},
4: {1: 5, 2: 7}
print(prim(graph, 0))
output:
[(0, 1, 2), (1, 2, 3), (1, 4, 5), (0, 3, 6)]
10. Develop a program to find out the maximum numbers in a given list of n
numbers using the divide and conquer technique.
def find_max(arr, low, high):
if low == high:
return arr[low]
mid = (low + high) // 2
left_max = find_max(arr, low, mid)
right_max = find_max(arr, mid+1, high)
return max(left_max, right_max)
arr = [3, 5, 2, 9, 7]
print(find_max(arr, 0, len(arr)-1))
output:
11. Implement the heap sort algorithm in C. Compare its performance with other
sorting algorithms for different input sizes.
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)
arr = [12, 11, 13, 5, 6]
heap_sort(arr)
print(arr)
output:
[5, 6, 11, 12, 13]
12. Implement quick sort algorithm and analyse its time complexity.
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr)//2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
arr = [3,6,8,10,1,2,1]
print(quick_sort(arr))
output:
[1, 1, 2, 3, 6, 8, 10]
13. Implement Traveling Salesperson problem and then solve the same problem
instance using any approximation algorithm and determine the error in the
approximation.
def tsp_nearest_neighbor(dist_matrix):
n = len(dist_matrix)
visited = [False]*n
path = [0]
visited[0] = True
for _ in range(n-1):
last = path[-1]
next_city = min([(dist_matrix[last][j], j) for j in range(n) if not visited[j]], key=lambda
x: x[0])[1]
path.append(next_city)
visited[next_city] = True
path.append(0) # return to start
return path
dist_matrix = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
path = tsp_nearest_neighbor(dist_matrix)
print("Approximate TSP path:", path)
output:
Approximate TSP path: [0, 1, 3, 2, 0]
14. Write a C program to Implement N Queens problem using Backtracking.
def is_safe(board, row, col, n):
for i in range(col):
if board[row][i]:
return False
for i,j in zip(range(row,-1,-1), range(col,-1,-1)):
if board[i][j]:
return False
for i,j in zip(range(row,n), range(col,-1,-1)):
if board[i][j]:
return False
return True
def solve_nqueens(board, col, n):
if col >= n:
for row in board:
print(" ".join("Q" if x else "." for x in row))
print()
return True
res = False
for i in range(n):
if is_safe(board, i, col, n):
board[i][col] = 1
res = solve_nqueens(board, col+1, n) or res
board[i][col] = 0
return res
n=4
board = [[0]*n for _ in range(n)]
solve_nqueens(board, 0, n)
output:
.Q..
...Q
Q...
..Q.
..Q.
Q...
...Q
.Q..
15. Implement randomized algorithms for finding the kth smallest number. generate
python program with an output in simple program
import random
def quickselect(arr, k):
if len(arr) == 1:
return arr[0]
pivot = random.choice(arr)
lows = [el for el in arr if el < pivot]
highs = [el for el in arr if el > pivot]
pivots = [el for el in arr if el == pivot]
if k <= len(lows):
return quickselect(lows, k)
elif k > len(lows) + len(pivots):
return quickselect(highs, k - len(lows) - len(pivots))
else:
return pivots[0]
arr = [7, 10, 4, 3, 20, 15]
k=3
print(f"{k}rd smallest element is {quickselect(arr, k)}")
output:
3rd smallest element is 7
