LAB-1

AIM: Implementation of Linear and Binary Search Algorithms.

 LINEAR SEARCH:
data = [34, 12, 45, 78, 56, 89, 7, 23, 98]
target = 56
position = -1
for i in range(len(data)):
if data[i] == target:
position = i
break
if position == -1:
print("Element not found")
else:
print("Element found at index", position)

OUTPUT:

 BINARY SEARCH:
def search_binary(arr, target, start, end):
mid = (start + end) // 2
if start > end:
return -1
if arr[mid] == target:
return mid
if target < arr[mid]:
return search_binary(arr, target, start, mid - 1)
return search_binary(arr, target, mid + 1, end)
numbers = [2, 10, 22, 35, 48, 59, 123, 210, 500]
key = 59

ADA 1 230057
result = search_binary(numbers, key, 0, len(numbers) - 1)
print(f"Element found at index: {result}" if result != -1 else "Element not found")

OUTPUT:

ADA 2 230057
 LAB – 2
AIM : Implementation of Insertion and Selection Sort.

 INSERTION SORT:
def sort_insertion(arr):
for i in range(1, len(arr)):
current = arr[i]
pos = i - 1
while pos >= 0 and current < arr[pos]:
arr[pos + 1] = arr[pos]
pos -= 1
arr[pos + 1] = current
data = [45, 23, 78, 12, 56, 89, 10]
sort_insertion(data)
print(f"Sorted array: {data}")

OUTPUT:

 SELECTION SORT:
def sort_selection(arr):
for i in range(len(arr)):
smallest = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[smallest]:
smallest = j
arr[i], arr[smallest] = arr[smallest], arr[i]
arr = [64, 34, 25, 12, 22, 11, 90]
sort_selection(arr)
print(f"Sorted array: {arr}")

ADA 3 230057
OUTPUT:

ADA 4 230057
 LAB – 3
AIM : Implementation of Bubble and Quick Sort.

 BUBBLE SORT:
def sort_bubble(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
return arr

arr = [45, 23, 78, 12, 56, 89, 10]

sorted_arr = sort_bubble(arr)
print(f"Sorted array: {sorted_arr}")

OUTPUT:

 QUICK SORT:

def quick_sort(arr, start, end):

if start < end:
pivot_index = partition(arr, start, end)
quick_sort(arr, start, pivot_index - 1)
quick_sort(arr, pivot_index + 1, end)

def partition(arr, start, end):

pivot = arr[start]
left = start + 1
right = end

ADA 5 230057
 while True:
# Move left index to the right as long as the element is less than or equal to the pivot
while left <= right and arr[left] <= pivot:
left += 1

# Move right index to the left as long as the element is greater than or equal to the pivot
while left <= right and arr[right] >= pivot:
right -= 1

if left <= right:

# Swap elements at left and right indices
arr[left], arr[right] = arr[right], arr[left]
else:
break

# Swap the pivot element with the element at the right index
arr[start], arr[right] = arr[right], arr[start]
return right

# Example usage:
arr = [64, 34, 25, 12, 22, 11, 90]
quick_sort(arr, 0, len(arr) - 1)
print(f"Sorted array: {arr}")

OUTPUT:

ADA 6 230057
 LAB – 4
AIM : Implementation of Merge Sort.
 MERGE SORT:

import numpy as np

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

arr = [38, 27, 43, 3, 9, 82, 10]

merge_sort(arr)
print(f"Sorted array: {arr}")

OUTPUT:

ADA 7 230057
 LAB – 5
AIM : Implementation of Graph Representation Adjacency List.
class Graph:
def __init__(self):
self.adj_list = {}

def add_edge(self, node1, node2):

if node1 not in self.adj_list:
self.adj_list[node1] = []
self.adj_list[node1].append(node2)
if node2 not in self.adj_list:
self.adj_list[node2] = []

def display_adj_list(self):
for node in self.adj_list:
print(f"{node} -> {', '.join(self.adj_list[node])}")

def get_adjacent_nodes(self, node):

if node in self.adj_list:
return self.adj_list[node]
return "Node not found"

if __name__ == "__main__":
g = Graph()
g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "D")
g.add_edge("C", "D")
g.add_edge("D", "E")
g.add_edge("E", "A")
print("Adjacency List:")
g.display_adj_list()

