Practical 1
Aim :- Implementation of different searching & sorting techniques.
Searching Algorithm
Code :
import math 
def linear_search(arr, target):
        for i in range(len(arr)):
        if arr[i] == target:
            return i  # Return index where found
    return -1  # Return -1 if not found
def binary_search_iterative(arr, target):
        low, high = 0, len(arr) - 1

    while low <= high:
        mid = (low + high) // 2  # Find the middle index
        if arr[mid] == target:
            return mid  # Element found
        elif arr[mid] < target:
            low = mid + 1  # Search in right half
        else:
            high = mid - 1  # Search in left half
    return -1
def binary_search_recursive(arr, low, high, target):
        if high >= low:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            return binary_search_recursive(arr, low, mid - 1, target)
        else:
            return binary_search_recursive(arr, mid + 1, high, target)
    else:
        return -1  # Element not found

if __name__ == "__main__":
    arr = list(map(int, input("Enter elements of the array (space-separated): ").split()))
    target = int(input("Enter the element to search for: "))

    print("\nOriginal Array:", arr)

    idx_linear = linear_search(arr, target)
    print(f"\nLinear Search → {'Found at index ' + str(idx_linear) if idx_linear != -1 else 'Not Found'}")

    arr_sorted = sorted(arr)
    print("\nSorted Array (for Binary & Jump Search):", arr_sorted)

    idx_bin_iter = binary_search_iterative(arr_sorted, target)
    print(f"Binary Search (Iterative) → {'Found at index ' + str(idx_bin_iter) if idx_bin_iter != -1 else 'Not Found'}")

    idx_bin_rec = binary_search_recursive(arr_sorted, 0, len(arr_sorted) - 1, target)
    print(f"Binary Search (Recursive) → {'Found at index ' + str(idx_bin_rec) if idx_bin_rec != -1 else 'Not Found'}")

Output : 

 




Sorting Algorithm
Code :- 
1. Bubble Sort
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # Last i elements are already sorted
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

 2. Selection Sort
def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr
3. Insertion Sort
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # Move elements greater than key to one position ahead
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

 4. 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
        # Merge the two halves
        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
        # Check for any remaining elements
        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
    return arr






5. Quick Sort
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[len(arr) // 2]
        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]
        return quick_sort(left) + middle + quick_sort(right)


 6. 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)
    # Build max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # Extract elements from heap
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # swap
        heapify(arr, i, 0)
    return arr
# -------------------------------
# Test Sorting Algorithms
# -------------------------------
if __name__ == "__main__":
    arr = [64, 25, 12, 22, 11]
    print("Original Array:", arr)
    print("\nBubble Sort:", bubble_sort(arr.copy()))
    print("Selection Sort:", selection_sort(arr.copy()))
    print("Insertion Sort:", insertion_sort(arr.copy()))
    print("Merge Sort:", merge_sort(arr.copy()))
    print("Quick Sort:", quick_sort(arr.copy()))
    print("Heap Sort:", heap_sort(arr.copy()))
Output : 
 














Practical 2
Aim : Perform various hashing techniques with Linear Probe as collision resolution 

Code :
# Hash Table Implementation using Linear Probing
class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size  # initialize empty hash table

    # Simple hash function
    def hash_function(self, key):
        return key % self.size

    # Insert a key into hash table
    def insert(self, key):
        index = self.hash_function(key)

        # If collision occurs, perform linear probing
        start_index = index  # To detect if we have looped around
        while self.table[index] is not None:
            if self.table[index] == key:
                print(f"Key {key} already exists at index {index}.")
                return
            index = (index + 1) % self.size
            if index == start_index:  # Table is full
                print("Hash table is full. Cannot insert more keys.")
                return

        self.table[index] = key
        print(f"Key {key} inserted at index {index}.")

    # Search for a key in the hash table
    def search(self, key):
        index = self.hash_function(key)
        start_index = index

        while self.table[index] is not None:
            if self.table[index] == key:
                print(f"Key {key} found at index {index}.")
                return index
            index = (index + 1) % self.size
            if index == start_index:  # back to start
                break
        print(f"Key {key} not found in the table.")
        return -1

    # Display the hash table
    def display(self):
        print("\nHash Table:")
        for i in range(self.size):
            print(f"Index {i}: {self.table[i]}")
        print("-" * 30)



