Exp No: 1 Student Record Management System (Procedural Date :

Approach)

AIM:
To develop a Student Record Management System using the
procedural approach in Python.

ALGORITHM:
1. Start the program.

2. Initialize a file (e.g., students.txt) to store student data.

3. Define a function add_student():

○ Get student roll number, name, age, and grade from the
user.

○ Append the record to the file.

4. Define a function view_students():

○ Read the file.

○ Display each student record line by line.

5. Define a function search_student():

○ Ask for roll number to search.

○ Read all lines from the file.

○ Find and display the matching record if it exists

6. Define a function update_student():

○ Ask for roll number to update.

 ○ Read all records.

○ Modify the matching record.

○ Write all records back to the file.

7. Define a function delete_student():

○ Ask for roll number to delete.

○ Read all records.

○ Remove the matching record.

○ Write the remaining records back to the file.

8. Define a menu() function:

○ Show options (Add, View, Search, Update, Delete, Exit).

○ Loop through menu until the user chooses to exit.

9. Stop the Program.

CODING:

import os

FILENAME = "students.txt"

# Function to add a new student

def add_student():
roll = input("Enter Roll Number: ")
name = input("Enter Name: ")
age = input("Enter Age: ")
grade = input("Enter Grade: ")
with open(FILENAME, "a") as file:
file.write(f"{roll},{name},{age},{grade}\n")
print("Student added successfully.\n")

# Function to view all student records

def view_students():
if not os.path.exists(FILENAME):
print("No records found.\n")
return
print("\nAll Student Records:")
print("Roll\tName\tAge\tGrade")
print("-" * 30)
with open(FILENAME, "r") as file:
for line in file:
roll, name, age, grade = line.strip().split(",")
print(f"{roll}\t{name}\t{age}\t{grade}")
print()

# Function to search for a student by roll number

def search_student():
roll_search = input("Enter Roll Number to search: ")
found = False
if not os.path.exists(FILENAME):
print("No records found.\n")
return
 with open(FILENAME, "r") as file:
for line in file:
roll, name, age, grade = line.strip().split(",")
if roll == roll_search:
print("\nStudent Found:")
print("Roll\tName\tAge\tGrade")
print(f"{roll}\t{name}\t{age}\t{grade}\n")
found = True
break
if not found:
print("Student not found.\n")

# Function to update a student's record

def update_student():
roll_update = input("Enter Roll Number to update: ")
updated = False
if not os.path.exists(FILENAME):
print("No records to update.\n")
return
with open(FILENAME, "r") as file:
records = file.readlines()
with open(FILENAME, "w") as file:
for line in records:
roll, name, age, grade = line.strip().split(",")
if roll == roll_update:
print("Enter new details:")
name = input("New Name: ")
age = input("New Age: ")
grade = input("New Grade: ")
file.write(f"{roll},{name},{age},{grade}\n")
updated = True
else:
file.write(line)
if updated:
print("Student record updated.\n")
else:
print("Student not found.\n")
# Function to delete a student record
def delete_student():
roll_delete = input("Enter Roll Number to delete: ")
deleted = False
if not os.path.exists(FILENAME):
print("No records to delete.\n")
return
with open(FILENAME, "r") as file:
records = file.readlines()
with open(FILENAME, "w") as file:
for line in records:
roll, name, age, grade = line.strip().split(",")
if roll == roll_delete:
deleted = True
continue # Skip writing this record
else:
file.write(line)
if deleted:
print("Student record deleted.\n")
else:
print("Student not found.\n")

# Main menu function

def menu():
while True:
print("===== Student Record Management System =====")
print("1. Add Student")
print("2. View Students")
print("3. Search Student")
print("4. Update Student")
print("5. Delete Student")
print("6. Exit")
choice = input("Enter your choice (1-6): ")
if choice == '1':
add_student()
elif choice == '2':
 view_students()
elif choice == '3':
search_student()
elif choice == '4':
update_student()
elif choice == '5':
delete_student()
elif choice == '6':
print("Exiting the system. Goodbye!")
break
else:
print("Invalid choice. Please try again.\n")

# Run the system

menu()

Output:

===== Student Record Management System =====

1. Add Student

2. View Students

3. Search Student

4. Update Student

5. Delete Student

