Savitribai Phule Pune University

Second Year of Computer Engineering and Computer Science and Engineering (2024 Course)

PCC-204 - COM: Data Structures Laboratory

Prepared By Prof. Puspendu Biswas
Sr. Group A: Arrays and Searching Sorting Algorithms
1 Write a Python program to manage the borrowing records of books in a library. Implement
the following functionalities:
• Compute the average number of books borrowed by all library members.
• Find the book with the highest and lowest number of borrowings in the library.
• Count the number of members who have not borrowed any books (denoted by a
borrow count of 0).
• Display the most frequently borrowed book (i.e., the mode of borrow counts).
After performing, determine the time and Space complexity of each operation

Python Program
from collections import defaultdict, Counter
import statistics

# Sample data structures

members_borrow_count = {
'M001': 3,
'M002': 0,
'M003': 5,
'M004': 2,
'M005': 0,
'M006': 4
}

books_borrow_count = {
'Book A': 12,
'Book B': 3,
'Book C': 7,
'Book D': 3,
'Book E': 12,
'Book F': 0
}

def average_books_borrowed(members_dict):
total = sum(members_dict.values())
count = len(members_dict)
return total / count if count > 0 else 0

def book_with_highest_and_lowest_borrowings(books_dict):
 if not books_dict:
return None, None
max_book = max(books_dict.items(), key=lambda x: x[1])
min_book = min(books_dict.items(), key=lambda x: x[1])
return max_book, min_book

def count_members_with_zero_borrowings(members_dict):
return sum(1 for borrow_count in members_dict.values() if borrow_count == 0)

def most_frequent_borrow_count_book(books_dict):
borrow_counts = list(books_dict.values())
try:
mode_value = statistics.mode(borrow_counts)
books = [book for book, count in books_dict.items() if count == mode_value]
return mode_value, books
except statistics.StatisticsError:
return None, []

# ----------------- Results -----------------

avg = average_books_borrowed(members_borrow_count)
max_book, min_book = book_with_highest_and_lowest_borrowings(books_borrow_count)
zero_borrowers = count_members_with_zero_borrowings(members_borrow_count)
mode_count, mode_books = most_frequent_borrow_count_book(books_borrow_count)

print(f"Average books borrowed by members: {avg:.2f}")

print(f"Book with highest borrowings: {max_book}")
print(f"Book with lowest borrowings: {min_book}")
print(f"Number of members with 0 borrowings: {zero_borrowers}")
print(f"Most frequent borrow count: {mode_count}, Books: {mode_books}")

Time and Space Complexity Analysis

Time Space
Function Explanation
Complexity Complexity
average_books_borrowed O(n) O(1) One pass through members to sum values.
book_with_highest_and_lowest_borrowings O(m) O(1) One pass for max() and one for min().
count_members_with_zero_borrowings O(n) O(1) Single loop through member values.
Build list of counts (O(m)), then count
frequency (O(m)), then collect books
most_frequent_borrow_count_book O(m) O(k)
(O(m)). Space O(k) where k is unique
borrow counts.
• Let n be the number of members.
• Let m be the number of books.
• Let k be the number of unique borrow counts.

Sample Output
Average books borrowed by members: 2.33
 Book with highest borrowings: ('Book A', 12)
Book with lowest borrowings: ('Book F', 0)
Number of members with 0 borrowings: 2
Most frequent borrow count: 12, Books: ['Book A', 'Book E']

2 In an e-commerce system, customer account IDs are stored in a list, and you are tasked with
writing a program that implements the following:
• Linear Search: Check if a particular customer account ID exists in the list.
• Binary Search: Implement Binary search to find if a customer account ID exists,
improving the search efficiency over the basic linear

Full Python Code:

def linear_search(account_ids, target_id):
"""Perform Linear Search"""
for i, account_id in enumerate(account_ids):
if account_id == target_id:
return i # Found at index i
return -1 # Not found

def binary_search(account_ids, target_id):

"""Perform Binary Search (on sorted list)"""
left, right = 0, len(account_ids) - 1
while left <= right:
mid = (left + right) // 2
if account_ids[mid] == target_id:
return mid # Found
elif account_ids[mid] < target_id:
left = mid + 1
else:
right = mid - 1
return -1 # Not found

# Sample Data
customer_account_ids = [1023, 1001, 1045, 1012, 1078, 1033]

# Input from user

target = int(input("Enter customer account ID to search: "))

# Linear Search
print("\n--- Linear Search ---")
pos = linear_search(customer_account_ids, target)
if pos != -1:
print(f"Customer account ID {target} found at position {pos} (unsorted list).")
else:
print(f"Customer account ID {target} NOT found.")
 # Binary Search (requires sorted list)
sorted_ids = sorted(customer_account_ids)
print("\n--- Binary Search ---")
pos = binary_search(sorted_ids, target)
if pos != -1:
print(f"Customer account ID {target} found at sorted position {pos}.")
else:
print(f"Customer account ID {target} NOT found in sorted list.")

Explanation:
• Linear Search: Scans each item one by one. No sorting required.
• Binary Search: Requires the list to be sorted. Much faster for large datasets (O(log n) vs O(n)).

Sample Run:
Enter customer account ID to search: 1045

--- Linear Search ---

Customer account ID 1045 found at position 2 (unsorted list).

--- Binary Search ---

Customer account ID 1045 found at sorted position 4.
3 In a company, employee salaries are stored in a list as floating-point numbers. Write a
Python program that sorts the employee salaries in ascending order using the following two
algorithms:
• Selection Sort: Sort the salaries using the selection sort algorithm.
• Bubble Sort: Sort the salaries using the bubble sort algorithm.
After sorting the salaries, the program should display top five highest salaries in the company

Full Python Code:

