EX:1(a) DESIGN AND IMPLEMENT A SMART PARKING LOT VEHICLE

MANAGEMENT SYSTEM USING STACK, QUEUE, AND CIRCULAR

DATE QUEUE

AIM
To implement stack, queue, and circular queue operations using arrays in Python for
managing vehicle entry and exit in a multi-level smart parking lot.
ALGORITHM
STACK

STEP1: Initialize an empty array and a variable top = -1.

STEP2: Push: Increment top, insert element.
STEP3: Pop: Remove element at top, decrement top.
STEP4: Check for overflow and underflow.
QUEUE

STEP1: Initialize front = 0, rear = -1.

STEP2: Enqueue: Increment rear, insert element.
STEP3: Dequeue: Remove element at front, increment front.
STEP4: Check for overflow and underflow.
CIRCULAR QUEUE

STEP1: Initialize front = rear = -1.

STEP2: Enqueue: (rear + 1) % size
STEP3: Dequeue: (front + 1) % size
STEP4: Overflow if next rear equals front; underflow if front is -1.
Program

# Stack Implementation
class Stack:
def __init__(self, max_size):
[Link] = []
self.max_size = max_size
def push(self, item):
if len([Link]) == self.max_size:

1|Pa ge
 print("Stack Overflow")
else:
[Link](item)
def pop(self):
if not [Link]:
print("Stack Underflow")
else:
return [Link]()
# Queue Implementation
class Queue:
def __init__(self, max_size):
[Link] = []
self.max_size = max_size
def enqueue(self, item):
if len([Link]) == self.max_size:
print("Queue is Full")
else:
[Link](item)
def dequeue(self):
if not [Link]:
print("Queue is Empty")
else:
return [Link](0)
# Circular Queue Implementation
class CircularQueue:
def __init__(self, size):
[Link] = size
[Link] = [None] * size
[Link] = [Link] = -1
def enqueue(self, item):

2|Pa ge
 if ([Link] + 1) % [Link] == [Link]:
print("Circular Queue is Full")
elif [Link] == -1:
[Link] = [Link] = 0
[Link][[Link]] = item
else:
[Link] = ([Link] + 1) % [Link]
[Link][[Link]] = item

def dequeue(self):
if [Link] == -1:
print("Circular Queue is Empty")
elif [Link] == [Link]:
temp = [Link][[Link]]
[Link] = [Link] = -1
return temp
else:
temp = [Link][[Link]]
[Link] = ([Link] + 1) % [Link]
return temp
# -------------------------------
# Test Cases from Your Question
# -------------------------------
# Stack test
print("=== Stack Test ===")
stack = Stack(5)
[Link]('KA01AB1234')
[Link]('KA01CD5678')
print("Popped:", [Link]()) # Expected 'KA01CD5678'
# Queue test

3|Pa ge
print("\n=== Queue Test ===")
queue = Queue(5)
[Link]('KA41EF4321')
print("Dequeued:", [Link]()) # Expected 'KA41EF4321'

# Circular Queue test

print("\n=== Circular Queue Test ===")
cq = CircularQueue(5)
[Link]('KA17HG7070')
[Link]('KA15DE9981')
print("Dequeued:", [Link]()) # Expected 'KA17HG7070'

OUTPUT
=== Stack Test ===
Popped: KA01CD5678

=== Queue Test ===

Dequeued: KA41EF4321

=== Circular Queue Test ===

Dequeued: KA17HG7070

RESULT
Thus, the Python program using array-based stack, queue, and circular queue to simulate real-
time vehicle movement in a smart parking system has been implemented, executed, and
verified successfully.

4|Pa ge
 EX:1(b) IN A TOLL BOOTH, THERE ARE N VEHICLES (EACH VEHICLE HAS A
REGISTRATION NUMBER) ARE WAITING IN A QUEUE. THE
DATE REGISTRATION NUMBER OF THE VEHICLES ARE PASSED AS INPUT TO
THE PROGRAM. FOR EVERY MINUTE A VEHICLE PASSES THE TOLL
BOOTH. AN INTEGER X IS ALSO PASSED AS INPUT TO THE PROGRAM.
THE PROGRAM MUST PRINT THE REGISTRATION NUMBER OF THE
REMAINING VEHICLE(S) AFTER X MINUTES IN THE QUEUE.
IMPLEMENT THE INSERT AND POLL FUNCTIONS SO THAT THE
PROGRAM RUNS SUCCESSFULLY.

AIM
To implement a Python program that simulates vehicles waiting in a toll booth queue. The
program uses insert to add vehicles, poll to remove vehicles passing through the toll for X
minutes, and then prints the remaining vehicles in the queue.
ALGORITHM
STEP1: Start the program.
STEP2: Read the number of vehicles N.
STEP3: Read the registration numbers of the N vehicles.
STEP4: Read an integer X (number of minutes, each minute one vehicle passes).
STEP5: Initialize a queue (FIFO structure).
STEP6: Insert all vehicle registration numbers into the queue.
STEP7: For each of the X minutes:
• Remove (poll) one vehicle from the front of the queue.
STEP8: Display the registration numbers of the remaining vehicles in the queue.
STEP8: Stop.
PROGRAM
from collections import deque
class TollBoothQueue:
def __init__(self):
[Link] = deque()
# Insert vehicle into the queue
def insert(self, reg_no):
[Link](reg_no)
# Remove (poll) vehicle from the queue
def poll(self):

5|Pa ge
 if [Link]:
return [Link]()
else:
return None
# Display remaining vehicles
def display(self):
if [Link]:
print("Remaining Vehicles in Queue:", " ".join([Link]))
else:
print("No vehicles remaining in the queue.")
# Input Section
n = int(input("Enter number of vehicles: "))
vehicle_numbers = []
print("Enter the registration numbers:")
for _ in range(n):
vehicle_numbers.append(input().strip())
x = int(input("Enter number of minutes (vehicles to pass): "))
# Initialize queue
toll_queue = TollBoothQueue()
# Insert vehicles into the queue
for reg in vehicle_numbers:
toll_queue.insert(reg)
# Poll vehicles (pass through toll)
for _ in range(x):
toll_queue.poll()
# Display remaining vehicles
toll_queue.display()

6|Pa ge
OUTPUT
Enter number of vehicles: 3
Enter the registration numbers:
TN01AB1234
TN02CD5678
TN03EF1111
Enter number of minutes (vehicles to pass): 2
Remaining Vehicles in Queue: TN03EF1111

RESULT
The program successfully manages vehicles in a queue at a toll booth by inserting registration
numbers, removing vehicles as they pass the toll, and displaying the remaining vehicles after
X minutes.