6. Exit

Enter your choice (1-6): 1

Enter Roll Number: 101

Enter Name: Alice

Enter Age: 20

Enter Grade: A

Student added successfully.

===== Student Record Management System =====

1. Add Student

2. View Students

3. Search Student

4. Update Student

5. Delete Student

6. Exit

Enter your choice (1-6): 2

All Student Records:

Roll Name Age Grade

------------------------------

101 Alice 20 A
RESULT:
Thus the program was executed successfully and the output
was verified.
Exp No : 2 Bank Account Simulation Using OOP Date :

AIM:
To simulate the operations of a bank account using Object-
Oriented Programming (OOP) in Python.

Algorithm:
1. Start the program.

2. Create a class BankAccount with the following

attributes:

o account_number

o account_holder_name

o balance (initially 0 or a given value)

3. Define the following methods inside the class:

o __init__() → Constructor to initialize account

o deposit(amount) → Add amount to balance

o withdraw(amount) → Deduct amount if balance is

sufficient

o check_balance() → Return current balance

o display_account_details() → Print all account info

4. In the main section of the program:

o Create an instance of the BankAccount class

 o Display a menu to the user:

§ Deposit

§ Withdraw

§ Check balance

§ View account details

§ Exit

5. Based on user input, call the appropriate method.

6. Loop until the user chooses to exit.

7. Stop the program

CODING:
class BankAccount:

def __init__(self, account_number, account_holder_name,

initial_balance=0.0):

self.account_number = account_number

self.account_holder_name = account_holder_name

self.balance = initial_balance