OUTPUT:

ADA 8 230057
 LAB – 6
AIM : Implementation of Graph Representation Adjacency Matrix.

import numpy as np
def adjacency_matrix(V, edges):
matrix = np.zeros((V, V), dtype=int)
for u, v in edges:
matrix[u][v] = 1
matrix[v][u] = 1
return matrix
V=6
edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 4), (3, 5), (4, 5)]
adj_matrix = adjacency_matrix(V, edges)
print("Adjacency Matrix:")
for row in adj_matrix:
print(row)

OUTPUT:

ADA 9 230057
 LAB – 7
AIM : Implemention of Graph Searching Breadth First Search (BFS).

from collections import deque

def bfs(adj, start):
q = deque()
visited = [False] * len(adj)
visited[start] = True
q.append(start)

while q:
curr = q.popleft()
print(curr, end=" ")

for neighbor in adj[curr]:

if not visited[neighbor]:
visited[neighbor] = True
q.append(neighbor)
def add_edge(adj, u, v):
adj[u].append(v)
adj[v].append(u)
if __name__ == "__main__":
V=5
adj = [[] for _ in range(V)]
add_edge(adj, 0, 1)
add_edge(adj, 0, 2)
add_edge(adj, 1, 3)
add_edge(adj, 1, 4)
print("BFS starting from node 0:")
bfs(adj, 0)

OUTPUT:

ADA 10 230057
 LAB – 8
AIM : Implemention of Graph Searching Depth First Search (DFS) .

def dfs(adj, start):

stack = []
visited = [False] * len(adj)
stack.append(start)
while stack:
curr = stack.pop()
if not visited[curr]:
print(curr, end=" ")
visited[curr] = True
for neighbor in reversed(adj[curr]):
if not visited[neighbor]:
stack.append(neighbor)
def add_edge(adj, u, v):
adj[u].append(v)
adj[v].append(u)
if __name__ == "__main__":
V=5
adj = [[] for _ in range(V)]
add_edge(adj, 0, 1)
add_edge(adj, 0, 2)
add_edge(adj, 1, 3)
add_edge(adj, 1, 4)
print("DFS starting from node 0:")
dfs(adj, 0)

OUTPUT:

ADA 11 230057
 LAB – 9
AIM : Implementation of Minimum Spanning Tree. Prim’s Algorithm .

V=6
G=[
[0, 7, 0, 0, 9, 10],
[7, 0, 8, 0, 0, 5],
[0, 8, 0, 6, 0, 7],
[0, 0, 6, 0, 12, 15],
[9, 0, 0, 12, 0, 4],
[10, 5, 7, 15, 4, 0]
]
selected = [False] * V
no_edge = 0
selected[0] = True
print("Edge : Weight\n")
while no_edge < V - 1:
minimum = float('inf')
x=0
y=0
for i in range(V):
if selected[i]:
for j in range(V):
if not selected[j] and G[i][j]:
if minimum > G[i][j]:
minimum = G[i][j]
x=i
y=j
print(f"{x} - {y} : {G[x][y]}")
selected[y] = True
no_edge += 1

ADA 12 230057
OUTPUT:

ADA 13 230057
 LAB – 10
AIM : Implementation of Minimum Spanning Tree Kruskal’s Algorithm .
V=5
edges = [
(0, 1, 9),
(0, 2, 75),
(1, 2, 95),
(1, 3, 19),
(1, 4, 42),
(2, 3, 51),
(2, 4, 66),
(3, 4, 31)
]
edges.sort(key=lambda x: x[2])
parent = list(range(V))
rank = [0] * V
def find(node):
if parent[node] != node:
parent[node] = find(parent[node])
return parent[node]
def union(u, v):
root_u = find(u)
root_v = find(v)
if root_u != root_v:
if rank[root_u] > rank[root_v]:
parent[root_v] = root_u
elif rank[root_u] < rank[root_v]:
parent[root_u] = root_v
else:
parent[root_v] = root_u
rank[root_u] += 1
print("Edge : Weight")

