1) Write a Program to find the sum and product of two matrices using the list data

structure

def calculate_sum_and_product(matrix_a, matrix_b):

if len(matrix_a) != len(matrix_b) or len(matrix_a[0]) != len(matrix_b[0]):
raise ValueError("Matrices must have the same dimensions")

num_rows, num_cols = len(matrix_a), len(matrix_a[0])

matrix_sum = [[0 for _ in range(num_cols)] for _ in range(num_rows)]

matrix_product = [[0 for _ in range(num_cols)] for _ in range(num_rows)]

for row in range(num_rows):

for col in range(num_cols):
matrix_sum[row][col] = matrix_a[row][col] + matrix_b[row][col]
matrix_product[row][col] = matrix_a[row][col] * matrix_b[row][col]

return matrix_sum, matrix_product

if __name__ == "__main__":
num_rows = int(input("Enter the number of rows for the matrices: "))
num_cols = int(input("Enter the number of columns for the matrices: "))

print("Enter elements for the first matrix:")

matrix_a = [[int(input(f"Enter element [{row}][{col}]: ")) for col in range(num_cols)] for row in
range(num_rows)]

print("Enter elements for the second matrix:")

matrix_b = [[int(input(f"Enter element [{row}][{col}]: ")) for col in range(num_cols)] for row in
range(num_rows)]

result_sum, result_product = calculate_sum_and_product(matrix_a, matrix_b)

print("\nSum of matrices:")
for row in result_sum:
print(row)

print("\nProduct of matrices:")
for row in result_product:
print(row)
input matrix 1 : [1, 2] input matrix 2: [4, 5]
[4, 5] [6, 7]

OUTPUT:
Sum of matrix:
[5, 7]
[10, 12]

Product of matrix:
[4, 10]
[24, 35]

1
1-Write a program to find the largest and smallest elements in an array using the array/list data
structure.
def find_largest_and_smallest(arr):
if len(arr) == 0:
return None, None

largest = smallest = arr[0]

for num in arr:

if num > largest:
largest = num
if num < smallest:
smallest = num

return largest, smallest

if __name__ == "__main__":
arr = list(map(int, input("Enter the elements of the array separated by spaces: ").split()))

largest, smallest = find_largest_and_smallest(arr)

print(f"Largest element: {largest}")

print(f"Smallest element: {smallest}")
INPUT -
Enter the elements of the array separated by spaces: 1 2 3 4 5 6 7
OUTPUT-
Largest element: 7
Smallest element: 1

2
2) Write a program to implement a doubly linked list with function for
insertion,deletion,travaersal using the linked list data structure.
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None

class DoublyLinkedList:
def __init__(self):
[Link] = None

def insert_at_beginning(self, data):

new_node = Node(data)
if [Link] is None:
[Link] = new_node
else:
new_node.next = [Link]
[Link] = new_node
[Link] = new_node

def insert_at_end(self, data):

new_node = Node(data)
if [Link] is None:
[Link] = new_node
else:
temp = [Link]
while [Link]:
temp = [Link]
[Link] = new_node
new_node.prev = temp

def insert_after(self, prev_node, data):

if prev_node is None:
print("The given previous node cannot be None")
return
new_node = Node(data)
new_node.next = prev_node.next
prev_node.next = new_node
new_node.prev = prev_node
if new_node.next:
new_node.[Link] = new_node

def delete(self, data):

temp = [Link]
if temp is None:
print("List is empty")
return

if [Link] == data:
[Link] = [Link]
if [Link]:
[Link] = None
temp = None
return

while temp:
if [Link] == data:
break
temp = [Link]

3
 if temp is None:
print("Node with data", data, "not found")
return

if [Link]:
[Link] = [Link]
if [Link]:
[Link] = [Link]
temp = None

def traverse_forward(self):
temp = [Link]
if not temp:
print("List is empty")
return
while temp:
print([Link], end=" <=> " if [Link] else "\n")
temp = [Link]

def traverse_backward(self):
temp = [Link]
if not temp:
print("List is empty")
return

while [Link]:
temp = [Link]

while temp:
print([Link], end=" <=> " if [Link] else "\n")
temp = [Link]

INPUT-
dll = DoublyLinkedList()
dll.insert_at_beginning(10)
dll.insert_at_end(20)
dll.insert_at_end(30)
dll.insert_after([Link], 15)