print(f" Account for {self.account_holder_name} created

successfully.\n")

def deposit(self, amount):

if amount > 0:

self.balance += amount

print(f" Deposited ₹{amount}. New Balance:

₹{self.balance:.2f}")

else:

print(" Deposit amount must be greater than zero.")

def withdraw(self, amount):

if amount > self.balance:

print(" Insufficient balance.")

elif amount <= 0:

print(" Withdrawal amount must be greater than zero.")

else:
 self.balance -= amount

print(f" Withdrawn ₹{amount}. New Balance:

₹{self.balance:.2f}")

def check_balance(self):

print(f" Current Balance: ₹{self.balance:.2f}")

def display_account_details(self):

print("\n Account Details:")

print(f"Account Number: {self.account_number}")

print(f"Account Holder: {self.account_holder_name}")

print(f"Balance: ₹{self.balance:.2f}\n")

# Main Menu

def main():

print(" Welcome to Bank Account Simulation")

acc_number = input("Enter Account Number: ")

acc_holder = input("Enter Account Holder Name: ")

initial_amount = float(input("Enter Initial Deposit Amount (₹): "))

# Create a bank account object

account = BankAccount(acc_number, acc_holder, initial_amount)

 while True:

print("\n====== MENU ======")

print("1. Deposit Money")

print("2. Withdraw Money")

print("3. Check Balance")

print("4. Account Details")

print("5. Exit")

choice = input("Enter your choice (1-5): ")

if choice == '1':

amount = float(input("Enter amount to deposit: ₹"))

account.deposit(amount)

elif choice == '2':

amount = float(input("Enter amount to withdraw: ₹"))

account.withdraw(amount)

elif choice == '3':

account.check_balance()

elif choice == '4':

account.display_account_details()

elif choice == '5':

print(" Thank you for using the Bank Account Simulation.

Goodbye!")

break
 else:

print(" Invalid choice. Please select from 1 to 5.")

# Run the program

main()

OUTPUT:
User Input:

Enter Account Number: 12345678

Enter Account Holder Name: Alice

Enter Initial Deposit Amount (₹): 5000

Menu Interaction:
1. Deposit Money

2. Withdraw Money

3. Check Balance

4. Account Details

5. Exit

Enter your choice (1-5): 1

Enter amount to deposit: ₹2000

Deposited ₹2000. New Balance: ₹7000.00

Enter your choice (1-5): 2

Enter amount to withdraw: ₹1500

Withdrawn ₹1500. New Balance: ₹5500.00

Enter your choice (1-5): 4

Account Details:

Account Number: 12345678

Account Holder: Alice

Balance: ₹5500.00
RESULT:
Thus the program was executed successfully and the output was
verified.
Exp No : 3 Implement Custom Stack and Queue Date :
ADTs with Recursion and Algorithm
Analysis

AIM:
Implement Custom Stack and Queue ADTs with Recursion and
Algorithm Analysis

Algorithm:
Stack Behaviour:

· LIFO: Last In, First Out

· Implemented using a linked list

· Uses recursion to calculate size and print elements.

Queue Behaviour:

· FIFO: First In, First Out

· Implemented using a linked list

· Uses recursion in display and size

CODING:
class StackNode:

def __init__(self, data):

self.data = data

self.next = None

class Stack:

def __init__(self):

self.top = None

def is_empty(self):

return self.top is None # O(1)

def push(self, item):

new_node = StackNode(item)

new_node.next = self.top

self.top = new_node # O(1)

def pop(self):

if self.is_empty():

raise IndexError("Pop from empty stack")

item = self.top.data

self.top = self.top.next # O(1)

 return item

def peek(self):

if self.is_empty():

raise IndexError("Peek from empty stack")

return self.top.data # O(1)

def size(self):

return self._size_recursive(self.top)

def _size_recursive(self, node):

if node is None:

return 0

return 1 + self._size_recursive(node.next) # O(n), O(n) space

def display(self):

print("Stack (Top to Bottom):")

self._display_recursive(self.top)

def _display_recursive(self, node):

if node is None:

return

print(node.data)
 self._display_recursive(node.next) # O(n), O(n) space

class QueueNode:

def __init__(self, data):

self.data = data

self.next = None

class Queue:

def __init__(self):

self.front = self.rear = None

def is_empty(self):

return self.front is None # O(1)

def enqueue(self, item):

new_node = QueueNode(item)

if self.rear is None:

self.front = self.rear = new_node

else:

self.rear.next = new_node

self.rear = new_node # O(1)

def dequeue(self):

if self.is_empty():

raise IndexError("Dequeue from empty queue")

item = self.front.data

self.front = self.front.next

if self.front is None:

self.rear = None # O(1)

return item

def peek(self):

if self.is_empty():

raise IndexError("Peek from empty queue")

return self.front.data # O(1)

def size(self):

return self._size_recursive(self.front)

def _size_recursive(self, node):

if node is None:

return 0

return 1 + self._size_recursive(node.next) # O(n)

def display(self):
 print("Queue (Front to Rear):")

self._display_recursive(self.front)

def _display_recursive(self, node):

if node is None:

return

print(node.data)

self._display_recursive(node.next) # O(n)

# ----------- Example function calls -------------

if __name__ == "__main__":

# Testing Stack

stack = Stack()

print("Pushing onto stack: 10, 20, 30")

stack.push(10)

stack.push(20)

stack.push(30)

stack.display() # Should print 30, 20, 10 (top to bottom)

print(f"Stack size: {stack.size()}")

print(f"Top element (peek): {stack.peek()}")

 print(f"Popped element: {stack.pop()}")

stack.display()

print(f"Stack size after pop: {stack.size()}")

# Testing Queue

queue = Queue()

print("\nEnqueuing into queue: 100, 200, 300")

queue.enqueue(100)

queue.enqueue(200)

queue.enqueue(300)

queue.display() # Should print 100, 200, 300 (front to rear)

print(f"Queue size: {queue.size()}")

print(f"Front element (peek): {queue.peek()}")

print(f"Dequeued element: {queue.dequeue()}")

queue.display()

print(f"Queue size after dequeue: {queue.size()}")

Output:
Pushing onto stack: 10, 20, 30

Stack (Top to Bottom):

30

20

10
Stack size: 3

Top element (peek): 30

Popped element: 30

Stack (Top to Bottom):

20

10

Stack size after pop: 2

Enqueuing into queue: 100, 200, 300

Queue (Front to Rear):

100

200

300

Queue size: 3

Front element (peek): 100

Dequeued element: 100

Queue (Front to Rear):

200

300

Queue size after dequeue: 2

RESULT:
Thus the program was executed successfully and the output was
verified.
Exp No : 4 Recursive Merge Sort with Operation Date :
Count and Custom Object Sorting

AIM:
Implementing the Program Recursive Merge Sort with Operation
Count and Custom Object Sorting.

ALGORITHM:
MERGE_SORT(A, key):

1. If length of A ≤ 1:

Return A // Base case

2. Divide A into two halves:

mid ← length(A) // 2

Left ← A[0 .. mid-1]

Right ← A[mid .. end]

3. Recursively sort both halves:

SortedLeft ← MERGE_SORT(Left, key)

SortedRight ← MERGE_SORT(Right, key)

4. Return MERGE(SortedLeft, SortedRight, key)

 MERGE(Left, Right, key):

1. Create empty list Result

2. Initialize pointers i ← 0, j ← 0

3. While i < length(Left) and j < length(Right):

Increment comparison_count by 1

If key(Left[i]) ≤ key(Right[j]):

Append Left[i] to Result

i←i+1

Else:

Append Right[j] to Result

j←j+1

4. Append remaining elements of Left[i..] to Result

5. Append remaining elements of Right[j..] to Result

6. Stop the program.

CODING:
# Custom Object Class
class Student:
def __init__(self, name, grade):
self.name = name
self.grade = grade

def __repr__(self):
return f"{self.name} ({self.grade})"

# Merge Sort with Operation Counter

class MergeSortCounter:
def __init__(self):
self.comparisons = 0
self.merges = 0

def merge_sort(self, arr, key=lambda x: x):

if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = self.merge_sort(arr[:mid], key)
right = self.merge_sort(arr[mid:], key)
return self._merge(left, right, key)

def _merge(self, left, right, key):

result = []
i=j=0
self.merges += 1 # Count each merge call

while i < len(left) and j < len(right):

self.comparisons += 1 # Count comparisons
if key(left[i]) <= key(right[j]):
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
 result.extend(left[i:])
result.extend(right[j:])
return result

# Using the Merge Sort with Custom Objects

# Sample Data
students = [
Student("Alice", 88),
Student("Bob", 72),
Student("Charlie", 95),
Student("Diana", 85),
Student("Evan", 90)
]

# Initialize Sorter
sorter = MergeSortCounter()

# Sort by grade
sorted_students = sorter.merge_sort(students, key=lambda student:
student.grade)

# Output the sorted list and counts

print("Sorted Students:", sorted_students)
print("Total Comparisons:", sorter.comparisons)
print("Total Merges:", sorter.merges)

Output:
Sorted Students: [Bob (72), Diana (85), Alice (88), Evan (90), Charlie
(95)]

Total Comparisons: 7

Total Merges: 4
RESULT:
Thus the program was executed successfully and the output was
verified.
Exp No : 5 Implement sorting algorithms in Date :
Python Bubble Sort, Selection Sort

AIM:
Implement sorting algorithms in Python Bubble Sort, Selection Sort

ALGORITHM:
1.Start the Program.

2.Bubble Sort repeatedly steps through the list, compares adjacent

items, and swaps them if they’re in the wrong order.

· Worst-case time: O(n²)

· Best-case (sorted list): O(n)

· Stable: Yes

3. Selection Sort divides the list into sorted and unsorted parts. It
repeatedly selects the smallest (or largest) from the unsorted part and
moves it to the sorted part.

· Time complexity: O(n²)

· Stable: No (unless implemented carefully)

· Fewer swaps than Bubble Sort

CODING:
# Bubble Sort

def bubble_sort(arr):

n = len(arr)

comparisons = 0

swaps = 0

arr = arr[:] # Make a copy to avoid modifying original

for i in range(n):

for j in range(0, n - i - 1):

comparisons += 1

if arr[j] > arr[j + 1]:

# Swap

arr[j], arr[j + 1] = arr[j + 1], arr[j]

swaps += 1

return arr, comparisons, swaps

# Selection Sort

def selection_sort(arr):

n = len(arr)

comparisons = 0

swaps = 0

arr = arr[:] # Make a copy to avoid modifying original

for i in range(n):

min_idx = i

for j in range(i + 1, n):

comparisons += 1

if arr[j] < arr[min_idx]:

min_idx = j

if min_idx != i:

arr[i], arr[min_idx] = arr[min_idx], arr[i]

swaps += 1

return arr, comparisons, swaps

sample = [64, 25, 12, 22, 11]

sorted_bubble, comp_bubble, swap_bubble =

bubble_sort(sample)

print("Bubble Sort Result:", sorted_bubble)

print("Comparisons:", comp_bubble, "Swaps:", swap_bubble)

sorted_selection, comp_selection, swap_selection =

selection_sort(sample)

print("Selection Sort Result:", sorted_selection)

print("Comparisons:", comp_selection, "Swaps:",

swap_selection)
OUTPUT:
Bubble Sort Result: [11, 12, 22, 25, 64]

Comparisons: 10

Swaps: 5

Selection Sort Result: [11, 12, 22, 25, 64]

Comparisons: 10

Swaps: 4
RESULT:
Thus the program was executed successfully and the output was
verified.
Exp No: 6 Date :
Implement Linear Search, Binary Search, Hash
Table with Collision Handling

Aim:
Implement Linear Search, Binary Search, Hash Table with
Collision Handling

Algorithm:
1.Start the program.

2.Linear Search:

Traverse the list from the beginning.

Compare each element with the target value.

If found, return the index.

If not found by the end, return -1.

3. Initialize low = 0, high = len(arr) - 1.

While low <= high:

● Compute mid = (low + high) // 2.

● If arr[mid] == target, return mid.
● If arr[mid] < target, search right half: low = mid + 1.
● Else, search left half: high = mid - 1.

If not found, return -1.

4. Hash Table with Collision Handling

Use a hash function to convert a key to an index.

 If the index is empty, insert the key-value pair.

If not, append to the list at that index (chaining).

For search/delete, traverse the chain at the hashed index.

Program:
# Linear Search

def linear_search(arr, target):

for i in range(len(arr)):

if arr[i] == target:

return i # Element found

return -1 # Element not found

# Binary Search (array must be sorted)

def binary_search(arr, target):

low = 0

high = len(arr) - 1

while low <= high:

mid = (low + high) // 2

if arr[mid] == target:

return mid # Element found

elif arr[mid] < target:

 low = mid + 1

else:

high = mid - 1

return -1 # Element not found

# Hash Table with Collision Handling (Chaining)

class HashTable:

def __init__(self, size):

self.size = size

self.table = [[] for _ in range(size)] # List of lists for chaining

def _hash_function(self, key):

return hash(key) % self.size

def insert(self, key, value):

index = self._hash_function(key)

# Update if key exists

for pair in self.table[index]:

if pair[0] == key:

pair[1] = value

return

# Else insert new key-value pair

 self.table[index].append([key, value])

def search(self, key):

index = self._hash_function(key)

for pair in self.table[index]:

if pair[0] == key:

return pair[1]

return None # Not found

def delete(self, key):

index = self._hash_function(key)

for i, pair in enumerate(self.table[index]):

if pair[0] == key:

del self.table[index][i]

return True

return False # Not found

def display(self):

for i, bucket in enumerate(self.table):

print(f"Index {i}: {bucket}")

# Linear Search Test

arr = [10, 20, 30, 40, 50]

print("Linear Search for 30:", linear_search(arr, 30)) # Output: 2

# Binary Search Test (sorted list)

arr_sorted = [5, 10, 15, 20, 25]

print("Binary Search for 15:", binary_search(arr_sorted, 15)) # Output: 2

# Hash Table Test

ht = HashTable(10)

ht.insert("apple", 100)

ht.insert("banana", 200)

ht.insert("grape", 300)

print("Search 'banana':", ht.search("banana")) # Output: 200

ht.delete("banana")

print("Search 'banana' after deletion:", ht.search("banana")) # Output:

None

ht.display()
Output:
Linear Search Output:

Element 8 found at index: 4

Binary Search Output:

Element 10 found at index: 3

Hash Table Contents:

Index 0: []

Index 1: []

Index 2: [['banana', 200]]

Index 3: [['apple', 100], ['elppa', 300]]

Index 4: [['grape', 150]]

Hash Table Search Output:

Value for 'banana': 200

Value for 'grape': 150

Deleting 'apple'...

Hash Table Contents:

Index 0: []

Index 1: []

Index 2: [['banana', 200]]

Index 3: [['elppa', 300]]

Index 4: [['grape', 150]]

RESULT:
Thus the program was executed successfully and the output was
verified.
Exp No: 7 Date:
lement binary tree ADT

Aim:
To implement a Binary Tree Abstract Data Type (ADT)

Algorithm:
1. Start
2. Define a Node class with attributes:
○ data → to store node value
○ left → pointer to left child
○ right → pointer to right child
3. Define a BinaryTree class with methods:
○ is_empty() → check if the tree is empty
○ size() → recursively count the total number of nodes
○ height() → recursively calculate the maximum depth of the
tree
○ inorder() → traverse the tree in Left → Root → Right order
○ preorder() → traverse the tree in Root → Left → Right order
○ postorder() → traverse the tree in Left → Right → Root order
○ level_order() → traverse the tree level by level using a queue\

4. Manually construct the binary tree by creating nodes and linking

left and right children.
Example tree:
 A

/\

B C

/ /\

D E F

5. Call traversal methods and display the traversal outputs.

6. Compute and display tree properties:

○ Size (total number of nodes)
○ Height (maximum depth of the tree)
7. Stop the Program.

Program:
from collections import deque

# Node definition

class Node:

def __init__(self, data):

self.data = data

self.left = None

self.right = None

# Binary Tree ADT

class BinaryTree:

def __init__(self, root=None):

self.root = root
def is_empty(self):

return self.root is None

def size(self):

def _size(node):

if node is None:

return 0

return 1 + _size(node.left) + _size(node.right)

return _size(self.root)

def height(self):

def _height(node):

if node is None:

return 0

return 1 + max(_height(node.left), _height(node.right))

return _height(self.root)

# Inorder Traversal

def inorder(self):

result = []

def _inorder(node):

if node:
 _inorder(node.left)

result.append(node.data)

_inorder(node.right)

_inorder(self.root)

return result

# Preorder Traversal

def preorder(self):

result = []

def _preorder(node):

if node:

result.append(node.data)

_preorder(node.left)

_preorder(node.right)

_preorder(self.root)

return result

# Postorder Traversal

def postorder(self):

result = []
def _postorder(node):

if node:

_postorder(node.left)

_postorder(node.right)

result.append(node.data)

_postorder(self.root)

return result

# Level-order (Breadth-first) Traversal

def level_order(self):

result = []

if not self.root:

return result

queue = deque([self.root])

while queue:

node = queue.popleft()

result.append(node.data)

if node.left:

queue.append(node.left)

if node.right:

queue.append(node.right)

return result
# ----------------- Demo -----------------

if __name__ == "__main__":

# Constructing tree manually

# A

# /\

# B C

# / /\

# D E F

root = Node('A')

root.left = Node('B')

root.right = Node('C')

root.left.left = Node('D')

root.right.left = Node('E')

root.right.right = Node('F')

tree = BinaryTree(root)

print("Inorder Traversal :", tree.inorder())

print("Preorder Traversal :", tree.preorder())

print("Postorder Traversal :", tree.postorder())

print("Level-order Traversal:", tree.level_order())

print("Size of Tree:", tree.size())

print("Height of Tree:", tree.height())

Output :
Inorder Traversal : ['D', 'B', 'A', 'E', 'C', 'F']

Preorder Traversal : ['A', 'B', 'D', 'C', 'E', 'F']

Postorder Traversal : ['D', 'B', 'E', 'F', 'C', 'A']

Level-order Traversal: ['A', 'B', 'C', 'D', 'E', 'F']

Size of Tree: 6

Height of Tree: 3
Result:
Thus the program was executed successfully and the output was
verified.
Exp No: 8 Date:
implement an AVL tree class with
rotations (LL,RR,LR,RL)

Aim:
To implement an AVL Tree that maintains a balanced binary
search tree through automatic rotations (LL, RR, LR, RL).

Algorithm:
1. Start with the root node of the AVL tree.
2. Perform standard BST insertion:
o If the tree is empty, create a new node and return it.
o If the key < root’s key, insert into the left subtree.
o If the key > root’s key, insert into the right subtree.
3. Update the height of the current node:

height=1+max(height of left child,height of right child)

4.Calculate the balance factor of the current node:

balance factor=height(left subtree)−height(right subtree

5.Check for imbalance and apply the appropriate rotation:

· LL Case (Left-Left): balance factor > 1 and key < left child → Right
rotate.

· RR Case (Right-Right): balance factor < -1 and key > right child →
Left rotate.
 · LR Case (Left-Right): balance factor > 1 and key > left child → Left
rotate left child, then right rotate root.

· RL Case (Right-Left): balance factor < -1 and key < right child →
Right rotate right child, then left rotate root.

6.Return the root node after rotation.

7.Stop the program.

Program:
class Node:

def __init__(self, key):

self.key = key

self.left = None

self.right = None

self.height = 1 # height of node

class AVLTree:

# Get height of a node

def get_height(self, node):

if not node:

return 0

return node.heigh
# Get balance factor

def get_balance(self, node):

if not node:

return 0

return self.get_height(node.left) - self.get_height(node.right)

# Right rotate (LL Rotation)

def right_rotate(self, y):

x = y.left

T2 = x.right

# Perform rotation

x.right = y

y.left = T2

# Update heights

y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))

x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))

return x

# Left rotate (RR Rotation)

def left_rotate(self, x):

y = x.right

T2 = y.left
 # Perform rotation

y.left = x

x.right = T2

# Update heights

x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))