7|Pa ge
 EX:2(a) DEVELOPMENT OF A SMARTPHONE CONTACT MANAGEMENT
SYSTEM USING SINGLY LINKED LIST IN PYTHON
DATE

AIM
To implement singly linked list operations in Python to manage contacts in a smartphone
application.
ALGORITHM
STEP1: Initialize the linked list with head = None.
STEP2: Insert: Add node at beginning, end, or after a specific node.
STEP3: Delete: Remove node with given value.
STEP4: Search: Traverse nodes to find value.
STEP5: Display: Traverse and print all elements.
PROGRAM
class Node:
def __init__(self, name, number):
[Link] = name
[Link] = number
[Link] = None
class ContactList:
def __init__(self):
[Link] = None
def insert_at_end(self, name, number):
new_node = Node(name, number)
if not [Link]:
[Link] = new_node
return
last = [Link]
while [Link]:
last = [Link]
[Link] = new_node
def delete_contact(self, name):

8|Pa ge
 temp = [Link]
prev = None
while temp and [Link] != name:
prev = temp
temp = [Link]
if not temp:
print("Contact not found")
return
if prev:
[Link] = [Link]
else:
[Link] = [Link]
def display(self):
temp = [Link]
while temp:
print(f"{[Link]}: {[Link]}")
temp = [Link]
# Create a contact list
contacts = ContactList()
# Insert contacts
contacts.insert_at_end("Alice", "12345")
contacts.insert_at_end("Bob", "67890")
contacts.insert_at_end("Charlie", "54321")
print("Contact List after insertion:")
[Link]()
# Delete a contact
print("\nDeleting Bob...")
contacts.delete_contact("Bob")
print("\nContact List after deletion:")
[Link]()

9|Pa ge
# Try deleting a non-existent contact
print("\nDeleting Eve (not in list)...")
contacts.delete_contact("Eve")
print("\nFinal Contact List:")
[Link]()

OUTPUT:
Contact List after insertion:
Alice: 12345
Bob: 67890
Charlie: 54321
Deleting Bob...
Contact List after deletion:
Alice: 12345
Charlie: 54321
Deleting Eve (not in list)...
Contact not found
Final Contact List:
Alice: 12345
Charlie: 54321

RESULT
Thus, the Python program using a singly linked list for efficient addition, deletion, and display
of phone contacts has been executed and verified successfully.

10 | P a g e
 EX:2(b) IN A BOOKSTORE, N BOOKS EACH BOOK HAS AN ID ARE ARRANGED
BY THE SHOPKEEPER. THE IDS OF THE BOOKS ARE PASSED AS INPUT
DATE TO THE PROGRAM. THE PROGRAM MUST PRINT THE BOOK IDS IN
REVERSE ORDER. IMPLEMENT THE PUSH AND POP FUNCTION SO
THAT THE PROGRAM RUNS SUCCESSFULLY.

AIM:
To write a Python program that reads N book IDs, stores them using a stack with push and pop
functions, and prints the book IDs in reverse order.

ALGORITHM:
STEP1: Start the program.
STEP2: Read the integer N (number of book IDs).
STEP3: Read N space-separated book IDs as input.
STEP4: Initialize an empty stack (using a list).
STEP5: Define the function push(stack, value) to add a value to the stack.
STEP6: Define the function pop(stack) to remove and return the top value from the stack.
STEP7: For each book ID, call push() to insert it into the stack.
STEP8: Repeatedly call pop() to retrieve and print the IDs in reverse order until the stack is
empty.
STEP9: End the program.

PROGRAM:
def reverse_book_ids():
stack = []
num_books = int(input("Enter the number of books: "))

print("Enter the book IDs:")

for _ in range(num_books):
book_id = input()
[Link](book_id)

print("\nBook IDs in reverse order:")

while stack:
print([Link]())
if __name__ == "__main__":
reverse_book_ids()

OUTPUT:
Enter the number of books: 4
Enter the book IDs:
45 66 701 890
Book IDs in reverse order: 890 701 66 45

RESULT
Thus, the Python program that reads N book IDs, stores them using a stack with push and pop
functions, and prints the book IDs in reverse order has been implemented, executed, and
verified successfully.

11 | P a g e
 EX:3 SIMULATION OF BROWSER HISTORY AND PRINT JOB MANAGEMENT
USING LINKED LIST-BASED STACK AND QUEUE IN PYTHON
DATE

AIM
To write a Python program that uses linked lists to implement Stack and Queue Abstract Data
Types ADTs, simulating browser history navigation using a stack and print job management
using a queue.
ALGORITHM
FOR STACK:
STEP1: Start the program.
STEP2: Define a StackNode class with attributes:
• url to store the visited URL.
• next pointer to link to the next node.
STEP3: Define a StackHistory class with:
• top pointer initialized as None.
• push(url) to create a new node and add it at the top.
• pop() to remove and return the most recently visited URL.
STEP4: Push visited URLs (simulate browsing).
STEP5: Pop URLs to simulate "Back" navigation.
STEP6: Display the popped URLs as output.
FOR QUEUE:
STEP1: Define a PrintJobNode class with attributes:
• doc to store the document name.
• next pointer to link to the next node.
STEP2: Define a PrintQueue class with:
• front and rear pointers initialized as None.
• enqueue(doc) to add a new document node at the rear.
• dequeue() to remove and return the document from the front.
STEP3: Enqueue print jobs (simulate job submission).
STEP4: Dequeue jobs in FIFO order (simulate printing).
STEP5: Display the dequeued documents as output.

12 | P a g e
PROGRAM
# Stack using Linked List
class StackNode:
def __init__(self, url):
[Link] = url
[Link] = None
class StackHistory:
def __init__(self):
[Link] = None
def push(self, url):
node = StackNode(url)
[Link] = [Link]
[Link] = node
def pop(self):
if not [Link]:
return None
url = [Link]
[Link] = [Link]
return url
# Queue using Linked List
class PrintJobNode:
def __init__(self, doc):
[Link] = doc
[Link] = None
class PrintQueue:
def __init__(self):
[Link] = [Link] = None
def enqueue(self, doc):
node = PrintJobNode(doc)
if not [Link]:

13 | P a g e
 [Link] = [Link] = node
return
[Link] = node
[Link] = node
def dequeue(self):
if not [Link]:
return None
doc = [Link]
[Link] = [Link]
if not [Link]:
[Link] = None
return doc
history = StackHistory()
# Push some URLs
[Link]("[Link]")
[Link]("[Link]")
[Link]("[Link]")
# Pop the last visited URL
print("Last visited (popped):", [Link]())
# Pop another
print("Last visited (popped):", [Link]())
# Create Print Queue
queue = PrintQueue()
# Enqueue some print jobs
[Link]("[Link]")
[Link]("[Link]")
[Link]("[Link]")
# Dequeue (print) jobs
print("\nPrinting Jobs:")
print("Printed:", [Link]())