# ------------------------------
# Main Program
# ------------------------------
if __name__ == "__main__":
    size = int(input("Enter size of hash table: "))
    ht = HashTable(size)

    while True:
        print("\nMENU:")
        print("1. Insert")
        print("2. Search")
        print("3. Display")
        print("4. Exit")

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

        if choice == 1:
            key = int(input("Enter key to insert: "))
            ht.insert(key)
        elif choice == 2:
            key = int(input("Enter key to search: "))
            ht.search(key)
        elif choice == 3:
            ht.display()
        elif choice == 4:
            print("Exiting program...")
            break
        else:
            print("Invalid choice! Please try again.")

Output : 
  



Practical 3 
Aim : Implementation of Stacks,Ordinary Queue & Circular queue (Using arrays) 
Stack
Code : 
# Stack implementation using arrays (lists)
class Stack:
    def __init__(self, size):
        self.size = size        # Maximum size of stack
        self.stack = []         # Initialize an empty list to store stack elements

    # Check if stack is empty
    def isEmpty(self):
        return len(self.stack) == 0

    # Check if stack is full
    def isFull(self):
        return len(self.stack) == self.size

    # Push operation
    def push(self, item):
        if self.isFull():
            print("Stack Overflow! Cannot push", item)
        else:
            self.stack.append(item)
            print(f"Pushed {item} into the stack.")

    # Pop operation
    def pop(self):
        if self.isEmpty():
            print("Stack Underflow! Stack is empty.")
        else:
            removed = self.stack.pop()
            print(f"Popped element: {removed}")

    # Peek operation (view top element)
    def peek(self):
        if self.isEmpty():
            print("Stack is empty. Nothing to peek.")
        else:
            print("Top element is:", self.stack[-1])

    # Display the entire stack
    def display(self):
        if self.isEmpty():
            print("Stack is empty.")
        else:
            print("Stack elements (top → bottom):")
            for i in reversed(self.stack):
                print(i)

# -----------------------------
# Main Program (User Interaction)
# -----------------------------
if __name__ == "__main__":
    size = int(input("Enter the size of the stack: "))
    s = Stack(size)

    while True:
        print("\n----- STACK MENU -----")
        print("1. Push element")
        print("2. Pop element")
        print("3. Peek top element")
        print("4. Display stack")
        print("5. Exit")

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

        if choice == 1:
            element = input("Enter element to push: ")
            s.push(element)
        elif choice == 2:
            s.pop()
        elif choice == 3:
            s.peek()
        elif choice == 4:
            s.display()
        elif choice == 5:
            print("Exiting program...")
            break
        else:
            print("Invalid choice! Please try again.")
Output : 

   


 
Queue
Code : 
# Stack implementation using arrays (lists)
class Stack:
    def __init__(self, size):
        self.size = size        # Maximum size of stack
        self.stack = []         # Initialize an empty list to store stack elements

    # Check if stack is empty
    def isEmpty(self):
        return len(self.stack) == 0

    # Check if stack is full
    def isFull(self):
        return len(self.stack) == self.size

    # Push operation
    def push(self, item):
        if self.isFull():
            print("Stack Overflow! Cannot push", item)
        else:
            self.stack.append(item)
            print(f"Pushed {item} into the stack.")

    # Pop operation
    def pop(self):
        if self.isEmpty():
            print("Stack Underflow! Stack is empty.")
        else:
            removed = self.stack.pop()
            print(f"Popped element: {removed}")

    # Peek operation (view top element)
    def peek(self):
        if self.isEmpty():
            print("Stack is empty. Nothing to peek.")
        else:
            print("Top element is:", self.stack[-1])

    # Display the entire stack
    def display(self):
        if self.isEmpty():
            print("Stack is empty.")
        else:
            print("Stack elements (top → bottom):")
            for i in reversed(self.stack):
                print(i)

# -----------------------------
# Main Program (User Interaction)
# -----------------------------
if __name__ == "__main__":
    size = int(input("Enter the size of the stack: "))
    s = Stack(size)

    while True:
        print("\n----- STACK MENU -----")
        print("1. Push element")
        print("2. Pop element")
        print("3. Peek top element")
        print("4. Display stack")
        print("5. Exit")

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

        if choice == 1:
            element = input("Enter element to push: ")
            s.push(element)
        elif choice == 2:
            s.pop()
        elif choice == 3:
            s.peek()
        elif choice == 4:
            s.display()
        elif choice == 5:
            print("Exiting program...")
            break
        else:
            print("Invalid choice! Please try again.")