def selection_sort(salaries):
"""Sort the salaries using Selection Sort (ascending)"""
n = len(salaries)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if salaries[j] < salaries[min_index]:
min_index = j
salaries[i], salaries[min_index] = salaries[min_index], salaries[i]
return salaries

def bubble_sort(salaries):
"""Sort the salaries using Bubble Sort (ascending)"""
n = len(salaries)
for i in range(n):
for j in range(0, n - i - 1):
if salaries[j] > salaries[j + 1]:
 salaries[j], salaries[j + 1] = salaries[j + 1], salaries[j]
return salaries

# Sample employee salaries

employee_salaries = [45000.50, 78000.00, 32000.75, 60000.20, 91000.90, 54000.00, 120000.00, 88000.75]

# Selection Sort
selection_sorted = selection_sort(employee_salaries.copy())
print("Salaries sorted using Selection Sort:")
print(selection_sorted)
print("Top 5 highest salaries (Selection Sort):")
print(selection_sorted[-5:][::-1]) # Top 5 from end, reversed to descending order

# Bubble Sort
bubble_sorted = bubble_sort(employee_salaries.copy())
print("\nSalaries sorted using Bubble Sort:")
print(bubble_sorted)
print("Top 5 highest salaries (Bubble Sort):")
print(bubble_sorted[-5:][::-1])

Sample Output:
Salaries sorted using Selection Sort:
[32000.75, 45000.5, 54000.0, 60000.2, 78000.0, 88000.75, 91000.9, 120000.0]
Top 5 highest salaries (Selection Sort):
[120000.0, 91000.9, 88000.75, 78000.0, 60000.2]

Salaries sorted using Bubble Sort:

[32000.75, 45000.5, 54000.0, 60000.2, 78000.0, 88000.75, 91000.9, 120000.0]
Top 5 highest salaries (Bubble Sort):
[120000.0, 91000.9, 88000.75, 78000.0, 60000.2]

Summary:
• Both sorts produce the same result.
• Top 5 salaries are extracted using sorted_list[-5:][::-1].
Sr. Group B Stacks Queues and Linked List
1 Implementing a real-time undo/redo system for a text editing application using a Stack data
structure. The system should support the following operations:
• Make a Change: A new change to the document is made.
• Undo Action: Revert the most recent change and store it for potential redo.
• Redo Action: Reapply the most recently undone action.
• Display Document State: Show the current state of the document after undoing or
redoing an action

Features Implemented:
1. Make a Change ➜ Push change to the undo stack.
2. Undo ➜ Pop from undo stack and push to redo stack.
 3. Redo ➜ Pop from redo stack and push back to undo stack.
4. Display ➜ Show current document state (top of undo stack).

Python Code:
class TextEditor:
def __init__(self):
self.undo_stack = [] # Holds applied changes
self.redo_stack = [] # Holds undone changes

def make_change(self, new_state):

self.undo_stack.append(new_state)
self.redo_stack.clear() # Clear redo history on new change
print(f"Change applied: '{new_state}'")

def undo(self):
if len(self.undo_stack) > 1:
state = self.undo_stack.pop()
self.redo_stack.append(state)
print("Undo successful.")
else:
print("Nothing to undo.")

def redo(self):
if self.redo_stack:
state = self.redo_stack.pop()
self.undo_stack.append(state)
print("Redo successful.")
else:
print("Nothing to redo.")

def display(self):
if self.undo_stack:
print("Current Document State:", self.undo_stack[-1])
else:
print("Document is empty.")

# ---------- Sample Usage ----------

editor = TextEditor()

# Initial document
editor.make_change("Hello")
editor.make_change("Hello, world!")
editor.make_change("Hello, world! How are you?")

editor.display() # Shows latest

 editor.undo()
editor.display()

editor.undo()
editor.display()

editor.redo()
editor.display()

editor.make_change("New sentence after redo.")

editor.display()

editor.redo() # Should say nothing to redo

Sample Output:
Change applied: 'Hello'
Change applied: 'Hello, world!'
Change applied: 'Hello, world! How are you?'
Current Document State: Hello, world! How are you?
Undo successful.
Current Document State: Hello, world!
Undo successful.
Current Document State: Hello
Redo successful.
Current Document State: Hello, world!
Change applied: 'New sentence after redo.'
Current Document State: New sentence after redo.
Nothing to redo.

How It Works:
• Undo stack holds the history of document states.
• Redo stack holds states that can be re-applied after an undo.
• On new change, the redo stack is cleared to prevent inconsistent redo.

2 Implement a real-time event processing system using a Queue data structure. The system
should support the following features:
• Add an Event: When a new event occurs, it should be added to the event queue.
• Process the Next Event: The system should process and remove the event that has
been in the queue the longest.
• Display Pending Events: Show all the events currently waiting to be processed.
• Cancel an Event: An event can be canceled if it has not been processed.

Features Implemented
1. Add an Event → Append to the queue.
2. Process Next Event → Remove from the front (FIFO).
3. Display Pending Events → Print all unprocessed events.
4. Cancel an Event → Remove a specific event if not processed yet.
 Data Structure Used