print("Traverse forward:")
dll.traverse_forward()

print("Traverse backward:")
dll.traverse_backward()

[Link](20)

print("\nAfter deleting 20:")

dll.traverse_forward()

OUTPUT - Traverse forward:

10 <=> 15 <=> 20 <=> 30
Traverse backward:
30 <=> 20 <=> 15 <=> 10

After deleting 20:

10 <=> 15 <=> 30

4
3) Write a program to implement linked list (Singly, doubly and circular) with functions
for adding ,deleting, and displaying elements using the linked list data structure
class Node:
def __init__(self, data, prev=None, next=None):
[Link] = data
[Link] = prev
[Link] = next
class LinkedList:
def __init__(self, list_type="singly"):
[Link] = None
self.list_type = list_type

def append(self, data):

new_node = Node(data)
if not [Link]:
[Link] = new_node
if self.list_type == "circular":
new_node.next = new_node
else:
temp = [Link]
if self.list_type == "singly":
while [Link]: temp = [Link]
[Link] = new_node
elif self.list_type == "doubly":
while [Link]: temp = [Link]
[Link] = new_node
new_node.prev = temp
elif self.list_type == "circular":
while [Link] != [Link]: temp = [Link]
[Link] = new_node
new_node.next = [Link]

def delete(self, key):

temp = [Link]
if temp and [Link] == key:
if self.list_type == "circular" and [Link] == [Link]:
[Link] = None
else:
if self.list_type != "circular": [Link] = [Link]
if self.list_type == "doubly" and [Link]: [Link] = [Link]
if self.list_type == "doubly" and [Link]: [Link] = [Link]
temp = None
return
prev = None
while temp and [Link] != key:
prev, temp = temp, [Link]
if temp:
if self.list_type == "doubly" and [Link]: [Link] = [Link]
if self.list_type == "doubly" and [Link]: [Link] = [Link]
if self.list_type != "circular": [Link] = [Link]
if self.list_type == "circular" and [Link] == [Link]:
[Link] = None
temp = None

def display(self):
if not [Link]:

5
 print("List is empty.")
return
temp = [Link]
while True:
print([Link], end=" -> " if [Link] != [Link] else "\n")
temp = [Link]
if self.list_type == "circular" and temp == [Link]:
break
elif self.list_type != "circular" and [Link] is None:
break
INPUT-
print("Singly Linked List:")
singly_ll = LinkedList("singly")
singly_ll.append(10)
singly_ll.append(20)
singly_ll.append(30)
singly_ll.display()
singly_ll.delete(20)
singly_ll.display()

print("\nDoubly Linked List:")

doubly_ll = LinkedList("doubly")
doubly_ll.append(10)
doubly_ll.append(20)
doubly_ll.append(30)
doubly_ll.display()
doubly_ll.delete(20)
doubly_ll.display()

print("\nCircular Linked List:")

circular_ll = LinkedList("circular")
circular_ll.append(10)
circular_ll.append(20)
circular_ll.append(30)
circular_ll.display()
circular_ll.delete(20)
circular_ll.display()
OUTPUT-
Singly Linked List:
10 -> 20 -> 30
10 -> 30
Doubly Linked List:
10 <-> 20 <-> 30
10 <-> 30
Circular Linked List:
10 -> 20 -> 30 -> 10
10 -> 30 -> 10

6
4) Stack implementation using array with PUSH,POP operations
class Stack:
def __init__(self, size):
[Link] = size
[Link] = [None] * size
[Link] = -1

def push(self, data):

if [Link] == [Link] - 1:
print("Stack Overflow")
else:
[Link] += 1
[Link][[Link]] = data
print(f"Pushed {data} into stack")

def pop(self):
if [Link] == -1:
print("Stack Underflow")
return None
else:
popped_item = [Link][[Link]]
[Link] -= 1
print(f"Popped {popped_item} from stack")
return popped_item

def peek(self):
if [Link] == -1:
print("Stack is empty")
return None
else:
return [Link][[Link]]

def display(self):
if [Link] == -1:
print("Stack is empty")
else:
print("Stack elements: ", end="")
for i in range([Link], -1, -1):
print([Link][i], end=" ")
print()