y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))

return y

# Insert function

def insert(self, root, key):

# Step 1: Perform normal BST insertion

if not root:

return Node(key)

elif key < root.key:

root.left = self.insert(root.left, key)

else:

root.right = self.insert(root.right, key)

# Step 2: Update height

root.height = 1 + max(self.get_height(root.left),
self.get_height(root.right))
# Step 3: Get balance factor

balance = self.get_balance(root)

# Step 4: Balance the tree

# Case 1 - Left Left

if balance > 1 and key < root.left.key:

return self.right_rotate(root)

# Case 2 - Right Right

if balance < -1 and key > root.right.key:

return self.left_rotate(root)

# Case 3 - Left Right

if balance > 1 and key > root.left.key:

root.left = self.left_rotate(root.left)

return self.right_rotate(root)

# Case 4 - Right Left

if balance < -1 and key < root.right.key:

root.right = self.right_rotate(root.right)

return self.left_rotate(root)

return root
 # Preorder traversal

def preorder(self, root):

if not root:

return

print(f"{root.key}", end=" ")

self.preorder(root.left)

self.preorder(root.right)

# Example usage

if __name__ == "__main__":

avl = AVLTree()

root = None

nums = [10, 20, 30, 40, 50, 25]

for num in nums:

root = avl.insert(root, num)