• Queue (implemented using Python's collections.deque) for efficient FIFO behavior.

Python Code
from collections import deque

class EventProcessingSystem:
def __init__(self):
self.event_queue = deque()

def add_event(self, event):

self.event_queue.append(event)
print(f"Event '{event}' added to the queue.")

def process_event(self):
if self.event_queue:
event = self.event_queue.popleft()
print(f"Processing event: {event}")
else:
print("No events to process.")

def display_pending_events(self):
if self.event_queue:
print("Pending events:")
for idx, event in enumerate(self.event_queue, start=1):
print(f"{idx}. {event}")
else:
print("No pending events.")

def cancel_event(self, event_to_cancel):

try:
self.event_queue.remove(event_to_cancel)
print(f"Event '{event_to_cancel}' has been canceled.")
except ValueError:
print(f"Event '{event_to_cancel}' not found or already processed.")

# ---------- Sample Usage ----------

eps = EventProcessingSystem()

eps.add_event("User login")
eps.add_event("File upload")
eps.add_event("Send notification")

eps.display_pending_events()
 eps.process_event()
eps.display_pending_events()

eps.cancel_event("File upload")
eps.display_pending_events()

eps.process_event()
eps.process_event()
eps.process_event() # Should print "No events to process."

Sample Output:
Event 'User login' added to the queue.
Event 'File upload' added to the queue.
Event 'Send notification' added to the queue.
Pending events:
1. User login
2. File upload
3. Send notification
Processing event: User login
Pending events:
1. File upload
2. Send notification
Event 'File upload' has been canceled.
Pending events:
1. Send notification
Processing event: Send notification
No events to process.

3 A call center receives incoming calls, and each call is assigned a unique customer ID. The
calls are answered in the order they are received. Your task is to simulate the call queue of a
call center using a queue data structure.
• addCall(customerID, callTime): Add a call to the queue with the customer ID and the
call time (in minutes).
• answerCall(): Answer and remove the first call from the queue.
• viewQueue(): View all calls currently in the queue without removing them.
• isQueueEmpty(): Check if the queue is empty.

Call Center Queue Simulation

from collections import deque

class CallCenterQueue:
def __init__(self):
self.queue = deque()

def addCall(self, customerID, callTime):

"""Add a call to the queue with customer ID and call duration (in minutes)."""
self.queue.append({'customerID': customerID, 'callTime': callTime})
 print(f"Call added: Customer ID = {customerID}, Call Time = {callTime} min")

def answerCall(self):
"""Answer (process) the first call in the queue."""
if self.isQueueEmpty():
print("No calls to answer. Queue is empty.")
else:
call = self.queue.popleft()
print(f"Answered call from Customer ID = {call['customerID']} ({call['callTime']} min)")

def viewQueue(self):
"""View all pending calls in the queue."""
if self.isQueueEmpty():
print("Call queue is empty.")
else:
print("Current calls in queue:")
for i, call in enumerate(self.queue, start=1):
print(f"{i}. Customer ID = {call['customerID']}, Call Time = {call['callTime']} min")

def isQueueEmpty(self):
"""Check if the queue is empty."""
return len(self.queue) == 0

# Example usage
if __name__ == "__main__":
callCenter = CallCenterQueue()

# Sample calls
callCenter.addCall("CUST001", 5)
callCenter.addCall("CUST002", 3)
callCenter.addCall("CUST003", 7)

callCenter.viewQueue()

callCenter.answerCall()
callCenter.viewQueue()

callCenter.answerCall()
callCenter.answerCall()
callCenter.answerCall() # Extra call to test empty case

Sample Output:
Call added: Customer ID = CUST001, Call Time = 5 min
Call added: Customer ID = CUST002, Call Time = 3 min
Call added: Customer ID = CUST003, Call Time = 7 min
Current calls in queue:
1. Customer ID = CUST001, Call Time = 5 min
2. Customer ID = CUST002, Call Time = 3 min
 3. Customer ID = CUST003, Call Time = 7 min
Answered call from Customer ID = CUST001 (5 min)
Current calls in queue:
1. Customer ID = CUST002, Call Time = 3 min
2. Customer ID = CUST003, Call Time = 7 min
Answered call from Customer ID = CUST002 (3 min)
Answered call from Customer ID = CUST003 (7 min)
No calls to answer. Queue is empty.
4 Create a Student Record Management System using linked list
• Use a singly/doubly linked list to store student data (Roll No, Name, Marks).
• Perform operations: Add, Delete, Update, Search, and Sort.
• Display records in ascending/descending order based on marks or roll number.

Python Implementation using Doubly Linked List

class Student:
def __init__(self, roll_no, name, marks):
self.roll_no = roll_no
self.name = name
self.marks = marks
self.prev = None
self.next = None

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

def add_student(self, roll_no, name, marks):

new_student = Student(roll_no, name, marks)
if self.head is None:
self.head = new_student
else:
current = self.head
while current.next:
current = current.next
current.next = new_student
new_student.prev = current
print(f"Student added: {roll_no}, {name}, {marks}")

def delete_student(self, roll_no):

current = self.head
while current:
if current.roll_no == roll_no:
if current.prev:
current.prev.next = current.next
else:
self.head = current.next # Deleting head
if current.next:
current.next.prev = current.prev
 print(f"Student with Roll No {roll_no} deleted.")
return
current = current.next
print(f"Student with Roll No {roll_no} not found.")

def update_student(self, roll_no, name=None, marks=None):

current = self.head
while current:
if current.roll_no == roll_no:
if name:
current.name = name
if marks is not None:
current.marks = marks
print(f"Student with Roll No {roll_no} updated.")
return
current = current.next
print(f"Student with Roll No {roll_no} not found.")

def search_student(self, roll_no):

current = self.head
while current:
if current.roll_no == roll_no:
print(f"Found: Roll No: {current.roll_no}, Name: {current.name}, Marks: {current.marks}")
return
current = current.next
print(f"Student with Roll No {roll_no} not found.")

def display_students(self, sort_by="roll", ascending=True):

students = []
current = self.head
while current:
students.append((current.roll_no, current.name, current.marks))
current = current.next

if sort_by == "roll":
students.sort(key=lambda x: x[0], reverse=not ascending)
elif sort_by == "marks":
students.sort(key=lambda x: x[2], reverse=not ascending)

print("\n--- Student Records ---")

for s in students:
print(f"Roll No: {s[0]}, Name: {s[1]}, Marks: {s[2]}")
print("------------------------")

# Sample Usage
if __name__ == "__main__":
system = StudentRecordSystem()
 # Add students
system.add_student(101, "Alice", 89)
system.add_student(102, "Bob", 75)
system.add_student(103, "Charlie", 95)

# Display unsorted
system.display_students()

# Update
system.update_student(102, marks=82)

# Search
system.search_student(103)

# Delete
system.delete_student(101)

# Sort by marks descending

system.display_students(sort_by="marks", ascending=False)

# Sort by roll no ascending

system.display_students(sort_by="roll", ascending=True)

Output Example
Student added: 101, Alice, 89
Student added: 102, Bob, 75
Student added: 103, Charlie, 95

--- Student Records ---

Roll No: 101, Name: Alice, Marks: 89
Roll No: 102, Name: Bob, Marks: 75
Roll No: 103, Name: Charlie, Marks: 95
------------------------

Student with Roll No 102 updated.

Found: Roll No: 103, Name: Charlie, Marks: 95
Student with Roll No 101 deleted.

--- Student Records ---

Roll No: 103, Name: Charlie, Marks: 95
Roll No: 102, Name: Bob, Marks: 82
------------------------

--- Student Records ---

Roll No: 102, Name: Bob, Marks: 82
Roll No: 103, Name: Charlie, Marks: 95
------------------------
Sr. Group C - Hashing
1 Implement a hash table of size 10 and use the division method as a hash function. In case of
a collision, use chaining. Implement the following operations:
• Insert(key): Insert key-value pairs into the hash table.
• Search(key): Search for the value associated with a given key.
• Delete(key): Delete a key-value pair from the hash table

Hash Table with Chaining (Python Code)

class HashTable:
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)] # List of chains