7
INPUT-
stack = Stack(5)

[Link](10)
[Link](20)
[Link](30)
[Link](40)
[Link](50)

[Link]()

[Link](60)

[Link]()
[Link]()

[Link]()
OUTPUT –
Pushed 10 into stack
Pushed 20 into stack
Pushed 30 into stack
Pushed 40 into stack
Pushed 50 into stack
Stack elements: 50 40 30 20 10
Stack Overflow
Popped 50 from stack
Popped 40 from stack
Stack elements: 30 20 10

8
5) Implement Stack using Linked list.
class Node:
def __init__(self, data):
[Link] = data
[Link] = None

class Stack:
def __init__(self):
[Link] = None

def push(self, data):

new_node = Node(data)
if not [Link]:
[Link] = new_node
else:
new_node.next = [Link]
[Link] = new_node
print(f"Pushed {data} onto stack")

def pop(self):
if not [Link]:
print("Stack Underflow")
return None
else:
popped_item = [Link]
[Link] = [Link]
print(f"Popped {popped_item} from stack")
return popped_item

def peek(self):
if not [Link]:
print("Stack is empty")
return None
else:
return [Link]

def display(self):
if not [Link]:
print("Stack is empty")
return
temp = [Link]
print("Stack elements:", end=" ")
while temp:
print([Link], end=" ")
temp = [Link]
print()

9
INPUT-
stack = Stack()

[Link](10)
[Link](20)
[Link](30)
[Link](40)

[Link]()

[Link]()
[Link]()

[Link]()
print(f"Top element is: {[Link]()}")

OUTPUT-
Pushed 10 onto stack
Pushed 20 onto stack
Pushed 30 onto stack
Pushed 40 onto stack
Stack elements: 40 30 20 10
Popped 40 from stack
Popped 30 from stack
Stack elements: 20 10
Top element is: 20

10
6) Reverse a String using Stack.
def reverse_string_using_stack(s):
stack = []
for char in s:
[Link](char)
reversed_string = ""
while stack:
reversed_string += [Link]()
return reversed_string

input_string = "NAMSTE"
reversed_string = reverse_string_using_stack(input_string)
print("Reversed String:", reversed_string)

OUTPUT-
Reversed String: ETSMAN

11
7) Demostrate Queue Using Array
class Queue:
def __init__(self, capacity):
[Link] = capacity
[Link] = [None] * capacity
[Link] = 0
[Link] = -1
[Link] = 0

def is_empty(self):
return [Link] == 0

def is_full(self):
return [Link] == [Link]

def enqueue(self, item):

if self.is_full():
print("Queue is full!")
return
[Link] = ([Link] + 1) % [Link]
[Link][[Link]] = item
[Link] += 1
print(f"Enqueued: {item}")

def dequeue(self):
if self.is_empty():
print("Queue is empty!")
return None
item = [Link][[Link]]
[Link] = ([Link] + 1) % [Link]
[Link] -= 1
print(f"Dequeued: {item}")
return item

def display(self):
if self.is_empty():
print("Queue is empty!")
return
print("Queue elements:", end=" ")
for i in range([Link]):
index = ([Link] + i) % [Link]
print([Link][index], end=" ")
print()

if __name__ == "__main__":
queue = Queue(5)
while True:
print("\nMenu:")
print("1. Enqueue")
print("2. Dequeue")
print("3. Display")
print("4. Exit")

12
 choice = int(input("Enter your choice: "))

if choice == 1:
value = int(input("Enter value to enqueue: "))
[Link](value)
elif choice == 2:
[Link]()
elif choice == 3:
[Link]()
elif choice == 4:
print("Exiting...")
break
else:
print("Invalid choice! Try again.")

OUTPUT-
Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter your choice: 1
Enter value to enqueue: 5
Enqueued: 5

Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter your choice: 2
Dequeued: 5

Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter your choice: 3
Queue is empty!

Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter your choice: 4
Exiting...

13
8) Write a program to implement infix expression to postfix expression
class InfixToPostfix:
def __init__(self):
[Link] = []
[Link] = []
[Link] = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}

def is_operator(self, char):

return char in [Link]

def is_operand(self, char):

return [Link]()

def precedence_of(self, operator):

return [Link](operator, 0)

def infix_to_postfix(self, expression):