print("Preorder traversal of AVL tree:")

avl.preorder(root)

Output:
Preorder traversal of AVL tree:

30 20 10 25 40 50
Result:
The AVL Tree successfully inserts nodes while maintaining a

balanced binary search tree.

Exp No: 9 Date:
implement breadth first search(BFS)depth
first search(DFS)

Aim:
To implement Breadth-First Search (BFS) and Depth-First Search
(DFS)

Algorithm Breadth-First Search (BFS)

1. Start with a graph and a starting node.

2. Initialize an empty queue and a set/list for visited nodes.
3. Enqueue the starting node and mark it as visited.
4. While the queue is not empty:
o Dequeue a node from the queue and process it (e.g., print
it).
o For each adjacent neighbor of the node:
§ If the neighbor is not visited, mark it as visited and
enqueue it.
5. Repeat until the queue is empty.
6. Stop the program.

Algorithm: Depth-First Search (DFS)

Recursive Method

1. Start with a graph and a starting node.

2. Initialize an empty set/list for visited nodes.
3. Visit the starting node and mark it as visited.
 4. For each adjacent neighbor of the node:
o If the neighbor is not visited, recursively perform DFS on it.
5. Repeat until all reachable nodes are visited.
6. Stop the Program.

Iterative Method (using stack)