14 | P a g e
print("Printed:", [Link]())
print("Printed:", [Link]())
OUTPUT

Last visited (popped): [Link]

Last visited (popped): [Link]
Printing Jobs:
Printed: [Link]
Printed: [Link]
Printed: [Link]

RESULT

Thus, the Python program using linked list implementation allowed dynamic and efficient
management of browser history and print queue scenarios, and has been implemented,
executed, and verified successfully.

15 | P a g e
 EX:4 DESIGN A PYTHON MODULE THAT INTEGRATES THE POLYNOMIAL
ADDITION PROGRAM WITH REAL-WORLD TAX SLABS, ALLOWING
DATE USERS TO INPUT INCOME RANGES AS POLYNOMIAL COEFFICIENTS
AND COMPUTE TOTAL TAX DYNAMICALLY.

AIM
To implement polynomial addition using linked lists in Python, simulating the tax
computation formula with variable components.
ALGORITHM
STEP1: Node Structure: Each node contains a coefficient (coeff), exponent (exp), and a
reference to the next node.
STEP2: Insertion: Insert nodes in descending order by exponent for proper
polynomial notation.
STEP3: Addition: Traverse two polynomials, adding coefficients of terms with the same
exponent, and append unmatched terms directly.
STEP4: Display: Traverse and print all polynomial terms.
STEP5: Evaluation: Substitute a value for the variable and compute the sum of all terms.
PROGRAM
class PolyNode:
def __init__(self, coeff, exp):
[Link] = coeff
[Link] = exp
[Link] = None
class Polynomial:
def __init__(self):
[Link] = None
def insert_term(self, coeff, exp):
new_node = PolyNode(coeff, exp)
if ([Link] is None) or ([Link] < exp):
new_node.next = [Link]
[Link] = new_node
else:
current = [Link]

16 | P a g e
 while [Link] and [Link] > exp:
current = [Link]
if [Link] and [Link] == exp:
[Link] += coeff
else:
new_node.next = [Link]
[Link] = new_node
def display(self):
terms = []
current = [Link]
while current:
if [Link] == 0:
[Link](f"{[Link]}")
elif [Link] == 1:
[Link](f"{[Link]}x")
else:
[Link](f"{[Link]}x^{[Link]}")
current = [Link]
print(" + ".join(terms) if terms else "0")
@staticmethod
def add(poly1, poly2):
result = Polynomial()
p1 = [Link]
p2 = [Link]
while p1 and p2:
if [Link] > [Link]:
result.insert_term([Link], [Link])
p1 = [Link]
elif [Link] < [Link]:
result.insert_term([Link], [Link])

17 | P a g e
 p2 = [Link]
else:
result.insert_term([Link] + [Link], [Link])
p1 = [Link]
p2 = [Link]
while p1:
result.insert_term([Link], [Link])
p1 = [Link]
while p2:
result.insert_term([Link], [Link])
p2 = [Link]
return result
def evaluate(self, x):
result = 0
current = [Link]
while current:
result += [Link] * (x ** [Link])
current = [Link]
return result
# Example Usage
# Define first tax formula: 3x^2 + 2x + 5
tax1 = Polynomial()
tax1.insert_term(3, 2)
tax1.insert_term(2, 1)
tax1.insert_term(5, 0)
# Define second tax formula: 2x^2 + 4
tax2 = Polynomial()
tax2.insert_term(2, 2)
tax2.insert_term(4, 0)
print("Tax Formula 1:")

18 | P a g e
[Link]()
print("Tax Formula 2:")
[Link]()
# Addition of two polynomials
combined_tax = [Link](tax1, tax2)
print("Combined Tax Formula:")
combined_tax.display()
# Evaluate for x = 2 (e.g., taxable income = 2 units)
result = combined_tax.evaluate(2)
print(f"Tax Amount for income=2: {result}")

OUTPUT
Tax Formula 1:
3x^2 + 2x + 5
Tax Formula 2:
2x^2 + 4
Combined Tax Formula:
5x^2 + 2x + 9
Tax Amount for income=2: 29

RESULT
Thus, the Python program for polynomial manipulation using linked lists was successfully
developed. The program efficiently created, added, displayed, and evaluated tax formulas
modeled as polynomials, enabling flexible and accurate automated tax computations. It has
been implemented, executed, and verified successfully

19 | P a g e
 EX:5 DESIGN AND DEVELOPMENT OF A CALCULATOR ENGINE USING
INFIX-TO-POSTFIX CONVERSION AND POSTFIX EVALUATION IN
DATE PYTHON

AIM
To implement evaluation of postfix expressions and conversion of infix expressions to postfix
form using Python.
ALGORITHM
STEP1: Use a stack to convert infix expression to postfix:
• If operand, add to postfix output.
• If operator, pop from stack based on precedence.
STEP2: For postfix evaluation:
• Traverse expression, push operands to stack.
• On operator, pop operands, apply operation, push result.
PROGRAM:
def infix_to_postfix(expression):
precedence = {'+':1, '-':1, '*':2, '/':2, '^':3}
stack = []
result = ''
for char in expression:
if [Link]():
result += char
elif char == '(':
[Link](char)
elif char == ')':
while stack and stack[-1] != '(':
result += [Link]()
[Link]()
else:
while stack and stack[-1] != '(' and [Link](stack[-1],0) >= precedence[char]:
result += [Link]()
[Link](char)
while stack:

20 | P a g e
 result += [Link]()