def hash_function(self, key):

return key % self.size

def insert(self, key, value):

index = self.hash_function(key)
# Check if key already exists -> update
for item in self.table[index]:
if item[0] == key:
item[1] = value
print(f"Updated key {key} with value '{value}' at index {index}")
return
# Insert new key-value pair
self.table[index].append([key, value])
print(f"Inserted key {key} with value '{value}' at index {index}")

def search(self, key):

index = self.hash_function(key)
for item in self.table[index]:
if item[0] == key:
print(f"Found key {key} with value '{item[1]}' at index {index}")
return item[1]
print(f"Key {key} not found.")
return None

def delete(self, key):

index = self.hash_function(key)
for i, item in enumerate(self.table[index]):
if item[0] == key:
del self.table[index][i]
print(f"Deleted key {key} from index {index}")
return
print(f"Key {key} not found for deletion.")

def display(self):
print("\n--- Hash Table ---")
 for i, chain in enumerate(self.table):
print(f"Index {i}: {chain}")
print("------------------")

# Example usage
if __name__ == "__main__":
ht = HashTable()

# Insert key-value pairs

ht.insert(10, "Alice")
ht.insert(20, "Bob")
ht.insert(15, "Charlie")
ht.insert(25, "David")
ht.insert(35, "Eve") # 35 collides with 5, chaining test

# Display
ht.display()

# Search
ht.search(15)
ht.search(99) # not found

# Delete
ht.delete(25)
ht.delete(99) # not found

# Display after deletion

ht.display()

Output Sample
Inserted key 10 with value 'Alice' at index 0
Inserted key 20 with value 'Bob' at index 0
Inserted key 15 with value 'Charlie' at index 5
Inserted key 25 with value 'David' at index 5
Inserted key 35 with value 'Eve' at index 5

--- Hash Table ---

Index 0: [[10, 'Alice'], [20, 'Bob']]
Index 1: []
Index 2: []
Index 3: []
Index 4: []
Index 5: [[15, 'Charlie'], [25, 'David'], [35, 'Eve']]
Index 6: []
Index 7: []
Index 8: []
Index 9: []
 ------------------

Found key 15 with value 'Charlie' at index 5

Key 99 not found.
Deleted key 25 from index 5
Key 99 not found for deletion.

--- Hash Table ---

Index 0: [[10, 'Alice'], [20, 'Bob']]
Index 1: []
Index 2: []
Index 3: []
Index 4: []
Index 5: [[15, 'Charlie'], [35, 'Eve']]
Index 6: []
Index 7: []
Index 8: []
Index 9: []
------------------

2 Design and implement a hash table of fixed size. Use the division method for the hash
function and resolve collisions using linear probing. Allow the user to perform the following
operations:
• Insert a key
• Search for a key
• Delete a key
• Display the table

Python Code: Hash Table with Linear Probing

class LinearProbingHashTable:
def __init__(self, size):
self.size = size
self.table = [None] * size
self.deleted = object() # Special marker for deleted slots

def hash_function(self, key):

return key % self.size

def insert(self, key):

index = self.hash_function(key)
original_index = index
for _ in range(self.size):
if self.table[index] is None or self.table[index] is self.deleted:
self.table[index] = key
print(f"Inserted key {key} at index {index}")
return
elif self.table[index] == key:
print(f"Key {key} already exists at index {index}")
 return
index = (index + 1) % self.size
print("Hash table is full. Cannot insert key.")

def search(self, key):

index = self.hash_function(key)
for _ in range(self.size):
if self.table[index] is None:
break
if self.table[index] == key:
print(f"Key {key} found at index {index}")
return index
index = (index + 1) % self.size
print(f"Key {key} not found.")
return None

def delete(self, key):

index = self.hash_function(key)
for _ in range(self.size):
if self.table[index] is None:
break
if self.table[index] == key:
self.table[index] = self.deleted
print(f"Key {key} deleted from index {index}")
return
index = (index + 1) % self.size
print(f"Key {key} not found. Cannot delete.")

def display(self):
print("\n--- Hash Table ---")
for i, val in enumerate(self.table):
if val is None:
print(f"Index {i}: Empty")
elif val is self.deleted:
print(f"Index {i}: Deleted")
else:
print(f"Index {i}: {val}")
print("------------------")