1. Start with a graph and a starting node.

2. Initialize a stack and a set/list for visited nodes.
3. Push the starting node onto the stack.
4. While the stack is not empty:
o Pop a node from the stack and process it.
o For each adjacent neighbor of the node:
§ If the neighbor is not visited, mark it as visited and
push it onto the stack.
5. Repeat until the stack is empty.
6. Stop the Program.
Program:
from collections import deque

# Graph class using adjacency list

class Graph:

def __init__(self):

self.graph = {} # Dictionary to store adjacency list

# Add edge to the graph

def add_edge(self, u, v):

if u not in self.graph:

self.graph[u] = []

if v not in self.graph:

self.graph[v] = []

self.graph[u].append(v)

self.graph[v].append(u) # For undirected graph; remove if directed

# Breadth-First Search (BFS)

def bfs(self, start):

visited = set()

queue = deque([start])

visited.add(start)

print("BFS Traversal:", end=" ")

 while queue:

node = queue.popleft()

print(node, end=" ")

for neighbor in self.graph[node]:

if neighbor not in visited:

visited.add(neighbor)

queue.append(neighbor)

print()

# Depth-First Search (DFS) using recursion

def dfs_util(self, node, visited):

visited.add(node)

print(node, end=" ")

for neighbor in self.graph[node]:

if neighbor not in visited:

self.dfs_util(neighbor, visited)

def dfs(self, start):

visited = set()

print("DFS Traversal:", end=" ")

self.dfs_util(start, visited)

print()
# Example usage

if __name__ == "__main__":

g = Graph()

g.add_edge(0, 1)

g.add_edge(0, 2)

g.add_edge(1, 2)

g.add_edge(1, 3)

g.add_edge(2, 4)

g.add_edge(3, 4)

g.add_edge(4, 5)

g.bfs(0)

g.dfs(0)

Output:
BFS Traversal: 0 1 2 3 4 5

DFS Traversal: 0 1 2 4 3 5
Result:
The Breadth-First Search (BFS) and Depth-First Search (DFS)
successfully implement.
Exp No: 10 Date:
implement dijstra's algorithm for
shortest path (greedy)

Aim:
To implement Dijkstra’s algorithm to find the shortest path from a
source vertex to all other vertices in a weighted graph using a greedy
approach.

Algorithm:

1. Start: Initialize all vertices with distance ∞, except the source

vertex which is set to 0.

2. Visited Set: Create an empty set to keep track of visited

vertices.
3. Select Vertex: Choose the unvisited vertex with the minimum
distance value.
4. Mark Visited: Mark this vertex as visited.
5. Update Distances: For each adjacent vertex, if it is unvisited
and the path through the selected vertex is shorter, update its
distance.
6. Repeat: Repeat steps 3–5 until all vertices are visited.
7. Distance Array: The distance array now contains the shortest
distances from the source to all vertices.
8. End: Output the distance array as the result.
Program:
import sys