for char in expression:
if self.is_operand(char):
[Link](char)
elif char == '(':
[Link](char)
elif char == ')':
while [Link] and [Link][-1] != '(':
[Link]([Link]())
[Link]()
else:
while ([Link] and self.precedence_of([Link][-1]) >= self.precedence_of(char)):
[Link]([Link]())
[Link](char)

while [Link]:
[Link]([Link]())

return ''.join([Link])

if __name__ == "__main__":
converter = InfixToPostfix()
expression = input("Enter an infix expression: ")
postfix_expression = converter.infix_to_postfix(expression)
print("Postfix expression:", postfix_expression)

OUTPUT-
Enter an infix expression: A+B*(C^D-E)
Postfix expression: ABCD^E-*+

14
9) Program to implement postfix expression to infix expression
def is_operator(c):
return c in ['+', '-', '*', '/']

def postfix_to_infix(postfix):
stack = []

for char in postfix:

if not is_operator(char):
[Link](char)
else:
operand2 = [Link]()
operand1 = [Link]()
infix_expr = f"({operand1} {char} {operand2})"
[Link](infix_expr)

return stack[0]

INPUT-
postfix = "ab+c*d+"
infix = postfix_to_infix(postfix)
print("Infix Expression:", infix)
OUTPUT –
Infix Expression: (((a + b) * c) + d)

15
10) Write a program, to implement binary search tree(BST)with operations for
insertion ,deletion, and in-order traversal using the tree data structure
class Node:
def __init__(self, key):
[Link] = None
[Link] = None
[Link] = key

class BST:
def __init__(self):
[Link] = None

def insert(self, root, key):

if root is None:
return Node(key)
else:
if key < [Link]:
[Link] = [Link]([Link], key)
else:
[Link] = [Link]([Link], key)
return root

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.find_min([Link])
[Link] = [Link]
[Link] = [Link]([Link], [Link])
return root

def find_min(self, root):

while [Link] is not None:
root = [Link]
return root

16
 def inorder_traversal(self, root):
if root:
self.inorder_traversal([Link])
print([Link], end=" ")
self.inorder_traversal([Link])

def insert_value(self, key):

if [Link] is None:
[Link] = Node(key)
else:
[Link] = [Link]([Link], key)

def delete_value(self, key):

[Link] = [Link]([Link], key)

def inorder(self):
self.inorder_traversal([Link])
print()

bst = BST()
bst.insert_value(50)
bst.insert_value(30)
bst.insert_value(20)
bst.insert_value(40)
bst.insert_value(70)
bst.insert_value(60)
bst.insert_value(80)

print("In-order traversal:")
[Link]()

bst.delete_value(20)
print("In-order traversal after deleting 20:")
[Link]()

bst.delete_value(30)
print("In-order traversal after deleting 30:")
[Link]()

bst.delete_value(50)
print("In-order traversal after deleting 50:")
[Link]()

17
OUTPUT-

In-order traversal:

20 30 40 50 60 70 80

In-order traversal after deleting 20:

30 40 50 60 70 80

In-order traversal after deleting 30:

40 50 60 70 80

In-order traversal after deleting 50:

40 60 70 80

18
11) Write a program to implement a Graph using a adjacency list and perform both depth
first search(DFS)and breadth first Search(BFS) using the graph data structure.
class Graph:
def __init__(self):
[Link] = {}

def add_edge(self, u, v):

if u not in [Link]:
[Link][u] = []
if v not in [Link]:
[Link][v] = []

[Link][u].append(v)
[Link][v].append(u)

def dfs(self, start):

visited = set()
self._dfs_helper(start, visited)

def _dfs_helper(self, node, visited):

[Link](node)
print(node, end=" ")
for neighbor in [Link][node]:
if neighbor not in visited:
self._dfs_helper(neighbor, visited)

def bfs(self, start):

visited = set()
queue = [start]
[Link](start)

while queue:
node = [Link](0)
print(node, end=" ")

for neighbor in [Link][node]:

if neighbor not in visited:
[Link](neighbor)
[Link](neighbor)

graph = Graph()
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 4)
graph.add_edge(2, 5)
graph.add_edge(3, 6)

print("DFS starting from vertex 1:")

[Link](1)

print("\nBFS starting from vertex 1:")