return result
def evaluate_postfix(expression):
stack = []
for char in expression:
if [Link]():
[Link](int(char))
else:
b = [Link]()
a = [Link]()
if char == '+':
[Link](a + b)
elif char == '-':
[Link](a - b)
elif char == '*':
[Link](a * b)
elif char == '/':
[Link](a // b)
return [Link]()
expression = "(3+5)*2"
postfix = infix_to_postfix(expression)
result = evaluate_postfix(postfix)
print("Infix Expression:", expression)
print("Postfix Expression:", postfix)
print("Evaluated Result:", result)
OUTPUT
Infix Expression: (3+5)*2 Postfix Expression: 35+2* Evaluated Result: 16
RESULT
Thus, the Python program for efficient and accurate conversion of infix expressions to postfix
form and evaluation of postfix expressions for backend computation has been implemented,
executed, and verified successfully.

21 | P a g e
 EX:6(a) IMPLEMENTATION OF BINARY SEARCH TREE (BST) WITH INSERTION,
SEARCH, AND INORDER TRAVERSAL IN PYTHON
DATE

AIM
To write a Python program to implement a Binary Search Tree (BST) with operations for
insertion, inorder traversal, and searching for specific elements.
ALGORITHM
STEP1: Insert: Compare new node's key with current node, insert left or right.
STEP2: Search: Traverse left or right depending on key comparison.
STEP3: Delete: Remove node and rearrange tree as per BST properties.
PROGRAM
class Node:
def __init__(self, key):
[Link] = key
[Link] = [Link] = None
class BST:
def __init__(self):
[Link] = None
def insert(self, root, key):
if not root:
return Node(key)
if key < [Link]:
[Link] = [Link]([Link], key)
else:
[Link] = [Link]([Link], key)
return root
def search(self, root, key):
if not root or [Link] == key:
return root
return [Link]([Link], key) if key < [Link] else [Link]([Link], key)
def inorder(self, root):

22 | P a g e
if root:
[Link]([Link])
print([Link], end=" ")
[Link]([Link])
# --- Main Program ---
bst = BST() # Create a BST object
root = None # Initialize root
# Insert elements into the BST
elements = [50, 30, 70, 20, 40, 60, 80]
for key in elements:
root = [Link](root, key)
# Display elements using Inorder Traversal
print("Inorder Traversal of BST:")
[Link](root)
print()
# Search for specific keys
search_keys = [40, 100]
for key in search_keys:
result = [Link](root, key)
if result:
print(f"Search {key}: Found")
else:
print(f"Search {key}: Not Found")
OUTPUT
Inorder Traversal of BST:
20 30 40 50 60 70 80 Search 40: Found Search 100: Not Found
RESULT
Thus, the Python program for implementing a Binary Search Tree (BST) was successfully
[Link] program allowed insertion of nodes, searching for elements, and displaying the
elements in sorted order using inorder traversal.

23 | P a g e
 EX:6(b) AN ARRAY OF N POSITIVE INTEGERS IS PASSED AS INPUT. THE
PROGRAM MUST FORM A BINARY SEARCH TREE WITH THESE
DATE NUMBERS. THE FIRST NUMBER (OUT OF THE N NUMBERS PASSED AS
INPUT) IS THE ROOT NODE OF THE BINARY SEARCH TREE.
IMPLEMENT THE FUNCTION PRINTINORDER() SO THAT THE
PROGRAM PRINTS THE IN-ORDER TRAVERSAL OF THE TREE FORMED.

AIM
To write a Python program that reads an array of N positive integers, constructs a Binary Search
Tree (BST) with the first element as the root, and prints the inorder traversal of the tree using
a function printInorder()
ALGORITHM
STEP1: Start.
STEP2: Read N positive integers as input into an array.
STEP3: Create a Node class with attributes key, left, and right.
STEP4: Define a BST class with the following functions:
insert(root, key):
▪ If root is None, create a new node and return it.
▪ If key < [Link], insert into the left subtree.
▪ Otherwise, insert into the right subtree.
printInorder(root):
▪ Recursively traverse the left subtree.
▪ Print the current node’s key.
▪ Recursively traverse the right subtree.
STEP5: Initialize root as None.
STEP6: For each element in the array, call insert() to build the BST (first element becomes the
root).
STEP7: Call printInorder(root) to display elements in sorted order.
STEP8: End.
PROGRAM
class Node:
def __init__(self, key):
[Link] = key
[Link] = None

24 | P a g e
 [Link] = None
class BST:
def __init__(self):
[Link] = None
def insert(self, root, key):
"""Insert a new key into the BST."""
if not root:
return Node(key)
if key < [Link]:
[Link] = [Link]([Link], key)
else:
[Link] = [Link]([Link], key)
return root
def printInorder(self, root):
"""Print the inorder traversal of BST."""
if root:
[Link]([Link])
print([Link], end=" ")
[Link]([Link])
# ---- Main Program ----
arr = list(map(int, input("Enter N positive integers separated by space: ").split()))
bst = BST()
root = None
# Build BST (first element as root)
for num in arr:
root = [Link](root, num)
# Print Inorder Traversal
print("Inorder Traversal of BST:")
[Link](root)
print()

25 | P a g e
OUTPUT
Enter N positive integers separated by space: 20 50 40 30 10
Inorder Traversal of BST:
10 20 30 40 50

RESULT
Thus, the Python program was successfully [Link] program constructed a Binary Search
Tree from the given array, with the first element as the root, and printed the elements in sorted
order using inorder traversal.

26 | P a g e
 EX:7 .
BALANCED BINARY SEARCH TREE IMPLEMENTATION USING AVL
DATE TREE IN PYTHON

AIM
To write a Python program that constructs a balanced Binary Search Tree (BST) using an AVL
Tree for a given set of integer keys, ensuring automatic balancing through rotations, and to
display the elements using inorder traversal.
ALGORITHM
STEP1: Start
STEP2: Create an AVLNode class with attributes: key, left, right, and height.
STEP3: Create an AVLTree class with methods
STEP4: For each key in the input array:
Insert the key into the AVL tree using the insert method.
Recalculate the balance factor and perform appropriate rotations if imbalance occurs:
o Left-Left (LL) rotation
o Right-Right (RR) rotation
o Left-Right (LR) rotation
o Right-Left (RL) rotation
STEP5: After inserting all keys, perform inorder traversal to print the sorted elements.
STEP6: Stop
PROGRAM
class AVLNode:
def __init__(self, key):
[Link] = key
[Link] = [Link] = None
[Link] = 1
class AVLTree:
def insert(self, root, key):
if not root:
return AVLNode(key)
if key < [Link]:

27 | P a g e
 [Link] = [Link]([Link], key)
else:
[Link] = [Link]([Link], key)
[Link] = 1 + max([Link]([Link]), [Link]([Link]))
balance = [Link](root)
# Left Left
if balance > 1 and key < [Link]:
return [Link](root)
# Right Right
if balance < -1 and key > [Link]:
return [Link](root)
# Left Right
if balance > 1 and key > [Link]:
[Link] = [Link]([Link])
return [Link](root)
# Right Left
if balance < -1 and key < [Link]:
[Link] = [Link]([Link])
return [Link](root)
return root
def getHeight(self, node):
return [Link] if node else 0
def getBalance(self, node):
return [Link]([Link]) - [Link]([Link]) if node else 0
def leftRotate(self, z):
y = [Link]
T2 = [Link]
[Link] = z
[Link] = T2
[Link] = 1 + max([Link]([Link]), [Link]([Link]))

28 | P a g e
 [Link] = 1 + max([Link]([Link]), [Link]([Link]))
return y
def rightRotate(self, y):
x = [Link]
T2 = [Link]
[Link] = y
[Link] = T2
[Link] = 1 + max([Link]([Link]), [Link]([Link]))
[Link] = 1 + max([Link]([Link]), [Link]([Link]))
return x
def inorder(self, root):
if root:
[Link]([Link])
print([Link], end=" ")
[Link]([Link])
# Driver Code
avl = AVLTree()
root = None
keys = [10, 20, 30, 15, 50, 25] # Sample input
for key in keys:
root = [Link](root, key)
print("Inorder Traversal of Balanced AVL Tree:")
[Link](root)
OUTPUT
Inorder Traversal of Balanced AVL Tree:
10 15 20 25 30 50
RESULT
The Python program successfully constructs a balanced AVL Tree from the given input keys.
The tree automatically balances itself after each insertion using single or double rotations.
The inorder traversal displays the keys in ascending sorted order:

29 | P a g e
 EX:8 DESIGNING AND EVALUATING A CUSTOM MIN HEAP-BASED
PRIORITY QUEUE FOR EMERGENCY ROOM PATIENT PRIORITIZATION
DATE IN PYTHON

AIM
To implement a Min Heap Priority Queue without using any predefined heap library, to
simulate an Emergency Room (ER) system where patients with higher severity (i.e., lower
priority number) are treated first.
ALGORITHM
STEP1: Start.
STEP2: Create a MinHeap class with the following functions:
• insert(patient, priority) – Adds a patient with their severity (priority) into the heap while
maintaining the Min Heap property.
• extract_min() – Removes and returns the patient with the lowest priority number
(highest severity).
• heapify() – Rearranges the heap to maintain the Min Heap property after insertion or
deletion.
STEP3: Read the list of patients along with their priority levels (severity).
STEP4: Insert each patient into the Min Heap.
STEP5: Continuously call extract_min() to simulate treating patients based on priority (lowest
priority number first).
STEP6: Display the order in which patients are treated.
STEP6: End
PROGRAM
class MinHeap:
def __init__(self):
[Link] = []
def insert(self, patient_name, priority):
# Append the new patient
[Link]((priority, patient_name))
self.__heapify_up(len([Link]) - 1)
def extract_min(self):
if not [Link]:

30 | P a g e
 print("No patients in queue.")
return None
if len([Link]) == 1:
return [Link]()

# Root is min; replace with last element

min_patient = [Link][0]
[Link][0] = [Link]()
self.__heapify_down(0)
return min_patient
def __heapify_up(self, index):
parent = (index - 1) // 2
if index > 0 and [Link][index][0] < [Link][parent][0]:
[Link][index], [Link][parent] = [Link][parent], [Link][index]
self.__heapify_up(parent)
def __heapify_down(self, index):
left = 2 * index + 1
right = 2 * index + 2
smallest = index
if left < len([Link]) and [Link][left][0] < [Link][smallest][0]:
smallest = left
if right < len([Link]) and [Link][right][0] < [Link][smallest][0]:
smallest = right
if smallest != index:
[Link][smallest], [Link][index] = [Link][index], [Link][smallest]
self.__heapify_down(smallest)
def display(self):
print("Current ER Queue (Priority, Patient):")
for patient in [Link]:
print(f"Priority: {patient[0]} - Patient: {patient[1]}")

31 | P a g e
 print()
# Example Usage
er_queue = MinHeap()
# Insert patients
er_queue.insert("Alice", 5) # Less critical
er_queue.insert("Bob", 3) # Moderate case
er_queue.insert("Charlie", 1) # Most critical
er_queue.insert("David", 4)
er_queue.insert("Eva", 2)
# Display the heap state
er_queue.display()
# Treat patients by extracting minimum (most severe priorities first)
print("Treating patients in order of severity:")
while True:
patient = er_queue.extract_min()
if patient is None:
break
print(f"Treating: {patient[1]} (Severity: {patient[0]})")

OUTPUT
Current ER Queue (Priority, Patient):
Priority: 1 - Patient: Charlie
Priority: 2 - Patient: Eva
Priority: 3 - Patient: Bob
Priority: 5 - Patient: Alice
Priority: 4 - Patient: David

32 | P a g e
Treating patients in order of severity:
Treating: Charlie (Severity: 1)
Treating: Eva (Severity: 2)
Treating: Bob (Severity: 3)
Treating: David (Severity: 4)
Treating: Alice (Severity: 5)

RESULT
Thus, the Python program for simulating Emergency Room patient prioritization using a Min
Heap (Priority Queue) was successfully implemented.

33 | P a g e
 EX:8(b) AN ARRAY OF N INTEGERS IS PASSED AS INPUT. FILL IN THE MISSING
LINES OF CODE TO IMPLEMENT THE BUILD MAXHEAP FUNCTION TO
DATE BUILD A MAX HEAP AND PRINT THE ELEMENTS IN DESCENDING
ORDER USING HEAP SORT. THE HEAP IS BUILT ON ARRAY STARTING
FROM INDEX 1. THE LEFT AND RIGHT CHILD OF AN ELEMENT AT
INDEX I IS OBTAINED FROM THE INDEX (2*I) AND (2*I+1)
RESPECTIVELY.

AIM
To implement a Python program to build a Max Heap using 1-based indexing and perform
Heap Sort to display the elements in descending order.
ALGORITHM
STEP1: Start
STEP2: Take an array of N integers as input (with index starting from 1; index 0 is unused).
STEP3: Define a heapify() function:
• Compare the current node at index i with its left child 2*i and right child 2*i+1.
• Swap the largest element to the root.
• Recursively heapify the affected subtree if a swap occurs.
STEP4: Define buildMaxHeap():
• For all non-leaf nodes (from N//2 down to 1), call heapify() to convert the array into a
Max Heap.
STEP5: Define heapSort():
• First, build the Max Heap using buildMaxHeap().
• Swap the first (largest) element with the last element of the heap.
• Reduce the heap size by 1 and call heapify() on the root to maintain the Max Heap
property.
• Repeat until all elements are sorted.
STEP6: Print the sorted array in descending order.
STEP7: Stop

PROGRAM
ef heapify(arr, n, i):
# Max heapify at index i
largest = i

34 | P a g e
 left = 2 * i
right = 2 * i + 1
# Check left child
if left <= n and arr[left] > arr[largest]:
largest = left
# Check right child
if right <= n and arr[right] > arr[largest]:
largest = right
# Swap and continue heapifying if needed
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def buildMaxHeap(arr, n):
# Start from last non-leaf node and go up to the root
for i in range(n // 2, 0, -1):
heapify(arr, n, i)

def heapSort(arr, n):

# Step 1: Build Max Heap
buildMaxHeap(arr, n)
# Step 2: Extract elements one by one
for i in range(n, 1, -1):
arr[1], arr[i] = arr[i], arr[1] # Swap max with last
heapify(arr, i - 1, 1) # Heapify reduced heap
# Input array (1-based indexing, so index 0 is dummy)
arr = [None] + [20, 5, 15, 22, 40, 10]
n = len(arr) - 1 # Ignore index 0
print("Original Array (1-based indexing):")
print(arr[1:])
# Perform Heap Sort

35 | P a g e
heapSort(arr, n)
# Output sorted elements (descending order)
print("\nElements in Descending Order after Heap Sort:")
print(arr[1:])

OUTPUT
Original Array (1-based indexing):
[20, 5, 15, 22, 40, 10]

Elements in Descending Order after Heap Sort:

[5, 10, 15, 20, 22, 40]

RESULT
Thus, the program successfully builds a Max Heap and sorts the array in descending order
using Heap Sort.

36 | P a g e
 EX:9
DESIGN AND IMPLEMENT A PYTHON-BASED SOLUTION TO COMPUTE
DATE OPTIMAL SHORTEST PATHS IN WEIGHTED GRAPHS USING DIJKSTRA’S
ALGORITHM

AIM
To write a Python program to implement Dijkstra’s Algorithm using a Min Heap (heapq) to
determine the shortest distance from a source node to all other nodes in a weighted directed
graph.
ALGORITHM
STEP1: Create a graph where nodes represent locations and edges represent roads with
distances.
STEP2: Assign initial distance to source as 0, others as infinity.
STEP3: Use a priority queue to repeatedly visit the node with the smallest known distance.
STEP4: For each neighbor, update distance if a shorter path is found.
STEP5: Repeat until destination or all nodes are visited.
STEP6: Stop
PROGRAM
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
visited = set()
heap = [(0, start)]
while heap:
curr_dist, curr_node = [Link](heap)
if curr_node in visited:
continue
[Link](curr_node)
for neighbor, weight in graph[curr_node].items():
distance = curr_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance

37 | P a g e
 [Link](heap, (distance, neighbor))
return distances
# Example graph
graph = {
'A': {'B': 5, 'C': 2},
'B': {'D': 1},
'C': {'B': 8, 'D': 7},
'D': {}
}
print(dijkstra(graph, 'A'))
OUTPUT
{'A': 0, 'B': 5, 'C': 2, 'D': 6}

RESULT
The Python program was successfully [Link] calculated the shortest distances from the
source node 'A' to all other nodes in the given weighted graph using Dijkstra’s Algorithm.

38 | P a g e
 EX:10(a)
MINIMUM SPANNING TREE CONSTRUCTION USING KRUSKAL’S
DATE ALGORITHM IN PYTHON

AIM
To write a Python program that constructs a Minimum Spanning Tree (MST) from a given
weighted undirected graph using Kruskal’s Algorithm, applying the Union-Find technique to
avoid cycles.
ALGORITHM
STEP1: Start.
STEP2: Represent the graph as a list of edges, where each edge is (u, v, weight).
STEP3: Sort all edges in non-decreasing order of their weights.
STEP4: Initialize:
• rank array for efficient union operations.
• result list to store MST edges.
STEP5: For each edge (u, v, w) in sorted order:
STEP6: Find the parent (root) of u and v using the Find function.
STEP7: If they belong to different sets:
o Include the edge (u, v, w) in result.
o Perform Union of the two sets.
STEP8: Repeat until the MST contains V-1 edges (where V is the number of vertices).
STEP9: Display the edges included in the MST.
STEP10. Stop.
PROGRAM (KRUSKAL'S)
def find(parent, i):
if parent[i] != i:
parent[i] = find(parent, parent[i])
return parent[i]
def union(parent, rank, x, y):
xroot, yroot = find(parent, x), find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot

39 | P a g e
 elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1
def kruskal(graph):
result, parent, rank = [], [], []
for node in range(len(graph)):
[Link](node)
[Link](0)
edges = sorted(graph, key=lambda item: item[2])
e=0
i=0
while e < len(graph)-1 and i < len(edges):
u, v, w = edges[i]
i += 1
x, y = find(parent, u), find(parent, v)
if x != y:
e += 1
[Link]((u, v, w))
union(parent, rank, x, y)
return result
# Example: graph = [(0, 1, 10), (1, 2, 5), (0, 2, 6)]
graph = [(0, 1, 10), (1, 2, 5), (0, 2, 6)]
print(kruskal(graph)
OUTPUT
Edges in MST: (1, 2, 5), (0, 2, 6)
RESULT
The Python program was successfully executed. The program constructed a Minimum
Spanning Tree (MST) for the given weighted undirected graph using Kruskal’s Algorithm.

40 | P a g e
 EX:10(b)
MINIMUM SPANNING TREE CONSTRUCTION USING PRIM’S
DATE ALGORITHM IN PYTHON

AIM
To write a Python program to implement Prim’s Algorithm using a priority queue (min-heap)
for finding the Minimum Spanning Tree (MST) of a given weighted undirected graph.
ALGORITHM
STEP1: Start with any arbitrary vertex as the starting point.
STEP2: Mark the starting vertex as visited and add all its edges to a priority queue (min-heap)
based on their weights.
STEP3: While there are edges in the priority queue:
• Remove the edge with the minimum weight.
• If the connected vertex is not visited:
o Mark it as visited.
o Add this edge to the MST.
o Add all edges from this vertex to the priority queue (if their destination vertex
is not visited).
STEP4: Repeat until all vertices are included in the MST.
STEP5: Print the edges of the Minimum Spanning Tree.

PROGRAM:
from heapq import heappush, heappop
def prim(graph):
min_spanning_tree = []
visited = set()
start_vertex = list([Link]())[0]
priority_queue = [(weight, start_vertex, neighbor) for neighbor, weight in
graph[start_vertex]]
heappush(priority_queue, (0, None, start_vertex))
while priority_queue:
weight, parent, current_vertex = heappop(priority_queue)

41 | P a g e
 if current_vertex not in visited:
[Link](current_vertex)
if parent is not None:
min_spanning_tree.append((parent, current_vertex, weight))
for neighbor, edge_weight in graph[current_vertex]:
if neighbor not in visited:
heappush(priority_queue, (edge_weight, current_vertex, neighbor))
return min_spanning_tree
# Example graph represented as an adjacency list
graph = {
'A': [('B', 2), ('C', 1)],
'B': [('A', 2), ('D', 3), ('E', 1)],
'C': [('A', 1), ('D', 4)],
'D': [('B', 3), ('C', 4), ('E', 1)],
'E': [('B', 1), ('D', 1)]
}
minimum_spanning_tree = prim(graph)
print("Minimum Spanning Tree:")
print(minimum_spanning_tree)

OUTPUT
Minimum Spanning Tree:
[('A', 'C', 1), ('A', 'B', 2), ('B', 'E', 1), ('E', 'D', 1)]

RESULT
Thus, the Python program was successfully [Link] program constructed the Minimum
Spanning Tree (MST) for the given graph using Prim’s Algorithm, and displayed the edges
with their corresponding weights.

42 | P a g e
 EX:11
DESIGN AND DEVELOP A DUAL-MODE INVENTORY LOOKUP SYSTEM
DATE USING LINEAR AND BINARY SEARCH FOR OPTIMIZED PRODUCT
RETRIEVAL IN PYTHON

AIM
To implement linear search and binary search algorithms in Python for efficiently finding a
product within an inventory database.
ALGORITHM
LINEAR SEARCH
STEP1: Iterate through the product list from start to finish.
STEP2: Compare each product's ID with the search ID.
STEP3: If a match is found, return the index or product details.
STEP4: If the end of the list is reached without a match, report as "not found."
BINARY SEARCH (ON SORTED INVENTORY)
STEP1: Start with the entire sorted inventory list.
STEP2: Find the middle element.
STEP3: If the search ID matches the middle, return the result.
STEP4: If the search ID is less, continue the search in the left half; if more, in the right half.
STEP5: Repeat until the element is found or the search space is empty.
PROGRAM
# Sample inventory: list of dictionaries, each with 'id' and 'name'
inventory = [
{"id": 101, "name": "Laptop"},
{"id": 202, "name": "Smartphone"},
{"id": 303, "name": "Tablet"},
{"id": 404, "name": "Headphones"}
]
def linear_search(inventory, product_id):
for idx, product in enumerate(inventory):
if product['id'] == product_id:
return idx, product

43 | P a g e
 return -1, None
def binary_search(inventory, product_id):
left, right = 0, len(inventory) - 1
while left <= right:
mid = (left + right) // 2
if inventory[mid]['id'] == product_id:
return mid, inventory[mid]
elif inventory[mid]['id'] < product_id:
left = mid + 1
else:
right = mid - 1
return -1, None
# Example usage:
# Linear Search (unsorted or general case)
print("Linear Search Result:")
idx, product = linear_search(inventory, 303)
if idx != -1:
print(f"Product found at index {idx}: {product}")
else:
print("Product not found.")
# Binary Search (works if inventory is sorted by 'id')
sorted_inventory = sorted(inventory, key=lambda x: x['id'])
print("\nBinary Search Result:")
idx, product = binary_search(sorted_inventory, 404)
if idx != -1:
print(f"Product found at index {idx}: {product}")
else:
print("Product not found.")

44 | P a g e
OUTPUT
Linear Search Result:
Product found at index 2: {'id': 303, 'name': 'Tablet'}
Binary Search Result:
Product found at index 3: {'id': 404, 'name': 'Headphones'}

RESULT
The program was executed successfully. It searched for a product by its ID using linear search
for unsorted inventory and binary search for sorted inventory, providing correct results in both
cases.

45 | P a g e
 EX:12 DESIGN A PYTHON PROGRAM THAT ALLOWS TEACHERS TO SWITCH
DYNAMICALLY BETWEEN INSERTION SORT AND SELECTION SORT
DATE BASED ON THE SIZE AND NATURE OF THE STUDENT SCORE LIST
(PARTIALLY SORTED VS. UNSORTED).

AIM
To implement Insertion Sort and Selection Sort algorithms in Python to sort students’ exam
scores in ascending order for generating performance-based reports.
ALGORITHM
INSERTION SORT ALGORITHM
STEP1: Start from the second element (index 1).
STEP2: Compare the current element with elements before it.
STEP3: Shift larger elements to the right.
STEP4: Insert the current element at its correct position.
STEP5: Repeat till the end of the list.
SELECTION SORT ALGORITHM
STEP1: Traverse the list to find the minimum element.
STEP2: Swap the minimum element with the first unsorted element.
STEP3: Repeat for the remaining unsorted sublist.

PROGRAM
def insertion_sort(scores):
for i in range(1, len(scores)):
key = scores[i]
j=i-1
while j >= 0 and key < scores[j]:
scores[j + 1] = scores[j]
j -= 1
scores[j + 1] = key
return scores
def selection_sort(scores):
n = len(scores)
for i in range(n):

46 | P a g e
 min_index = i
for j in range(i+1, n):
if scores[j] < scores[min_index]:
min_index = j
scores[i], scores[min_index] = scores[min_index], scores[i]
return scores
# Original list of exam scores
exam_scores = [72, 88, 53, 94, 78, 60]
# Apply Insertion Sort
print("Original Exam Scores:", exam_scores)
sorted_by_insertion = insertion_sort(exam_scores.copy())
print("Sorted by Insertion Sort:", sorted_by_insertion)
# Apply Selection Sort
sorted_by_selection = selection_sort(exam_scores.copy())
print("Sorted by Selection Sort:", sorted_by_selection)

OUTPUT
Original Exam Scores: [72, 88, 53, 94, 78, 60]
Sorted by Insertion Sort: [53, 60, 72, 78, 88, 94]
Sorted by Selection Sort: [53, 60, 72, 78, 88, 94]

RESULT
Insertion Sort and Selection Sort were successfully implemented to sort students’ exam scores.
The sorted list helps in generating accurate rank reports and performance graphs.

47 | P a g e
 EX:13 A PERSONAL FINANCE APPLICATION NEEDS TO AUTOMATICALLY
CATEGORIZE AND SORT A USER’S MONTHLY EXPENSES (SUCH AS
DATE RENT, FOOD, UTILITIES, TRAVEL, MISCELLANEOUS) BASED ON
AMOUNTS. SORTING THESE EXPENSES USING MERGE SORT HELPS
USERS UNDERSTAND SPENDING PRIORITIES AND VISUALIZE DATA
EFFICIENTLY.

AIM
To implement the Merge Sort algorithm in Python to categorize and sort monthly expenses in
ascending order, enabling better financial visualization and planning.
ALGORITHM:
MERGE SORT
STEP1: Divide the List:
• If the list has more than one element, divide it into two halves.
STEP2: Sort Both Halves:
• Recursively sort the left and right halves.
STEP3: Merge the Sorted Halves:
• Compare elements from both halves.
• Insert the smaller element into the result list.
• Repeat until all elements are merged in sorted order.
STEP4: Time Complexity:
• Best, Average, Worst: O(n log n)
PROGRAM
# Merge Sort Implementation
def merge_sort(expenses):
if len(expenses) > 1:
mid = len(expenses) // 2
left_half = expenses[:mid]
right_half = expenses[mid:]
# Recursive call
merge_sort(left_half)
merge_sort(right_half)

48 | P a g e
 # Merging the sorted halves
i=j=k=0
while i < len(left_half) and j < len(right_half):
if left_half[i][1] < right_half[j][1]:
expenses[k] = left_half[i]
i += 1
else:
expenses[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
expenses[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
expenses[k] = right_half[j]
j += 1
k += 1
# Sample Monthly Expenses (category, amount)
monthly_expenses = [
("Rent", 15000),
("Food", 5000),
("Utilities", 3000),
("Travel", 4500),
("Miscellaneous", 2500)
]
print("Original Monthly Expenses:")
for category, amount in monthly_expenses:
print(f"{category}: ₹{amount}")
# Sort expenses using merge sort

49 | P a g e
merge_sort(monthly_expenses)
print("\nSorted Monthly Expenses (Ascending):")
for category, amount in monthly_expenses:
print(f"{category}: ₹{amount}")

OUTPUT
Original Monthly Expenses:
Rent: ₹15000
Food: ₹5000
Utilities: ₹3000
Travel: ₹4500
Miscellaneous: ₹2500
Sorted Monthly Expenses (Ascending):
Miscellaneous: ₹2500
Utilities: ₹3000
Travel: ₹4500
Food: ₹5000
Rent: ₹15000

RESULT
The Merge Sort algorithm was successfully implemented to sort monthly expenses in
ascending order based on amount.

50 | P a g e
 EX:14 IN A WAREHOUSE, PRODUCTS OF VARYING SIZES OCCUPY SHELF
SPACE. TO REDUCE SPACE WASTAGE AND IMPROVE ITEM ACCESS
DATE TIME, THE WAREHOUSE MANAGEMENT SYSTEM NEEDS TO SORT
INVENTORY ITEMS BY SIZE. THIS OPTIMIZATION IS DONE USING THE
QUICK SORT ALGORITHM FOR BETTER PERFORMANCE IN LARGE-
SCALE DATA.

AIM
To implement the Quick Sort algorithm in Python to efficiently sort item sizes in ascending
order to optimize shelf space and inventory organization in a warehouse system.
ALGORITHM
STEP1: Start
STEP2: Take a list of unsorted item sizes.
STEP3: If the list contains 1 or 0 elements, return the list (base case).
STEP4: Choose the middle element as the pivot.
STEP5: Partition the list into:
• left: elements less than pivot,
• middle: elements equal to pivot (including duplicates),
• right: elements greater than pivot.
STEP6: Recursively apply Quick Sort on left and right.
STEP7: Combine the results as quick_sort(left) + middle + quick_sort(right).
STEP8: Display the original and sorted lists.
STEP9: End
PROGRAM
# Quick Sort implementation
def quick_sort(items):
if len(items) <= 1:
return items
else:
pivot = items[len(items) // 2] # Choose middle element as pivot
left = [x for x in items if x < pivot]
middle = [x for x in items if x == pivot] # Include duplicates
right = [x for x in items if x > pivot]
51 | P a g e
 return quick_sort(left) + middle + quick_sort(right)
# Sample item sizes in centimeters
item_sizes = [45, 12, 78, 23, 56, 10, 89, 33]
print("Original Item Sizes (in cm):")
print(item_sizes)
# Sort using Quick Sort
sorted_sizes = quick_sort(item_sizes)
print("\nSorted Item Sizes (in cm):")
print(sorted_sizes)
OUTPUT
Original Item Sizes (in cm):
[45, 12, 78, 23, 56, 10, 89, 33]
Sorted Item Sizes (in cm):
[10, 12, 23, 33, 45, 56, 78, 89]

RESULT
The Quick Sort algorithm was successfully implemented to sort warehouse product sizes
efficiently.

52 | P a g e
 EX:15 IMPLEMENTATION OF HASH TABLE WITH LINEAR PROBING AND
QUADRATIC PROBING IN PYTHON
DATE

AIM
To implement a hash table in Python that resolves collisions using Linear Probing and
Quadratic Probing, and to display the final hash table state after inserting multiple keys
ALGORITHM
STEP1: Start
STEP2: Create a HashTable class with:
Initialize the table size and two separate tables for Linear Probing and Quadratic
Probing (all set to None initially).
display(): Print both hash tables (Linear and Quadratic).
STEP3: Create a HashTable object of size 7.
STEP4: Insert keys [10, 20, 5, 15, 7] using Linear Probing.
STEP5: Insert keys [10, 20, 5, 15, 7] using Quadratic Probing.
STEP6: Display the final hash tables.
STEP8: Stop
PROGRAM
class HashTable:
def __init__(self, size):
[Link] = size
self.table_linear = [None for _ in range(size)]
self.table_quadratic = [None for _ in range(size)]

def linear_probing_insert(self, key):

index = key % [Link]
start_index = index # Save for cycle check
while self.table_linear[index] is not None:
index = (index + 1) % [Link]
if index == start_index:
print("Hash Table is Full - Linear Probing")

53 | P a g e
 return
self.table_linear[index] = key
def quadratic_probing_insert(self, key):
index = key % [Link]
i=1
start_index = index
while self.table_quadratic[index] is not None:
index = (start_index + i ** 2) % [Link]
i += 1
if i == [Link]:
print("Hash Table is Full - Quadratic Probing")
return
self.table_quadratic[index] = key
def display(self):
print("\nHash Table (Linear Probing):")
for i, val in enumerate(self.table_linear):
print(f"Index {i}: {val}")
print("\nHash Table (Quadratic Probing):")
for i, val in enumerate(self.table_quadratic):
print(f"Index {i}: {val}")

# ---------------- MAIN PROGRAM ----------------

# Create a hash table of size 7
hash_table = HashTable(7)
# Insert keys using Linear Probing
keys_linear = [10, 20, 5, 15, 7]
for key in keys_linear:
hash_table.linear_probing_insert(key)
# Insert keys using Quadratic Probing

54 | P a g e
keys_quadratic = [10, 20, 5, 15, 7]
for key in keys_quadratic:
hash_table.quadratic_probing_insert(key)
# Display the hash tables
hash_table.display()

OUTPUT
Hash Table (Linear Probing):
Index 0: 7
Index 1: 15
Index 2: None
Index 3: 10
Index 4: None
Index 5: 5
Index 6: 20
Hash Table (Quadratic Probing):
Index 0: 7
Index 1: 15
Index 2: None
Index 3: 10
Index 4: None
Index 5: 5
Index 6: 20

RESULT
Thus, the keys are successfully stored in the hash table using both Linear and Quadratic
Probing, resolving collisions effectively.

55 | P a g e