Output :
  
 





Circular Queue
Code : 
class CircularQueue:
    def __init__(self, size):
        self.size = size                  # Maximum size of the queue
        self.queue = [None] * size        # Initialize the queue with None
        self.front = -1                   # Points to the first element
        self.rear = -1                    # Points to the last element

    def isFull(self):
        return (self.rear + 1) % self.size == self.front
    def isEmpty(self):
        return self.front == -1
    def enqueue(self, value):
        if self.isFull():
            print("Queue is Full! Cannot enqueue", value)
            return
               if self.isEmpty():
            self.front = 0
        self.rear = (self.rear + 1) % self.size
        self.queue[self.rear] = value
        print(f"Enqueued: {value}")
    def dequeue(self):
        if self.isEmpty():
            print("Queue is Empty! Cannot dequeue.")
            return None
                value = self.queue[self.front]
        if self.front == self.rear:  # Queue becomes empty after dequeue
            self.front = self.rear = -1
        else:
            self.front = (self.front + 1) % self.size
        print(f"Dequeued: {value}")
        return value

    def peek(self):
        if self.isEmpty():
            print("Queue is Empty! Nothing to peek.")
            return None
        print(f"Front element: {self.queue[self.front]}")
        return self.queue[self.front]
    def display(self):
        if self.isEmpty():
            print("Queue is Empty!")
            return
        print("Queue elements:", end=" ")
        if self.rear >= self.front:
            for i in range(self.front, self.rear + 1):
                print(self.queue[i], end=" ")
        else:
            for i in range(self.front, self.size):
                print(self.queue[i], end=" ")
            for i in range(0, self.rear + 1):
                print(self.queue[i], end=" ")
        print()
# ------------------- User Interaction -------------------
def main():
    size = int(input("Enter the size of the Circular Queue: "))
    cq = CircularQueue(size)

    while True:
        print("\n--- Circular Queue Operations ---")
        print("1. Enqueue")
        print("2. Dequeue")
        print("3. Peek")
        print("4. Display Queue")
        print("5. Exit")
        choice = input("Enter your choice (1-5): ")
        if choice == '1':
            value = input("Enter value to enqueue: ")
            cq.enqueue(value)
        elif choice == '2':
            cq.dequeue()
        elif choice == '3':
            cq.peek()
        elif choice == '4':
            cq.display()
        elif choice == '5':
            print("Exiting program...")
            break
        else:
            print("Invalid choice! Please enter 1-5.")
if __name__ == "__main__":
    main()

Output : 
 

 



Practical 4 
Aim : Implementation of Stack Applications like: 
o	infix to postfix 
o	Postfix evaluation 
o	Balancing of Parenthesis 
Code :
# -------------------- STACK APPLICATIONS --------------------
def precedence(op):
    if op == '^':
        return 3
    if op in ('*', '/'):
        return 2
    if op in ('+', '-'):
        return 1
    return 0
# --------- Infix to Postfix ---------
def infix_to_postfix(expression):
    stack = []
    postfix = ""
    for ch in expression:
        if ch.isalnum():     # Operand
            postfix += ch
        elif ch == '(':
            stack.append(ch)
        elif ch == ')':
            while stack and stack[-1] != '(':
                postfix += stack.pop()
            stack.pop()      # Remove '('
        else:                # Operator
            while stack and precedence(stack[-1]) >= precedence(ch):
                postfix += stack.pop()
            stack.append(ch)
    while stack:
        postfix += stack.pop()

    return postfix
# --------- Postfix Evaluation ---------
def apply_operator(a, b, op):
    if op == '+': return a + b
    if op == '-': return a - b
    if op == '*': return a * b
    if op == '/': return a // b  # Integer division
def evaluate_postfix(postfix):
    stack = []
    for ch in postfix:
        if ch.isdigit():
            stack.append(int(ch))
        else:
            b = stack.pop()
            a = stack.pop()
            stack.append(apply_operator(a, b, ch))
    return stack.pop()