ADA 14 230057
mst_weight = 0
mst_edges = 0
for u, v, weight in edges:
if find(u) != find(v):
print(f"{u} - {v} : {weight}")
union(u, v)
mst_weight += weight
mst_edges += 1
if mst_edges == V - 1:
break
print(f"Total weight of MST: {mst_weight}")

OUTPUT:

ADA 15 230057
 LAB -11
AIM : Implementation of Binary Heap Graph.

def min_heap_build(array):
n = (len(array) // 2) - 1
for k in range(int(n), -1, -1):
min_heapify(array, k)
def min_heapify(array, k):
left = 2 * k + 1
right = 2 * k + 2
smallest = k
if left < len(array) and array[left] < array[k]:
smallest = left
if right < len(array) and array[right] < array[smallest]:
smallest = right
if smallest != k:
array[k], array[smallest] = array[smallest], array[k]
min_heapify(array, smallest)
array = [26, 18, 2, 57, 100, 5]
min_heap_build(array)
print(f"Min heap is {array}")

OUTPUT:

ADA 16 230057
 LAB – 12
AIM : Implementation of Single Source Shortest Paths Dijkstra’s Algorithm.
import sys
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]
def print_solution(self, dist):
print("Vertex \tDistance from Source")
for node in range(self.V):
print(node, "\t", dist[node])
def min_distance(self, dist, sptSet):
min_val = sys.maxsize
min_index = -1
for u in range(self.V):
if dist[u] < min_val and not sptSet[u]:
min_val = dist[u]
min_index = u
return min_index
def dijkstra(self, src):
dist = [sys.maxsize] * self.V
dist[src] = 0
sptSet = [False] * self.V
for _ in range(self.V):
x = self.min_distance(dist, sptSet)
sptSet[x] = True
for y in range(self.V):
if self.graph[x][y] > 0 and not sptSet[y] and dist[y] > dist[x] + self.graph[x][y]:
dist[y] = dist[x] + self.graph[x][y]

self.print_solution(dist)
if __name__ == "__main__":

ADA 17 230057
 g = Graph(6) # Specify the number of vertices
g.graph = [
[0, 2, 0, 1, 0, 0],
[2, 0, 3, 0, 0, 5],
[0, 3, 0, 6, 0, 2],
[1, 0, 6, 0, 4, 0],
[0, 0, 0, 4, 0, 3],
[0, 5, 2, 0, 3, 0]
]
g.dijkstra(0)

OUTPUT:

ADA 18 230057
 LAB – 13
AIM : Implementation of Single Source Shortest Paths Bellman-Ford’s Algorithm.

def bellman_ford(graph, source):

dist = {vertex: float('inf') for vertex in graph}
dist[source] = 0
for _ in range(len(graph) - 1):
for u in graph:
for v, weight in graph[u].items():
if dist[u] != float('inf') and dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
for u in graph:
for v, weight in graph[u].items():
if dist[u] != float('inf') and dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight # Potential negative cycle handling
return dist
graph = {
'A': {'B': 2, 'C': 1, 'D': 4},
'B': {'D': 2},
'C': {'B': 3},
'D': {'C': -6}
}
src = 'A'
short_path = bellman_ford(graph, src)
print(short_path)
OUTPUT:

ADA 19 230057
 LAB – 14
AIM : Implement a knapsack problem using a greedy algorithm (Fractional
Knapsack Problem) and a dynamic algorithm (0/1- Knapsack Problem) .

 GREEDY METHOD:

bjects = [1, 2, 3, 4, 5]
profit = [35, 25, 45, 20, 75]
weights = [50, 30, 60, 40, 70]
wk = 110
n=5
p_w_ratio = []
objects_in_max_profit = []
total_profit = 0
indices = []
for i in range(len(profit)):
p_w_ratio.append(profit[i] / weights[i])
sample_profit = p_w_ratio.copy()
while wk > 0:
maximum_ = max(sample_profit)
idx = p_w_ratio.index(maximum_)
while idx in indices:
idx = p_w_ratio.index(maximum_, idx + 1, n + 1)
if wk - weights[idx] < 0:
sample_weight = wk / weights[idx]
objects_in_max_profit.append(objects[idx])
indices.append(idx)
total_profit += profit[idx] * sample_weight
wk = 0
else:
objects_in_max_profit.append(objects[idx])
indices.append(idx)
wk -= weights[idx]
total_profit += profit[idx]
sample_profit.remove(maximum_)
print(f"Total profit is {total_profit}")
print(f"Objects are {objects_in_max_profit}")

OUTPUT:

 DYNAMIC METHOD:

ADA 20 230057
 import numpy as np
def create_matrix(w, n):
return np.zeros((n + 1, w + 1), int)
def knapsack(w, n):
matrix = create_matrix(w, n)
for i in range(1, n + 1):
for j in range(1, w + 1):
if j >= weights[i - 1]:
matrix[i][j] = max(matrix[i - 1][j], profit[i - 1] + matrix[i - 1][j - weights[i - 1]])
else:
matrix[i][j] = matrix[i - 1][j]
profit_objects = []
i=n
j=w
while i > 0 and j > 0:
if matrix[i][j] != matrix[i - 1][j]:
profit_objects.append(objects[i - 1])
j -= weights[i - 1]
i -= 1
return profit_objects, matrix[n][w], matrix
objects = [1, 2, 3, 4, 5]
profit = [35, 25, 45, 20, 75]
weights = [50, 30, 60, 40, 70]
Kw = 110
ans_objects, max_profit, matrix = knapsack(Kw, len(objects))
print("Objects included:", ans_objects)
print("Maximum Profit:", max_profit)

OUTPUT:

ADA 21 230057
 LAB – 15
AIM : Implement i th Order Statistic.
objects = [1, 2, 3, 4, 5]
profit = [35, 25, 45, 20, 75]
weights = [50, 30, 60, 40, 70]
wk = 110
n=5
p_w_ratio = []
objects_in_max_profit = []
total_profit = 0
indices = []
for i in range(len(profit)):
p_w_ratio.append(profit[i] / weights[i])
sample_profit = p_w_ratio.copy()
while wk > 0:
maximum_ = max(sample_profit)
idx = p_w_ratio.index(maximum_)
while idx in indices:
idx = p_w_ratio.index(maximum_, idx + 1, n + 1)
if wk - weights[idx] < 0:
sample_weight = wk / weights[idx]
objects_in_max_profit.append(objects[idx])
indices.append(idx)
total_profit += profit[idx] * sample_weight
wk = 0
else:
objects_in_max_profit.append(objects[idx])
indices.append(idx)
wk -= weights[idx]
total_profit += profit[idx]
sample_profit.remove(maximum_)
print(f"Total profit is {total_profit}")
print(f"Objects are {objects_in_max_profit}")

OUTPUT:

ADA 22 230057
 LAB – 16
AIM : Implementation of N-Queen’s Problem.

def median(arr):
n = len(arr)
sorted_arr = sorted(arr)
if n % 2 == 0:
return (sorted_arr[n // 2 - 1] + sorted_arr[n // 2]) / 2
else:
return sorted_arr[n // 2]
def partition(arr, pivot):
left = []
right = []
for num in arr:
if num < pivot:
left.append(num)
elif num > pivot:
right.append(num)
pivot_count = arr.count(pivot)
return left + [pivot] * pivot_count + right, len(left)
def quick_sort_with_median(arr):
if len(arr) <= 1:
return arr
pivot = median(arr)
partitioned, pivot_index = partition(arr, pivot)
left_sorted = quick_sort_with_median(partitioned[:pivot_index])
right_sorted = quick_sort_with_median(partitioned[pivot_index + arr.count(pivot):])
return left_sorted + [pivot] * arr.count(pivot) + right_sorted
if __name__ == "__main__":
array = [15, 35, 2, 8, 5, 4, 21, 14]
print("Original array:", array)
sorted_array = quick_sort_with_median(array)
print("Sorted array:", sorted_array)

OUTPUT:

ADA 23 230057