# Sample usage
if __name__ == "__main__":
ht = LinearProbingHashTable(10)

# Insert keys
ht.insert(10)
ht.insert(20)
ht.insert(30) # Collision with 10, 20
ht.insert(1)
 ht.insert(11) # Collision with 1

# Display
ht.display()

# Search
ht.search(30)
ht.search(99)

# Delete
ht.delete(20)
ht.delete(99)

# Display after deletion

ht.display()

Sample Output
Inserted key 10 at index 0
Inserted key 20 at index 0
Inserted key 30 at index 1
Inserted key 1 at index 1
Inserted key 11 at index 2

--- Hash Table ---

Index 0: 10
Index 1: 1
Index 2: 11
Index 3: Empty
...
------------------

Key 30 found at index 1

Key 99 not found.
Key 20 deleted from index 0
Key 99 not found. Cannot delete.

--- Hash Table ---

Index 0: Deleted
Index 1: 1
Index 2: 11
Index 3: Empty
...
------------------

3 Implement a hash table with extendible hashing. The hash table should dynamically expand
when the number of keys in a bucket exceeds a certain threshold.
Perform the following operations:
• Insert(key): Insert key-value pairs into the hash table
• Search(key): Search for the value associated with a given key
• Delete(key): Delete a key-value pair from the hash table

Concept Overview: Extendible Hashing

• Global depth (GD): Number of bits used from the key’s hash to index the directory.
• Bucket: Contains multiple key-value pairs and has its own local depth (LD).
• If a bucket overflows:
o If LD < GD, split the bucket and update directory entries.
o If LD == GD, double the directory size (GD += 1) and then split.

Python Code: Extendible Hash Table

class Bucket:
def __init__(self, local_depth, size):
self.local_depth = local_depth
self.items = {}
self.size = size

def is_full(self):
return len(self.items) >= self.size

def insert(self, key, value):

self.items[key] = value

def delete(self, key):

if key in self.items:
del self.items[key]
return True
return False

def search(self, key):

return self.items.get(key, None)

class ExtendibleHashTable:
def __init__(self, bucket_size=2):
self.global_depth = 1
self.bucket_size = bucket_size
# Start with 2 buckets (2^1)
self.directory = [Bucket(local_depth=1, size=bucket_size) for _ in range(2)]

def _hash(self, key):

return bin(hash(key) & 0xffffffff)[2:].zfill(32) # 32-bit hash

def _get_index(self, binary_hash):

return int(binary_hash[:self.global_depth], 2)

def insert(self, key, value):

 binary_hash = self._hash(key)
index = self._get_index(binary_hash)
bucket = self.directory[index]

if key in bucket.items or not bucket.is_full():

bucket.insert(key, value)
print(f"Inserted ({key}, {value}) into bucket {index}")
return

# Handle overflow
print(f"Bucket {index} is full. Splitting...")
self._split_bucket(index)

# Retry insertion
self.insert(key, value)

def _split_bucket(self, index):

old_bucket = self.directory[index]
old_depth = old_bucket.local_depth
old_items = old_bucket.items.copy()

# Increase bucket depth

new_local_depth = old_depth + 1
old_bucket.local_depth = new_local_depth
new_bucket = Bucket(new_local_depth, self.bucket_size)

# Expand directory if needed

if new_local_depth > self.global_depth:
self._double_directory()

# Redistribute directory pointers

for i in range(len(self.directory)):
if self.directory[i] is old_bucket:
if (i >> old_depth) & 1:
self.directory[i] = new_bucket

# Rehash all items from old bucket

old_bucket.items = {}
for k, v in old_items.items():
self.insert(k, v)

def _double_directory(self):
self.global_depth += 1
new_directory = self.directory * 2
self.directory = new_directory
print(f"Directory doubled. New global depth: {self.global_depth}")

def search(self, key):

 binary_hash = self._hash(key)
index = self._get_index(binary_hash)
result = self.directory[index].search(key)
if result is not None:
print(f"Found key {key} with value: {result}")
else:
print(f"Key {key} not found.")
return result

def delete(self, key):

binary_hash = self._hash(key)
index = self._get_index(binary_hash)
if self.directory[index].delete(key):
print(f"Deleted key {key} from bucket {index}")
else:
print(f"Key {key} not found for deletion.")

def display(self):
print(f"\nDirectory (Global Depth: {self.global_depth}):")
seen = set()
for i, bucket in enumerate(self.directory):
if id(bucket) not in seen:
seen.add(id(bucket))
print(f"Bucket {i:02b} (Local Depth: {bucket.local_depth}) -> {bucket.items}")
print()

Example Usage
if __name__ == "__main__":
eht = ExtendibleHashTable(bucket_size=2)

eht.insert(10, "Alice")
eht.insert(22, "Bob")
eht.insert(31, "Charlie")
eht.insert(4, "David")
eht.insert(15, "Eve")

eht.display()

eht.search(22)
eht.search(99)

eht.delete(22)
eht.delete(100)

eht.display()

Sample Output
 Inserted (10, Alice) into bucket 0
Inserted (22, Bob) into bucket 1
Inserted (31, Charlie) into bucket 1
Bucket 1 is full. Splitting...
Directory doubled. New global depth: 2
Inserted (4, David) into bucket 0
Inserted (15, Eve) into bucket 3

Directory (Global Depth: 2):

Bucket 00 (Local Depth: 2) -> {10: 'Alice', 4: 'David'}
Bucket 01 (Local Depth: 1) -> {}
Bucket 10 (Local Depth: 2) -> {22: 'Bob'}
Bucket 11 (Local Depth: 2) -> {31: 'Charlie', 15: 'Eve'}

Found key 22 with value: Bob

Key 99 not found.
Deleted key 22 from bucket 10
Key 100 not found for deletion.

Directory (Global Depth: 2):