# --------- Balanced Parenthesis ---------
def is_balanced(expression):
    stack = []
    match = {')': '(', '}': '{', ']': '['}
    for ch in expression:
        if ch in "({[":
            stack.append(ch)
        elif ch in ")}]":
            if not stack or stack[-1] != match[ch]:
                return False
            stack.pop()
    return len(stack) == 0
# -------------------- MENU --------------------
def main():
    while True:
        print("\n==== STACK APPLICATIONS MENU ====")
        print("1. Infix to Postfix")
        print("2. Postfix Evaluation")
        print("3. Parenthesis Balancing")
        print("4. Exit")
        choice = input("Enter your choice (1-4): ")
        if choice == '1':
            exp = input("Enter infix expression: ")
            print("Postfix Expression:", infix_to_postfix(exp))
        elif choice == '2':
            exp = input("Enter postfix expression: ")
            print("Evaluation Result:", evaluate_postfix(exp))
        elif choice == '3':
            exp = input("Enter expression: ")
            print("Balanced" if is_balanced(exp) else "Not Balanced")
        elif choice == '4':
            print("Exiting program...")
            break
        else:
            print("Invalid Input! Please try again.")
# Run the program
main()
Output 
 
Practical 5 
Aim : Implementation of all types of linked lists.

1 . Singly Linked List

Code :
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def insert(self, data):
        new = Node(data)
        new.next = self.head
        self.head = new

    def display(self):
        temp = self.head
        result = []
        while temp:
            result.append(str(temp.data))
            temp = temp.next
        return " -> ".join(result) + " -> None"

s = SinglyLinkedList()
s.insert(10); s.insert(20); s.insert(30)
print(s.display())

Output:
 







2 . Doubly Linked List

Code :
class DNode:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def insert(self, data):
        new = DNode(data)
        new.next = self.head
        if self.head:
            self.head.prev = new
        self.head = new

    def display(self):
        temp = self.head
        result = []
        while temp:
            result.append(str(temp.data))
            temp = temp.next
        return " <-> ".join(result) + " <-> None"

d = DoublyLinkedList()
d.insert(1); d.insert(2); d.insert(3)
print(d.display())

Output :
 











3. Circular Singly Linked List
Code : 
class CSNode:
    def __init__(self, data):
        self.data = data
        self.next = None

class CircularSinglyLinkedList:
    def __init__(self):
        self.head = None

    def insert(self, data):
        new = CSNode(data)
        if not self.head:
            self.head = new
            new.next = self.head
        else:
            temp = self.head
            while temp.next != self.head:
                temp = temp.next
            temp.next = new
            new.next = self.head

    def display(self):
        if not self.head:
            return "Empty"
        temp = self.head
        result = []
        while True:
            result.append(str(temp.data))
            temp = temp.next
            if temp == self.head:
                break
        return " -> ".join(result) + " -> (back to head)"

c = CircularSinglyLinkedList()
c.insert(5); c.insert(10); c.insert(15)
print(c.display())

Output :

 

4. Circular Doubly Linked List
Code : 
class CDNode:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class CircularDoublyLinkedList:
    def __init__(self):
        self.head = None

    def insert(self, data):
        new = CDNode(data)
        if not self.head:
            self.head = new
            new.next = new
            new.prev = new
        else:
            tail = self.head.prev
            tail.next = new
            new.prev = tail
            new.next = self.head
            self.head.prev = new

    def display(self):
        if not self.head:
            print("Empty")
            return
        temp = self.head
        while True:
            print(temp.data, end=" <-> ")
            temp = temp.next
            if temp == self.head:
                break
        print("(back to head)")


cd = CircularDoublyLinkedList()
cd.insert(10)
cd.insert(20)
cd.insert(30)
cd.display()
Output 

 
















Practical 6 
Aim : Demonstrate application of linked list (eg.Sparsematrix, Stack, Queue , Priority & Double ended Queue) 

A.	Sparse Matrix
Code :

# ---------------- SPARSE MATRIX IMPLEMENTATION ---------------- #

def create_sparse(matrix):
    """Convert normal matrix to sparse matrix (3-tuple form)."""
    sparse = []
    rows = len(matrix)
    cols = len(matrix[0])

    # First row = (rows, cols, total_nonzero)
    count = 0
    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] != 0:
                sparse.append([i, j, matrix[i][j]])
                count += 1

    return [[rows, cols, count]] + sparse

def display_sparse(sparse):
    print("\nSparse Matrix (Row  Column  Value):")
    for row in sparse:
        print(row)