[Link](1)
OUTPUT-
DFS starting from vertex 1:
124536
BFS starting from vertex 1:
123456

19
12) Write a program for graph implementation and Graph Traversals.
class Graph:
def __init__(self):
[Link] = {}

def add_node(self, node):

if node not in [Link]:
[Link][node] = []

def add_edge(self, node1, node2):

if node1 not in [Link]:
self.add_node(node1)
if node2 not in [Link]:
self.add_node(node2)
[Link][node1].append(node2)
[Link][node2].append(node1)

def dfs(self, start, visited=None):

if visited is None:
visited = set()

[Link](start)
print(start, end=" ")

for neighbor in [Link][start]:

if neighbor not in visited:
[Link](neighbor, visited)

def bfs(self, start):

visited = set()
queue = [start]
[Link](start)

while queue:
node = [Link](0)
print(node, end=" ")

for neighbor in [Link][node]:

if neighbor not in visited:
[Link](neighbor)
[Link](neighbor)

if __name__ == "__main__":
g = Graph()

g.add_edge(1, 2)
g.add_edge(1, 3)

20
 g.add_edge(2, 4)
g.add_edge(2, 5)
g.add_edge(3, 6)

print("DFS Traversal starting from node 1:")

[Link](1)

print("\n\nBFS Traversal starting from node 1:")

[Link](1)

OUTPUT -
DFS Traversal starting from node 1:
124536

BFS Traversal starting from node 1:

123456

21
13) Write a program to implement Merge Sort.
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]

merge_sort(left_half)
merge_sort(right_half)

i=j=k=0

while i < len(left_half) and j < len(right_half):

if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1

while i < len(left_half):

arr[k] = left_half[i]
i += 1
k += 1

while j < len(right_half):

arr[k] = right_half[j]
j += 1
k += 1

if __name__ == "__main__":
arr = [38, 27, 43, 3, 9, 82, 10]
print("Original array:", arr)
merge_sort(arr)
print("Sorted array:", arr)

OUTPUT-
Original array: [38, 27, 43, 3, 9, 82, 10]
Sorted array: [3, 9, 10, 27, 38, 43, 82]

22
14) Write a program for implementation of 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)

OUTPUT-
Original array: [12, 11, 13, 5, 6, 7]
Sorted array: [5, 6, 7, 11, 12, 13]

23
15) Write a Program to implement a Hash table with collision handling using chaining,
demonstrating the hash table data structure
class HashTable:
def __init__(self, size):
[Link] = size
[Link] = [[] for _ in range(size)]

def hash_function(self, key):

return hash(key) % [Link]

def insert(self, key, value):

index = self.hash_function(key)
for pair in [Link][index]:
if pair[0] == key:
pair[1] = value
return
[Link][index].append([key, value])

def search(self, key):

index = self.hash_function(key)
for pair in [Link][index]:
if pair[0] == key:
return pair[1]
return None

def delete(self, key):

index = self.hash_function(key)
for i, pair in enumerate([Link][index]):
if pair[0] == key:
del [Link][index][i]
return True
return False

def display(self):
for i, bucket in enumerate([Link]):
if bucket:
print(f"Index {i}: {bucket}")

if __name__ == "__main__":
ht = HashTable(10)
[Link]("name", "RAKESH")
[Link]("age", 24)
[Link]("country", "INDIA")
[Link]("email", "rbthakare2000@[Link]")
[Link]("phone", "9665798795")

print("Hash Table after insertions:")

24
 [Link]()

print("\nSearching for 'age':", [Link]("age"))

print("Searching for 'address':", [Link]("address"))

print("\nDeleting 'phone':", [Link]("phone"))

print("\nHash Table after deletion:")

[Link]()

OUTPUT-
Hash Table after insertions:
Index 1: [['name', 'RAKESH']]
Index 2: [['country', 'INDIA'], ['phone', '9665798795']]
Index 6: [['email', 'rbthakare2000@[Link]']]
Index 8: [['age', 24]]

Searching for 'age': 24

Searching for 'address': None

Deleting 'phone': True

Hash Table after deletion:

Index 1: [['name', 'RAKESH']]
Index 2: [['country', 'INDIA']]
Index 6: [['email', 'rbthakare2000@[Link]']]
Index 8: [['age', 24]]

25