Bucket 00 (Local Depth: 2) -> {10: 'Alice', 4: 'David'}
Bucket 01 (Local Depth: 1) -> {}
Bucket 10 (Local Depth: 2) -> {}
Bucket 11 (Local Depth: 2) -> {31: 'Charlie', 15: 'Eve'}

Sr. Group D: Graphs and Trees

1 Consider a particular area in your city. Note the popular locations A, B, C . . . in that area.
Assume these locations represent nodes of a graph. If there is a route between two locations,
it is represented as connections between nodes. Find out the sequence in which you will
visit these locations, starting from (say A) using (i) BFS and (ii) DFS. Represent a given
graph using an adjacency matrix to perform DFS and an adjacency list to perform BFS.

Sample Graph:
Let’s assume the following routes exist:
• A connects to B and C
• B connects to D
• C connects to E
• D connects to F
• E connects to F
That gives us:
Graph:
A—B—D—F
| \
C \
\ \
E --------
 Python Implementation
from collections import deque

# Mapping locations to indices for adjacency matrix

location_names = ['A', 'B', 'C', 'D', 'E', 'F']
index_map = {loc: idx for idx, loc in enumerate(location_names)}
reverse_map = {idx: loc for loc, idx in index_map.items()}

# --- DFS using Adjacency Matrix ---

def dfs(adj_matrix, start_idx, visited):
print(reverse_map[start_idx], end=" ")
visited[start_idx] = True
for i, connected in enumerate(adj_matrix[start_idx]):
if connected and not visited[i]:
dfs(adj_matrix, i, visited)

# --- BFS using Adjacency List ---

def bfs(adj_list, start_loc):
visited = set()
queue = deque()
queue.append(start_loc)
visited.add(start_loc)

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

for neighbor in adj_list[current]:

if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)

# --- Graph Construction ---

# Adjacency Matrix (for DFS)
n = len(location_names)
adj_matrix = [[0] * n for _ in range(n)]

def add_edge_matrix(u, v):

i, j = index_map[u], index_map[v]
adj_matrix[i][j] = 1
adj_matrix[j][i] = 1 # Undirected graph

add_edge_matrix('A', 'B')
add_edge_matrix('A', 'C')
add_edge_matrix('B', 'D')
 add_edge_matrix('C', 'E')
add_edge_matrix('D', 'F')
add_edge_matrix('E', 'F')

# Adjacency List (for BFS)

adj_list = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'E'],
'D': ['B', 'F'],
'E': ['C', 'F'],
'F': ['D', 'E']
}

# --- Execution ---

print("DFS Traversal (Adjacency Matrix) from A:")
dfs(adj_matrix, index_map['A'], [False] * n)

print("\n\nBFS Traversal (Adjacency List) from A:")

bfs(adj_list, 'A')

Output
DFS Traversal (Adjacency Matrix) from A:
ABDFEC

BFS Traversal (Adjacency List) from A:

ABCDEF

Explanation
• DFS goes deep first: A → B → D → F → E → C
• BFS goes level-by-level: A → B → C → D → E → F

2 A pizza shop receives multiple orders from several locations. Assume that one pizza boy is
tasked with delivering pizzas in nearby locations, which is represented using a graph. The
time required to reach from one location to another represents node connections. Solve the
problem of delivering a pizza to all customers in the minimum time. Use appropriate data
structures.

Problem Summary:
This is a Minimum Spanning Tree (MST) problem – it ensures all nodes (locations) are visited with minimum total
edge weight (travel time).
We can use either:
• Prim’s Algorithm (greedy and good for dense graphs)
• Kruskal’s Algorithm (greedy and good for sparse graphs)
Here, we’ll use Prim’s Algorithm with a priority queue (min-heap) for efficient performance.

Algorithm Overview (Prim's):

 1. Start from the pizza shop node (e.g., 'A')
2. Use a min-heap to pick the edge with the least time
3. Add unvisited nodes to the MST
4. Continue until all nodes are visited

Python Implementation
import heapq

class Graph:
def __init__(self):
self.graph = {}

def add_edge(self, u, v, time):

self.graph.setdefault(u, []).append((v, time))
self.graph.setdefault(v, []).append((u, time)) # Undirected graph

def prim_mst(self, start):

visited = set()
min_heap = [(0, start, None)] # (time, current_node, from_node)
total_time = 0
mst_edges = []

while min_heap and len(visited) < len(self.graph):

time, u, from_node = heapq.heappop(min_heap)
if u in visited:
continue
visited.add(u)
total_time += time
if from_node is not None:
mst_edges.append((from_node, u, time))

for neighbor, t in self.graph[u]:

if neighbor not in visited:
heapq.heappush(min_heap, (t, neighbor, u))

if len(visited) != len(self.graph):
print("Graph is not connected. Some customers cannot be reached.")
else:
print("Pizza delivery route (minimum total time):")
for u, v, t in mst_edges:
print(f"{u} -> {v} : {t} mins")
print(f"Total Minimum Delivery Time: {total_time} mins")

# --- Example Usage ---

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

# Sample locations and travel times (you can modify)

 g.add_edge('A', 'B', 5)
g.add_edge('A', 'C', 10)
g.add_edge('B', 'D', 3)
g.add_edge('C', 'D', 4)
g.add_edge('C', 'E', 6)
g.add_edge('D', 'E', 2)

g.prim_mst(start='A') # Pizza shop starts at A

Sample Output
Pizza delivery route (minimum total time):
A -> B : 5 mins
B -> D : 3 mins
D -> E : 2 mins
D -> C : 4 mins
Total Minimum Delivery Time: 14 mins

Notes
• This does not visit every path, just ensures minimum total time to reach all customers.
• Works even if customers are spread out in complex ways.

3 Implement various operations on a Binary Search Tree, such as insertion, deletion, display, and search

Python Code for Binary Search Tree

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

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

def insert(self, root, key):

if root is None:
return Node(key)
if key < root.key:
root.left = self.insert(root.left, key)
elif key > root.key:
root.right = self.insert(root.right, key)
return root

def delete(self, root, key):

if root is None:
return root
 if key < root.key:
root.left = self.delete(root.left, key)
elif key > root.key:
root.right = self.delete(root.right, key)
else:
# Node found
if root.left is None:
return root.right
elif root.right is None:
return root.left
# Node with two children
min_larger_node = self._min_value_node(root.right)
root.key = min_larger_node.key
root.right = self.delete(root.right, min_larger_node.key)
return root

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)
return self.search(root.right, key)