def sparse_add(sm1, sm2):
    """Add two sparse matrices."""

    if sm1[0][0] != sm2[0][0] or sm1[0][1] != sm2[0][1]:
        print("Matrices cannot be added (dimension mismatch).")
        return

    result = [[sm1[0][0], sm1[0][1], 0]]
    i = j = 1

    while i <= sm1[0][2] and j <= sm2[0][2]:
        if sm1[i][:2] == sm2[j][:2]:
            # same position
            value = sm1[i][2] + sm2[j][2]
            if value != 0:
                result.append([sm1[i][0], sm1[i][1], value])
                result[0][2] += 1
            i += 1
            j += 1

        elif sm1[i][0] < sm2[j][0] or (sm1[i][0] == sm2[j][0] and sm1[i][1] < sm2[j][1]):
            result.append(sm1[i])
            result[0][2] += 1
            i += 1
        else:
            result.append(sm2[j])
            result[0][2] += 1
            j += 1
    # Remaining entries
    while i <= sm1[0][2]:
        result.append(sm1[i])
        result[0][2] += 1
        i += 1

    while j <= sm2[0][2]:
        result.append(sm2[j])
        result[0][2] += 1
        j += 1

    return result

def fast_transpose(sparse):
    """Fast transpose of sparse matrix."""
    rows, cols, num = sparse[0]

    result = [[cols, rows, num]] + [[0, 0, 0]] * num
    count = [0] * cols

    # count elements in each column
    for i in range(1, num + 1):
        count[sparse[i][1]] += 1

    # starting position of each column
    index = [1] * cols
    for i in range(1, cols):
        index[i] = index[i - 1] + count[i - 1]

    # place elements in transposed form
    for i in range(1, num + 1):
        col = sparse[i][1]
        pos = index[col]
        result[pos] = [sparse[i][1], sparse[i][0], sparse[i][2]]
        index[col] += 1

    return result

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

def main():
    print("Enter matrix dimensions:")
    r = int(input("Rows: "))
    c = int(input("Cols: "))

    print("Enter matrix elements:")
    matrix = []
    for i in range(r):
        row = list(map(int, input().split()))
        matrix.append(row)
    sparse = create_sparse(matrix)
    display_sparse(sparse)

    print("\nFast Transpose:")
    trans = fast_transpose(sparse)
    display_sparse(trans)

main()
Output : 
 

















B.	Stack , Queue,Priority Queue , Double Ended 
Code : 
# ===================== STACK IMPLEMENTATION =====================

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if self.is_empty():
            return "Stack Underflow!"
        return self.items.pop()

    def peek(self):
        if self.is_empty():
            return "Stack is Empty!"
        return self.items[-1]

    def is_empty(self):
        return len(self.items) == 0

    def display(self):
        print("Stack:", self.items)


# ===================== QUEUE IMPLEMENTATION =====================

class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if self.is_empty():
            return "Queue Underflow!"
        return self.items.pop(0)

    def is_empty(self):
        return len(self.items) == 0

    def display(self):
        print("Queue:", self.items)


# ===================== PRIORITY QUEUE IMPLEMENTATION =====================

class PriorityQueue:
    def __init__(self):
        self.items = []

    def insert(self, item, priority):
        self.items.append((priority, item))
        self.items.sort()  # smallest priority first

    def delete(self):
        if self.is_empty():
            return "Priority Queue Underflow!"
        return self.items.pop(0)  # remove smallest priority

    def is_empty(self):
        return len(self.items) == 0

    def display(self):
        print("Priority Queue:", self.items)


# ===================== DOUBLE ENDED QUEUE (DEQUE) =====================

class Deque:
    def __init__(self):
        self.items = []

    def add_front(self, item):
        self.items.insert(0, item)

    def add_rear(self, item):
        self.items.append(item)

    def remove_front(self):
        if self.is_empty():
            return "Deque Underflow!"
        return self.items.pop(0)

    def remove_rear(self):
        if self.is_empty():
            return "Deque Underflow!"
        return self.items.pop()

    def is_empty(self):
        return len(self.items) == 0

    def display(self):
        print("Deque:", self.items)


# ===================== TEST CODE =====================

