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
[Link] 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):
[Link] = key
[Link] = None
[Link] = None
class BinarySearchTree:
def __init__(self):
[Link] = None
def insert(self, key):
[Link] = self._insert_recursive([Link], key)
def _insert_recursive(self, root, key):
if root is None:
return Node(key)
if key < [Link]:
[Link] = self._insert_recursive([Link], key)
else:
[Link] = self._insert_recursive([Link], key)
return root
def search(self, key):
return self._search_recursive([Link], key)
def _search_recursive(self, root, key):
if root is None or [Link] == key:
return root
if key < [Link]:
return self._search_recursive([Link], key)
return self._search_recursive([Link], key)
def in_order_traversal(self):
result = []
self._in_order_recursive([Link], result)
return result
def _in_order_recursive(self, root, result):
if root:
self._in_order_recursive([Link], result)
[Link]([Link])
self._in_order_recursive([Link], result)
if __name__ == "__main__":
bst = BinarySearchTree()
[Link](50)
[Link](30)
[Link](70)
[Link](20)
[Link](40)
[Link](60)
[Link](80)
print("In-order traversal of the BST:")
print(bst.in_order_traversal())
search_key = 40
if [Link](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):
[Link] = key
[Link] = None
[Link] = None
[Link] = 1
class AVLTree:
def __init__(self):
[Link] = None
def _height(self, node):
if node is None:
return 0
return [Link]
def _update_height(self, node):
if node is not None:
[Link] = 1 + max(self._height([Link]), self._height([Link]))
def _balance_factor(self, node):
if node is None:
return 0
return self._height([Link]) - self._height([Link])
def _rotate_right(self, y):
x = [Link]
T2 = [Link]
[Link] = y
[Link] = T2
self._update_height(y)
self._update_height(x)
return x
def _rotate_left(self, x):
y = [Link]
T2 = [Link]
[Link] = x
[Link] = T2
self._update_height(x)
self._update_height(y)
return y
def _balance(self, node):
if node is None:
return 0
return self._height([Link]) - self._height([Link])
def insert(self, root, key):
if root is None:
return AVLNode(key)
if key < [Link]:
[Link] = [Link]([Link], key)
else:
[Link] = [Link]([Link], key)
self._update_height(root)
balance = self._balance(root)
if balance > 1:
if key < [Link]:
return self._rotate_right(root)
else:
[Link] = self._rotate_left([Link])
return self._rotate_right(root)
if balance < -1:
if key > [Link]:
return self._rotate_left(root)
else:
[Link] = self._rotate_right([Link])
return self._rotate_left(root)
return root
def insert_key(self, key):
[Link] = [Link]([Link], key)
def delete(self, root, key):
if root is None:
return root
if key < [Link]:
[Link] = [Link]([Link], key)
elif key > [Link]:
[Link] = [Link]([Link], key)
else:
if [Link] is None:
temp = [Link]
root = None
return temp
elif [Link] is None:
temp = [Link]
root = None
return temp
temp = self._min_value_node([Link])
[Link] = [Link]
[Link] = [Link]([Link], [Link])
if root is None:
return root
self._update_height(root)
balance = self._balance(root)
if balance > 1:
if self._balance([Link]) >= 0:
return self._rotate_right(root)
else:
[Link] = self._rotate_left([Link])
return self._rotate_right(root)
if balance < -1:
if self._balance([Link]) <= 0:
return self._rotate_left(root)
else:
[Link] = self._rotate_right([Link])
return self._rotate_left(root)
return root
def delete_key(self, key):
[Link] = [Link]([Link], key)
def _min_value_node(self, node):
current = node
while [Link] is not None:
current = [Link]
return current
def in_order_traversal(self, root):
result = []
if root:
result += self.in_order_traversal([Link])
[Link]([Link])
result += self.in_order_traversal([Link])
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):
[Link] = defaultdict(list)
def add_edge(self, u, v):
[Link][u].append(v)
def bfs(self, start):
visited = [False] * len([Link])
queue = []
visited[start] = True
[Link](start)
while queue:
node = [Link](0)
print(node, end=" ")
for neighbor in [Link][node]:
if not visited[neighbor]:
visited[neighbor] = True
[Link](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}:")
[Link](start_node)
Q7. Write a program in python to implement DFS.
from collections import defaultdict
class Graph:
def __init__(self):
[Link] = defaultdict(list)
def add_edge(self, u, v):
[Link][u].append(v)
def dfs(self, node, visited):
visited[node] = True
print(node, end=" ")
for neighbor in [Link][node]:
if not visited[neighbor]:
[Link](neighbor, visited)
def depth_first_search(self, start):
visited = [False] * len([Link])
[Link](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
[Link] = [[0 for _ in range(vertices)] for _ in range(vertices)]
def add_edge(self, u, v, weight):
[Link][u][v] = weight
[Link][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 [Link][u][v] > 0 and not mst_set[v] and key[v] > [Link][u][v]:
key[v] = [Link][u][v]
parent[v] = u
print("Edge \tWeight")
for i in range(1, self.V):
print(f"{parent[i]} - {i}\t{[Link][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
[Link] = []
def add_edge(self, u, v, w):
[Link]([u, v, w])
def find(self, parent, i):
if parent[i] == i:
return i
return [Link](parent, parent[i])
def union(self, parent, rank, x, y):
root_x = [Link](parent, x)
root_y = [Link](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
[Link] = sorted([Link], key=lambda item: item[2])
parent = []
rank = []
for node in range(self.V):
[Link](node)
[Link](0)
while e < self.V - 1:
u, v, w = [Link][i]
i += 1
x = [Link](parent, u)
y = [Link](parent, v)
if x != y:
e += 1
[Link]([u, v, w])
[Link](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
[Link] = [[0 for _ in range(vertices)] for _ in range(vertices)]
def add_edge(self, u, v, w):
[Link][u][v] = w
[Link][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 [Link][u][v] > 0 and dist[u] + [Link][u][v] < dist[v]:
dist[v] = dist[u] + [Link][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}:")
[Link](start_node)