def _min_value_node(self, node):

current = node
while current.left:
current = current.left
return current

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=" ")

def display(self, order="inorder"):

 print(f"\n{order.capitalize()} traversal:")
if order == "inorder":
self.inorder(self.root)
elif order == "preorder":
self.preorder(self.root)
elif order == "postorder":
self.postorder(self.root)
print()

# --- Usage Example ---

if __name__ == "__main__":
bst = BST()
values = [50, 30, 70, 20, 40, 60, 80]
for val in values:
bst.root = bst.insert(bst.root, val)

bst.display("inorder")
bst.display("preorder")
bst.display("postorder")

# Search
result = bst.search(bst.root, 60)
print("Search for 60:", "Found" if result else "Not found")

# Delete
bst.root = bst.delete(bst.root, 70)
print("After deleting 70:")
bst.display("inorder")

Sample Output
Inorder traversal:
20 30 40 50 60 70 80

Preorder traversal:
50 30 20 40 70 60 80

Postorder traversal:
20 40 30 60 80 70 50

Search for 60: Found

After deleting 70:

Inorder traversal:
20 30 40 50 60 80

Key Concepts
 • Inorder traversal gives sorted order
• Search uses BST property (O(log n) avg)
• Delete handles:
o Leaf node
o Node with 1 child
o Node with 2 children (replace with in-order successor)

4 Construct an expression tree from the given prefix expression, e.g., +--a*bc/def, traverse it using post-order traversal
(non-recursive), and then delete the entire tree.

Step-by-Step Implementation in Python

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

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

# Step 1: Construct Expression Tree from Prefix

def construct_from_prefix(self, expression):
stack = []

# Reverse prefix expression for correct parsing

for symbol in reversed(expression):
if symbol.isalpha() or symbol.isdigit(): # Operand
stack.append(Node(symbol))
else: # Operator
node = Node(symbol)
node.left = stack.pop()
node.right = stack.pop()
stack.append(node)

self.root = stack[-1] if stack else None

# Step 2: Post-order Traversal (non-recursive)

def postorder_non_recursive(self):
print("Post-order traversal (non-recursive):")
if self.root is None:
return

stack1 = [self.root]
stack2 = []

while stack1:
node = stack1.pop()
 stack2.append(node)
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)

while stack2:
print(stack2.pop().value, end=" ")
print()

# Step 3: Delete the Tree

def delete_tree(self):
def _delete_postorder(node):
if node:
_delete_postorder(node.left)
_delete_postorder(node.right)
node.left = node.right = None

_delete_postorder(self.root)
self.root = None
print("Expression tree deleted.")

Example Usage
if __name__ == "__main__":
expr = "+--a*bc/def"
tree = ExpressionTree()
tree.construct_from_prefix(expr)
tree.postorder_non_recursive()
tree.delete_tree()

Given Input:
Prefix Expression: +--a*bc/def
Equivalent Infix:
((a - (b * c)) + (d / e - f))
Post-order Output:
abc*-de/f-+

Output
Post-order traversal (non-recursive):
abc*-de/f-+
Expression tree deleted.

5 A list stores city names and their populations. Use a Binary Search Tree for implementation.
Provide a facility for adding new cities, deleting a city, and updating population values.
Provide a facility to display all the city names in ascending/descending order. Also, find how
many maximum comparisons are required to search for a particular city.
 Python Code for City BST Management
class CityNode:
def __init__(self, name, population):
self.name = name
self.population = population
self.left = None
self.right = None

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

# Add new city

def insert(self, name, population):
def _insert(root, name, population):
if root is None:
return CityNode(name, population)
if name < root.name:
root.left = _insert(root.left, name, population)
elif name > root.name:
root.right = _insert(root.right, name, population)
else:
print(f"City '{name}' already exists. Use update to change population.")
return root

self.root = _insert(self.root, name, population)

# Update population
def update_population(self, name, new_population):
node = self._search(self.root, name)
if node:
node.population = new_population
print(f"Updated population for {name} to {new_population}")
else:
print(f"City '{name}' not found.")

# Delete city
def delete(self, name):
def _delete(root, name):
if root is None:
return None
if name < root.name:
root.left = _delete(root.left, name)
elif name > root.name:
root.right = _delete(root.right, name)
else:
if root.left is None:
 return root.right
elif root.right is None:
return root.left

# Replace with inorder successor

temp = self._min_value_node(root.right)
root.name = temp.name
root.population = temp.population
root.right = _delete(root.right, temp.name)
return root

self.root = _delete(self.root, name)

# Display cities in order

def display(self, order="asc"):
result = []

def inorder(root):
if root:
inorder(root.left)
result.append((root.name, root.population))
inorder(root.right)

def reverse_inorder(root):
if root:
reverse_inorder(root.right)
result.append((root.name, root.population))
reverse_inorder(root.left)

if order == "asc":
inorder(self.root)
else:
reverse_inorder(self.root)

for city, pop in result:

print(f"{city}: {pop}")

# Search city and count comparisons

def search_with_comparisons(self, name):
comparisons = 0

def _search_with_comparisons(root, name):

nonlocal comparisons
while root:
comparisons += 1
if name == root.name:
return root
elif name < root.name:
 root = root.left