if __name__ == "__main__":

    print("\n=== STACK TEST ===")
    s = Stack()
    s.push(10)
    s.push(20)
    s.push(30)
    s.display()
    print("Popped:", s.pop())
    s.display()

    print("\n=== QUEUE TEST ===")
    q = Queue()
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    q.display()
    print("Dequeued:", q.dequeue())
    q.display()

    print("\n=== PRIORITY QUEUE TEST ===")
    pq = PriorityQueue()
    pq.insert("A", 3)
    pq.insert("B", 1)
    pq.insert("C", 2)
    pq.display()
    print("Deleted:", pq.delete())
    pq.display()

    print("\n=== DEQUE TEST ===")
    dq = Deque()
    dq.add_front(10)
    dq.add_rear(20)
    dq.add_front(5)
    dq.display()
    print("Removed Front:", dq.remove_front())
    print("Removed Rear:", dq.remove_rear())
    dq.display()

Output :

 





Practical 7
Aim : Create and perform various operations on BST. 

Code :

# ================== NODE DEFINITION ==================

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

# ================== BST IMPLEMENTATION ==================

class BST:
    def __init__(self):
        self.root = None

    # ------- INSERT NODE -------
    def insert(self, root, key):
        if root is None:
            return Node(key)

        if key < root.key:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)

        return root

    def insert_key(self, key):
        self.root = self.insert(self.root, key)

    # ------- SEARCH NODE -------
    def search(self, root, key):
        if root is None or root.key == key:
            return root

        if key < root.key:
            return self.search(root.left, key)
        else:
            return self.search(root.right, key)

    # ------- FIND MINIMUM -------
    def find_min(self, root):
        while root.left:
            root = root.left
        return root

    # ------- DELETE NODE -------
    def delete(self, root, key):
        if root is None:
            return None

        if key < root.key:
            root.left = self.delete(root.left, key)
        elif key > root.key:
            root.right = self.delete(root.right, key)
        else:
            # Case 1: No Child
            if root.left is None and root.right is None:
                return None

            # Case 2: One Child
            if root.left is None:
                return root.right
            if root.right is None:
                return root.left

            # Case 3: Two Children → Replace with inorder successor
            successor = self.find_min(root.right)
            root.key = successor.key
            root.right = self.delete(root.right, successor.key)

        return root

    def delete_key(self, key):
        self.root = self.delete(self.root, key)

    # ------- TRAVERSALS -------
    def inorder(self, root):
        if root:
            self.inorder(root.left)
            print(root.key, end=" ")
            self.inorder(root.right)

    def preorder(self, root):
        if root:
            print(root.key, end=" ")
            self.preorder(root.left)
            self.preorder(root.right)

    def postorder(self, root):
        if root:
            self.postorder(root.left)
            self.postorder(root.right)
            print(root.key, end=" ")

# ================== TEST CODE ==================

if __name__ == "__main__":
    bst = BST()

    print("Inserting: 50, 30, 70, 20, 40, 60, 80")
    for i in [50, 30, 70, 20, 40, 60, 80]:
        bst.insert_key(i)

    print("\nInorder Traversal  :", end=" ")
    bst.inorder(bst.root)

    print("\nPreorder Traversal :", end=" ")
    bst.preorder(bst.root)

    print("\nPostorder Traversal:", end=" ")
    bst.postorder(bst.root)

    # Search
    key = 40
    print(f"\n\nSearching for {key}:",
          "Found" if bst.search(bst.root, key) else "Not Found")

    # Delete node
    print("\nDeleting 70...")
    bst.delete_key(70)
    print("Inorder after deletion:", end=" ")
    bst.inorder(bst.root)

    print("\nMinimum Value in BST:", bst.find_min(bst.root).key)

Output :

 




























Practical 8
Aim : Implementing Heap with different operations. 

