1.
Implement the binary search algorithm in C and analyse its time
complexity.
def binary_search(arr, key):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == key:
return mid
elif arr[mid] < key:
low = mid + 1
else:
high = mid - 1
return -1
# Example usage
arr = [1, 3, 5, 7, 9, 11, 13]
key = 7
result = binary_search(arr, key)
if result != -1:
print(f"Element found at index: {result}")
else:
print("Element not found")
Element 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, random
import matplotlib.pyplot as plt
def linear_search(arr, key):
for i in range(len(arr)):
if arr[i] == key:
return i
return -1
sizes = [1000, 2000, 4000, 8000, 16000]
times = []
for n in sizes:
arr = list(range(n))
key = random.choice(arr)
start = time.time()
linear_search(arr, key)
times.append(time.time() - start)
plt.plot(sizes, times, marker='o')
plt.title("Linear Search Time vs n")
plt.xlabel("n (List Size)")
plt.ylabel("Time (s)")
plt.grid(True)
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, 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
sizes = [1000, 2000, 4000, 8000, 12000]
times = []
for n in sizes:
arr = [random.randint(1, 100000) for _ in range(n)]
start = time.time()
insertion_sort(arr)
times.append(time.time() - start)
plt.plot(sizes, times, 'o-')
plt.title("Insertion Sort Time vs Number of Elements")
plt.xlabel("Number of Elements (n)")
plt.ylabel("Time (seconds)")
plt.grid(True)
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}")
# Example usage
txt = "ABABDABACDABABCABAB"
pat = "ABAB"
search(pat, txt)
Pattern found at index 0
Pattern found at index 10
Pattern found at index 15
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:
node = queue.popleft()
print(node, end=' ')
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# Example graph as adjacency list
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
bfs(graph, 'A')
A B C D E F
6. Write a C program to implement the depth first search algorithm
for a graph and analyse its time complexity.
def dfs(g, v, visited=set()):
print(v, end=' ')
visited.add(v)
for n in g[v]:
if n not in visited:
dfs(g, n, visited)
g = {0:[1,2], 1:[0,3,4], 2:[0], 3:[1], 4:[1]}
print("DFS from node 0:")
dfs(g, 0)
DFS from node 0:
0 1 3 4 2
7. Develop a program to find the shortest paths to other vertices using
Dijkstra’s algorithm.
import heapq
def dijkstra(g, start):
d = {v: float('inf') for v in g}; d[start] = 0
pq = [(0, start)]
while pq:
dist, node = heapq.heappop(pq)
for nei, wt in g[node]:
if d[node] + wt < d[nei]:
d[nei] = d[node] + wt
heapq.heappush(pq, (d[nei], nei))
return d
g = {'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("Shortest from A:", dijkstra(g, 'A'))
Shortest from A: {'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):
n = len(graph)
dist = [[graph[i][j] for j in range(n)] for i in range(n)]
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])
return dist
# Example graph with 4 nodes
INF = float('inf')
graph = [
[0, 5, INF, 10],
[INF, 0, 3, INF],
[INF, INF, 0, 1],
[INF, INF, INF, 0]
]
result = floyd_warshall(graph)
print("All-Pairs Shortest Paths:")
for row in result:
print(row)
All-Pairs Shortest Paths:
[0, 5, 8, 9]
[inf, 0, 3, 4]
[inf, inf, 0, 1]
[inf, inf, inf, 0]
9. Implement prims algorithm for finding the minimum spanning tree
of an undirected graph.
import heapq
def prim(g, start):
v, heap, cost = set(), [(0, start)], 0
while heap:
w, u = heapq.heappop(heap)
if u not in v:
v.add(u); cost += w
for n, wt in g[u]:
if n not in v:
heapq.heappush(heap, (wt, n))
return cost
g = {'A':[('B',2),('C',3)], 'B':[('A',2),('C',1),('D',1)], 'C':
[('A',3),('B',1),('D',4)], 'D':[('B',1),('C',4)]}
print("MST cost:", prim(g, 'A'))
MST cost: 4
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)
# Example list
numbers = [12, 5, 31, 7, 19, 45, 2, 11]
maximum = find_max(numbers, 0, len(numbers)-1)
print("Maximum number is:", maximum)
Maximum number is: 45
11. Implement the heap sort algorithm in C. Compare its performance
with other sorting algorithms for different input sizes.
def heapify(arr, n, i):
l, r = 2*i+1, 2*i+2
largest = max((i, l, r), key=lambda x: arr[x] if x < n else
float('-inf'))
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, 7]
heap_sort(arr)
print("Sorted:", arr)
Sorted: [5, 6, 7, 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[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)
# Example input
arr = [10, 7, 8, 9, 1, 5]
sorted_arr = quick_sort(arr)
print("Sorted array:", sorted_arr)
Sorted array: [1, 5, 7, 8, 9, 10]
13. Implement Traveling Salesperson problem and then solve the
same problem instance using any approximation algorithm and
determine the error in the approximation.
import itertools, math
def d(a, b): return math.dist(a, b)
def path_len(p): return sum(d(p[i], p[i+1]) for i in range(len(p)-1))
+ d(p[-1], p[0])
def tsp_brute(c): return min(path_len(p) for p in
itertools.permutations(c))
def tsp_nn(c):
u, p = c[1:], [c[0]]
while u:
n = min(u, key=lambda x: d(p[-1], x))
p.append(n); u.remove(n)
return path_len(p)
cities = [(0,0), (1,5), (5,2), (6,6)]
exact = tsp_brute(cities)
approx = tsp_nn(cities)
print(f"Exact: {exact:.2f}, Approx: {approx:.2f}, Error: {((approx-
exact)/exact)*100:.2f}%")
Exact: 19.71, Approx: 22.71, Error: 15.23%
14. Write a C program to Implement N Queens problem using
Backtracking.
def solve(n, row=0, board=[]):
if row == n:
print(board)
return
for col in range(n):
if all(col != c and abs(col - c) != row - r for r, c in
enumerate(board)):
solve(n, row+1, board + [col])
solve(4)
[1, 3, 0, 2]
[2, 0, 3, 1]
15. Implement randomized algorithms for finding the kth smallest
number.
import random
def quickselect(arr, k):
p = random.choice(arr)
lows = [x for x in arr if x < p]
highs = [x for x in arr if x > p]
if k <= len(lows):
return quickselect(lows, k)
elif k <= len(lows) + arr.count(p):
return p
else:
return quickselect(highs, k - len(lows) - arr.count(p))
print(quickselect([7,10,4,3,20,15], 3))
