DESIGN & ANALYSIS OF ALGORITHMS
PAPER CODE: CBCPC06
PRACTICAL FILE
SUBMITTED BY: SUBMITTED TO:
VINAY KUMAR (2022UCB6032) MRS. DIVYA TANEJA
BRANCH: CSDA
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
(BIG DATA ANALYTICS)
NETAJI SUBHAS UNIVERSITY OF TECHNOLOGY, EAST CAMPUS
GEETA COLONY, DELHI-110031
INDEX
S.NO PROGRAM DATE SIGN
1.
Write a program in python to implement 17/08/23
heap sort
2.
Write a program in python to implement 24/08/23
radix sort
3.
Write a program in python to implement 24/08/23
counting sort
4.
Write a program in python to implement 14/09/23
binary search tree
5.
Write a program in python to implement 14/09/23
AVL Tree
6.
Write a program in python to implement 05/10/23
BFS
7.
Write a program in python to implement 05/10/23
DFS
8.
Write a program in python to implement 12/10/23
prim’s algorithm
9.
Write a program in python to implement 12/10/23
Kruskal algorithm
10.
Write a program in python to implement 02/11/23
Dijkstra’s algorithm
Q1: Write a program in python to implement heap sort.
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[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
if __name__ == "__main__":
arr = [12, 11, 13, 5, 6, 7]
print("Original array:", arr)
heap_sort(arr)
print("Sorted array:", arr)
Q2: Write a program in python to implement radix sort.
def counting_sort(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for i in range(n):
index = (arr[i] // exp) % 10
count[index] += 1
for i in range(1, 10):
count[i] += count[i - 1]
i=n-1
while i >= 0:
index = (arr[i] // exp) % 10
output[count[index] - 1] = arr[i]
count[index] -= 1
i -= 1
for i in range(n):
arr[i] = output[i]
def radix_sort(arr):
max_element = max(arr)
exp = 1
while max_element // exp > 0:
counting_sort(arr, exp)
exp *= 10
if __name__ == "__main__":
arr = [170, 45, 75, 90, 802, 24, 2, 66]
print("Original array:", arr)
radix_sort(arr)
print("Sorted array:", arr)
Q3: Write a program in python to implement counting sort.
def counting_sort(arr):
max_element = max(arr)
min_element = min(arr)
range_of_elements = max_element - min_element + 1
count = [0] * range_of_elements
output = [0] * len(arr)
for i in range(len(arr)):
count[arr[i] - min_element] += 1
for i in range(1, len(count)):
count[i] += count[i - 1]
for i in range(len(arr) - 1, -1, -1):
output[count[arr[i] - min_element] - 1] = arr[i]
count[arr[i] - min_element] -= 1
for i in range(len(arr)):
arr[i] = output[i]
if __name__ == "__main__":
arr = [4, 2, 2, 8, 3, 3, 1]
print("Original array:", arr)
counting_sort(arr)
print("Sorted array:", arr)
Q4. Write a program in python to implement binary search tree.
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, key):
self.root = self._insert_recursive(self.root, key)
def _insert_recursive(self, root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = self._insert_recursive(root.left, key)
else:
root.right = self._insert_recursive(root.right, key)
return root
def search(self, key):
return self._search_recursive(self.root, key)
def _search_recursive(self, root, key):
if root is None or root.key == key:
return root
if key < root.key:
return self._search_recursive(root.left, key)
return self._search_recursive(root.right, key)
def in_order_traversal(self):
result = []
self._in_order_recursive(self.root, result)
return result
def _in_order_recursive(self, root, result):
if root:
self._in_order_recursive(root.left, result)
result.append(root.key)
self._in_order_recursive(root.right, result)
if __name__ == "__main__":
bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(70)
bst.insert(20)
bst.insert(40)
bst.insert(60)
bst.insert(80)
print("In-order traversal of the BST:")
print(bst.in_order_traversal())
search_key = 40
if bst.search(search_key):
print(f"{search_key} found in the BST")
else:
print(f"{search_key} not found in the BST")
Q5. Write a program in python to implement AVL tree.
class AVLNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
class AVLTree:
def __init__(self):
self.root = None
def _height(self, node):
if node is None:
return 0
return node.height
def _update_height(self, node):
if node is not None:
node.height = 1 + max(self._height(node.left), self._height(node.right))
def _balance_factor(self, node):
if node is None:
return 0
return self._height(node.left) - self._height(node.right)
def _rotate_right(self, y):
x = y.left
T2 = x.right
x.right = y
y.left = T2
self._update_height(y)
self._update_height(x)
return x
def _rotate_left(self, x):
y = x.right
T2 = y.left
y.left = x
x.right = T2
self._update_height(x)
self._update_height(y)
return y
def _balance(self, node):
if node is None:
return 0
return self._height(node.left) - self._height(node.right)
def insert(self, root, key):
if root is None:
return AVLNode(key)
if key < root.key:
root.left = self.insert(root.left, key)
else:
root.right = self.insert(root.right, key)
self._update_height(root)
balance = self._balance(root)
if balance > 1:
if key < root.left.key:
return self._rotate_right(root)
else:
root.left = self._rotate_left(root.left)
return self._rotate_right(root)
if balance < -1:
if key > root.right.key:
return self._rotate_left(root)
else:
root.right = self._rotate_right(root.right)
return self._rotate_left(root)
return root
def insert_key(self, key):
self.root = self.insert(self.root, key)
def delete(self, root, key):
if root is None:
return root
if key < root.key:
root.left = self.delete(root.left, key)
elif key > root.key:
root.right = self.delete(root.right, key)
else:
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp
temp = self._min_value_node(root.right)
root.key = temp.key
root.right = self.delete(root.right, temp.key)
if root is None:
return root
self._update_height(root)
balance = self._balance(root)
if balance > 1:
if self._balance(root.left) >= 0:
return self._rotate_right(root)
else:
root.left = self._rotate_left(root.left)
return self._rotate_right(root)
if balance < -1:
if self._balance(root.right) <= 0:
return self._rotate_left(root)
else:
root.right = self._rotate_right(root.right)
return self._rotate_left(root)
return root
def delete_key(self, key):
self.root = self.delete(self.root, key)
def _min_value_node(self, node):
current = node
while current.left is not None:
current = current.left
return current
def in_order_traversal(self, root):
result = []
if root:
result += self.in_order_traversal(root.left)
result.append(root.key)
result += self.in_order_traversal(root.right)
return result
if __name__ == "__main__":
avl_tree = AVLTree()
keys = [10, 20, 30, 40, 50, 25]
for key in keys:
avl_tree.insert_key(key)
print("In-order traversal of the AVL tree:")
print(avl_tree.in_order_traversal(avl_tree.root))
avl_tree.delete_key(30)
print("In-order traversal after deleting 30:")
print(avl_tree.in_order_traversal(avl_tree.root))
Q6. Write a program in python to implement BFS.
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def bfs(self, start):
visited = [False] * len(self.graph)
queue = []
visited[start] = True
queue.append(start)
while queue:
node = queue.pop(0)
print(node, end=" ")
for neighbor in self.graph[node]:
if not visited[neighbor]:
visited[neighbor] = True
queue.append(neighbor)
if __name__ == "__main__":
graph = Graph()
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 0)
graph.add_edge(2, 3)
graph.add_edge(3, 3)
start_node = 2
print(f"BFS traversal starting from node {start_node}:")
graph.bfs(start_node)
Q7. Write a program in python to implement DFS.
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def dfs(self, node, visited):
visited[node] = True
print(node, end=" ")
for neighbor in self.graph[node]:
if not visited[neighbor]:
self.dfs(neighbor, visited)
def depth_first_search(self, start):
visited = [False] * len(self.graph)
self.dfs(start, visited)
if __name__ == "__main__":
graph = Graph()
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 0)
graph.add_edge(2, 3)
graph.add_edge(3, 3)
start_node = 2
print(f"DFS traversal starting from node {start_node}:")
graph.depth_first_search(start_node)
Q8. Write a program in python to implement prim’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 add_edge(self, u, v, weight):
self.graph[u][v] = weight
self.graph[v][u] = weight
def min_key(self, key, mst_set):
min_val = float('inf')
min_index = -1
for v in range(self.V):
if key[v] < min_val and not mst_set[v]:
min_val = key[v]
min_index = v
return min_index
def prim_mst(self):
key = [float('inf')] * self.V
parent = [-1] * self.V
key[0] = 0
mst_set = [False] * self.V
for _ in range(self.V):
u = self.min_key(key, mst_set)
mst_set[u] = True
for v in range(self.V):
if self.graph[u][v] > 0 and not mst_set[v] and key[v] > self.graph[u][v]:
key[v] = self.graph[u][v]
parent[v] = u
print("Edge \tWeight")
for i in range(1, self.V):
print(f"{parent[i]} - {i}\t{self.graph[i][parent[i]]}")
if __name__ == "__main__":
g = Graph(5)
g.add_edge(0, 1, 2)
g.add_edge(0, 3, 6)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 8)
g.add_edge(1, 4, 5)
g.add_edge(2, 4, 7)
g.add_edge(3, 4, 9)
g.prim_mst()
Q9. Write a program in python to implement Kruskal algorithm.
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
def add_edge(self, u, v, w):
self.graph.append([u, v, w])
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
def union(self, parent, rank, x, y):
root_x = self.find(parent, x)
root_y = self.find(parent, y)
if rank[root_x] < rank[root_y]:
parent[root_x] = root_y
elif rank[root_x] > rank[root_y]:
parent[root_y] = root_x
else:
parent[root_y] = root_x
rank[root_x] += 1
def kruskal_mst(self):
result = []
i, e = 0, 0
self.graph = sorted(self.graph, key=lambda item: item[2])
parent = []
rank = []
for node in range(self.V):
parent.append(node)
rank.append(0)
while e < self.V - 1:
u, v, w = self.graph[i]
i += 1
x = self.find(parent, u)
y = self.find(parent, v)
if x != y:
e += 1
result.append([u, v, w])
self.union(parent, rank, x, y)
print("Edge \tWeight")
for u, v, w in result:
print(f"{u} - {v}\t{w}")
if __name__ == "__main__":
g = Graph(5)
g.add_edge(0, 1, 2)
g.add_edge(0, 3, 6)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 8)
g.add_edge(1, 4, 5)
g.add_edge(2, 4, 7)
g.add_edge(3, 4, 9)
g.kruskal_mst()
Q10. Write a program in python to implement 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 add_edge(self, u, v, w):
self.graph[u][v] = w
self.graph[v][u] = w
def min_distance(self, dist, spt_set):
min_val = float('inf')
min_index = -1
for v in range(self.V):
if dist[v] < min_val and not spt_set[v]:
min_val = dist[v]
min_index = v
return min_index
def dijkstra(self, src):
dist = [float('inf')] * self.V
dist[src] = 0
spt_set = [False] * self.V
for _ in range(self.V):
u = self.min_distance(dist, spt_set)
spt_set[u] = True
for v in range(self.V):
if not spt_set[v] and self.graph[u][v] > 0 and dist[u] + self.graph[u][v] < dist[v]:
dist[v] = dist[u] + self.graph[u][v]
self.print_solution(dist)
def print_solution(self, dist):
print("Vertex \tDistance from Source")
for node in range(self.V):
print(f"{node}\t{dist[node]}")
if __name__ == "__main__":
g = Graph(9)
g.add_edge(0, 1, 4)
g.add_edge(0, 7, 8)
g.add_edge(1, 2, 8)
g.add_edge(1, 7, 11)
g.add_edge(2, 3, 7)
g.add_edge(2, 8, 2)
g.add_edge(2, 5, 4)
g.add_edge(3, 4, 9)
g.add_edge(3, 5, 14)
g.add_edge(4, 5, 10)
g.add_edge(5, 6, 2)
g.add_edge(6, 7, 1)
g.add_edge(6, 8, 6)
g.add_edge(7, 8, 7)
start_node = 0
print(f"Dijkstra's algorithm starting from node {start_node}:")
g.dijkstra(start_node)