Code :
# ===================== MIN HEAP IMPLEMENTATION =====================
class MinHeap:
    def __init__(self):
        self.heap = []
    # ---------------- INSERT ELEMENT ----------------
    def insert(self, value):
        self.heap.append(value)
        self._percolate_up(len(self.heap) - 1)

    def _percolate_up(self, index):
        parent = (index - 1) // 2

        while index > 0 and self.heap[index] < self.heap[parent]:
            self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
            index = parent
            parent = (index - 1) // 2
    # ---------------- GET MINIMUM ----------------
    def get_min(self):
        if not self.heap:
            return "Heap is empty!"
        return self.heap[0]
    # ---------------- DELETE MINIMUM ----------------
    def extract_min(self):
        if not self.heap:
            return "Heap is empty!"

        root = self.heap[0]
        last = self.heap.pop()

        if self.heap:
            self.heap[0] = last
            self._heapify(0)

        return root
    # ---------------- HEAPIFY FUNCTION ----------------
    def _heapify(self, i):
        size = len(self.heap)
        smallest = i
        left = 2 * i + 1
        right = 2 * i + 2

        # choose smallest among root, left, right
        if left < size and self.heap[left] < self.heap[smallest]:
            smallest = left
        if right < size and self.heap[right] < self.heap[smallest]:
            smallest = right

        # if root is not smallest, swap and continue heapify
        if smallest != i:
            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            self._heapify(smallest)

    # ---------------- BUILD HEAP FROM LIST ----------------
    def build_heap(self, arr):
        self.heap = arr[:]
        # start heapify from middle index
        for i in range(len(self.heap)//2 - 1, -1, -1):
            self._heapify(i)

    # ---------------- DISPLAY ----------------
    def display(self):
        print("Heap:", self.heap)

# ===================== TEST CODE =====================

if __name__ == "__main__":
    h = MinHeap()

    print("Inserting values: 40, 20, 30, 35, 25, 80, 32")
    for val in [40, 20, 30, 35, 25, 80, 32]:
        h.insert(val)
        h.display()

    print("\nMinimum value:", h.get_min())

    print("\nExtracting minimum...")
    print("Extracted:", h.extract_min())
    h.display()

    print("\nBuilding heap from array [9, 4, 7, 1, -2, 6, 5]")
    h.build_heap([9, 4, 7, 1, -2, 6, 5])
    h.display()

    print("\nExtracting min:", h.extract_min())
    h.display()

Output :

 


Practical 9
Aim : Create a Graph storage structure (eg. Adjacency matrix) 
Code :

# ===================== GRAPH USING ADJACENCY MATRIX =====================

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        # create V x V matrix initialized to 0
        self.adj_matrix = [[0] * vertices for _ in range(vertices)]

    # -------- ADD EDGE --------
    def add_edge(self, u, v, directed=False):
        self.adj_matrix[u][v] = 1
        if not directed:          # If undirected, add both ways
            self.adj_matrix[v][u] = 1
    # -------- DISPLAY MATRIX --------
    def display(self):
        print("\nAdjacency Matrix:")
        for row in self.adj_matrix:
            print(row)
# ===================== TEST CODE =====================
if __name__ == "__main__":
    n = int(input("Enter number of vertices: "))
    g = Graph(n)

    edges = int(input("Enter number of edges: "))

    for _ in range(edges):
        print("\nEnter edge (u v): ", end="")
        u, v = map(int, input().split())
        g.add_edge(u, v)   # undirected graph

    g.display()

Output : 

 

Practical 10
Aim : Implementation of Graph traversal. (DFS and BFS) 
Code :

# ===================== GRAPH IMPLEMENTATION =====================

from collections import deque

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = {i: [] for i in range(vertices)}   # adjacency list

    # -------- ADD EDGE --------
    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)   # undirected graph

    # -------- BFS TRAVERSAL --------
    def bfs(self, start):
        visited = [False] * self.V
        queue = deque([start])
        visited[start] = True

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

        while queue:
            node = queue.popleft()
            print(node, end=" ")

            for neighbor in self.graph[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    queue.append(neighbor)

        print()

    # -------- DFS TRAVERSAL --------
    def dfs_util(self, node, visited):
        visited[node] = True
        print(node, end=" ")

        for neighbor in self.graph[node]:
            if not visited[neighbor]:
                self.dfs_util(neighbor, visited)

    def dfs(self, start):
        visited = [False] * self.V
        print("DFS Traversal:", end=" ")
        self.dfs_util(start, visited)
        print()

# ===================== TEST CODE =====================

if __name__ == "__main__":
    n = int(input("Enter number of vertices: "))
    g = Graph(n)

    edges = int(input("Enter number of edges: "))

    print("\nEnter edges (u v):")
    for _ in range(edges):
        u, v = map(int, input().split())
        g.add_edge(u, v)

    start = int(input("\nEnter starting node: "))

    print()
    g.bfs(start)
    g.dfs(start)



Output :