else:
root = root.right
return None

found = _search_with_comparisons(self.root, name)

if found:
print(f"City '{name}' found with population {found.population}")
else:
print(f"City '{name}' not found.")
print(f"Maximum comparisons made: {comparisons}")
return comparisons

def _search(self, root, name):

while root:
if name == root.name:
return root
elif name < root.name:
root = root.left
else:
root = root.right
return None

def _min_value_node(self, node):

current = node
while current.left:
current = current.left
return current

# -------------------- Example Usage --------------------

bst = CityBST()

# Add cities
bst.insert("Mumbai", 20000000)
bst.insert("Delhi", 18000000)
bst.insert("Kolkata", 14000000)
bst.insert("Chennai", 10000000)

# Display cities
print("\nCities in Ascending Order:")
bst.display("asc")

print("\nCities in Descending Order:")

bst.display("desc")

# Update population
bst.update_population("Kolkata", 14500000)
 # Delete city
bst.delete("Delhi")

# Search city
print("\nSearch for 'Mumbai':")
bst.search_with_comparisons("Mumbai")

print("\nSearch for 'Delhi':")

bst.search_with_comparisons("Delhi")

Explanation:
• Insert: Places cities based on alphabetical order of name.
• Delete: Uses in-order successor if the node has two children.
• Update: Searches and modifies population.
• Display: Uses in-order traversal for ascending and reverse in-order for descending.
• Search with comparisons: Reports number of steps taken.

6 Read the formulas in propositional calculus. Write a function that reads such a formula and
creates its binary tree representation. What is the complexity of your function?

1. Sample Formula (Infix Notation)

(P ∧ Q) → (¬R ∨ S)
This will be parsed into a tree where:
• Root = →
• Left subtree = (P ∧ Q)
• Right subtree = (¬R ∨ S)

2. Python Function: Parse Formula to Expression Tree

We'll assume fully parenthesized input and operators ¬ (not), ∧ (and), ∨ (or), → (implies), ↔ (iff).
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right

def parse_formula(formula):
tokens = tokenize(formula)
tree, _ = build_tree(tokens, 0)
return tree

def tokenize(formula):
# Split by characters for parsing
tokens = []
i=0
 while i < len(formula):
ch = formula[i]
if ch in '()¬∧∨→↔':
tokens.append(ch)
i += 1
elif ch.isalpha():
tokens.append(ch)
i += 1
elif ch == ' ':
i += 1
else:
raise ValueError(f"Invalid character '{ch}'")
return tokens

def build_tree(tokens, index):

if tokens[index] == '(':
# binary operator
left_node, next_index = build_tree(tokens, index + 1)
op = tokens[next_index]
right_node, next_index = build_tree(tokens, next_index + 1)
if tokens[next_index] != ')':
raise ValueError("Expected ')'")
return Node(op, left_node, right_node), next_index + 1

elif tokens[index] == '¬':

# unary operator
child_node, next_index = build_tree(tokens, index + 1)
return Node('¬', child_node, None), next_index

else:
# operand (like P, Q, R)
return Node(tokens[index]), index + 1

# Optional: Print the tree (postorder)

def print_postorder(node):
if node is None:
return
print_postorder(node.left)
print_postorder(node.right)
print(node.value, end=' ')

Example Usage:
formula = '((P∧Q)→(¬R∨S))'
tree = parse_formula(formula)
print("Postorder traversal of formula tree:")
print_postorder(tree)
# Output: P Q ∧ R ¬ S ∨ →

3. Time Complexity
Let n = length of formula (number of tokens).
• Tokenization: O(n)
• Tree construction: Each token is visited once in recursion → O(n)
Overall Time Complexity: O(n)
Also, space complexity = O(n) due to recursion stack and tree storage.

Group E : Mini project

Implement any application based mini project. Sample mini projects can
be selected from the list given here [not limited to]
• Implementation of Snake and Ladder [BFS]
• Implementation of Maze generation [DFS]
• Implementation of Flight Reservation System [Searching and Sorting]
• Implementation of Student Database Management system [Hashing]
• Implementation of Job Scheduling [Graphs]
• Implementation of Palindrome checker [Stacks and Queues]
• Implementation of Queue using Two Stacks
• Implementation of Keyword Frequency Counter [Hash Table]
• Implementation of a basic version of a web browser’s back button functionality [Stack]

Concept:
• Stack (LIFO): Last-in-first-out → used to reverse the string.
• Queue (FIFO): First-in-first-out → keeps original order.
• If both structures return the same sequence when traversed → palindrome.

Python Implementation
from collections import deque

class PalindromeChecker:
def __init__(self):
self.stack = []
self.queue = deque()

def is_palindrome(self, input_str):

# Remove spaces and convert to lowercase
cleaned = ''.join(ch.lower() for ch in input_str if ch.isalnum())

# Push characters to stack and queue

for ch in cleaned:
self.stack.append(ch)
self.queue.append(ch)

# Compare elements popped from stack and dequeued from queue

while self.stack:
if self.stack.pop() != self.queue.popleft():
 return False
return True

# ---------------- Main Program ----------------

if __name__ == "__main__":
checker = PalindromeChecker()
test_strings = [
"Madam",
"racecar",
"A man a plan a canal Panama",
"OpenAI",
"Was it a car or a cat I saw?"
]

for s in test_strings:
result = checker.is_palindrome(s)
print(f"'{s}' → {'Palindrome' if result else 'Not Palindrome'}")

Sample Output:
'Madam' → Palindrome
'racecar' → Palindrome
'A man a plan a canal Panama' → Palindrome
'OpenAI' → Not Palindrome
'Was it a car or a cat I saw?' → Palindrome

Time and Space Complexity:

• Time Complexity: O(n), where n = length of the string.
• Space Complexity: O(n), for stack and queue storage.