def dijkstra(graph, start):

num_vertices = len(graph)

visited = [False] * num_vertices

distance = [sys.maxsize] * num_vertices

distance[start] = 0

for _ in range(num_vertices):

# Pick the unvisited vertex with the smallest distance

min_distance = sys.maxsize

min_index = -1

for v in range(num_vertices):

if not visited[v] and distance[v] < min_distance:

min_distance = distance[v]

min_index = v

u = min_index

visited[u] = True

# Update distances of adjacent vertices

for v in range(num_vertices):

if graph[u][v] > 0 and not visited[v]:

 if distance[u] + graph[u][v] < distance[v]:

distance[v] = distance[u] + graph[u][v]

return distance

# Example usage:

graph = [

[0, 4, 0, 0, 0, 0, 0, 8, 0],

[4, 0, 8, 0, 0, 0, 0, 11, 0],

[0, 8, 0, 7, 0, 4, 0, 0, 2],

[0, 0, 7, 0, 9, 14, 0, 0, 0],

[0, 0, 0, 9, 0, 10, 0, 0, 0],

[0, 0, 4, 14, 10, 0, 2, 0, 0],

[0, 0, 0, 0, 0, 2, 0, 1, 6],

[8, 11, 0, 0, 0, 0, 1, 0, 7],

[0, 0, 2, 0, 0, 0, 6, 7, 0]

start_vertex = 0

distances = dijkstra(graph, start_vertex)

print(f"Shortest distances from vertex {start_vertex}:")

for i, d in enumerate(distances):

print(f"Vertex {i} : {d}")

Output:
Shortest distances from vertex 0:

Vertex 0 : 0

Vertex 1 : 4

Vertex 2 : 12

Vertex 3 : 19

Vertex 4 : 21

Vertex 5 : 11

Vertex 6 : 9

Vertex 7 : 8

Vertex 8 : 14
Result:
The implement of dijstra's algorithm for shortest path (greedy) has
been successfully Verified.