Dsa all programs
Assignment 1: Library Borrowing Management System
from collections import Counter
borrow_records = {
"member1": ["Book A", "Book B"],
"member2": [],
"member3": ["Book A", "Book C", "Book B"],
"member4": ["Book C"],
"member5": ["Book A"]
}
def compute_average_borrowed(records):
total_books = sum(len(books) for books in records.values())
total_members = len(records)
return total_books / total_members if total_members > 0 else 0
def find_max_min_borrowed_books(records):
book_count = Counter()
for books in records.values():
book_count.update(books)
if not book_count:
return None, None
max_borrowed = max(book_count.items(), key=lambda x: x[1])
min_borrowed = min(book_count.items(), key=lambda x: x[1])
return max_borrowed, min_borrowed
def count_zero_borrow_members(records):
return sum(1 for books in records.values() if len(books) == 0)
def find_most_frequent_book(records):
book_count = Counter()
for books in records.values():
book_count.update(books)
if not book_count:
return None
max_borrow = max(book_count.values())
most_frequent_books = [book for book, cnt in book_count.items() if cnt == max_borrow]
return most_frequent_books
if __name__ == "__main__":
print("Library Borrowing Management System\n")
avg = compute_average_borrowed(borrow_records)
print(f"Average books borrowed per member: {avg:.2f}")
max_book, min_book = find_max_min_borrowed_books(borrow_records)
if max_book and min_book:
print(f"Most borrowed book: {max_book[0]} ({max_book[1]} times)")
print(f"Least borrowed book: {min_book[0]} ({min_book[1]} times)")
else:
print("No books have been borrowed.")
zero_borrow_count = count_zero_borrow_members(borrow_records)
print(f"Number of members who borrowed 0 books: {zero_borrow_count}")
mode_books = find_most_frequent_book(borrow_records)
if mode_books:
print("Most frequently borrowed book(s):", ", ".join(mode_books))
else:
print("No books found to determine mode.")
# Assignment 2
def linear_search(arr, target):
for i, val in enumerate(arr):
if val == target:
return i
return -1
def binary_search(sorted_arr, target):
left, right = 0, len(sorted_arr) - 1
while left <= right:
mid = (left + right) // 2
if sorted_arr[mid] == target:
return mid
elif sorted_arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
if __name__ == "__main__":
ids = [1034, 2051, 1022, 1505, 3002, 2501, 1890, 1200]
target = 1034
print(linear_search(ids, target))
print(binary_search(sorted(ids), target))
# Assignment 3: Undo/Redo Text Editor
class TextEditor:
def __init__(self):
self.document = ""
self.undo_stack = []
self.redo_stack = []
def make_change(self, change: str):
# Save current state to undo, then apply change
self.undo_stack.append(self.document)
self.document += change
self.redo_stack.clear()
print("\nChange made.")
self.display_state()
def undo_action(self):
if not self.undo_stack:
print("\nNo more actions to undo.")
else:
self.redo_stack.append(self.document)
self.document = self.undo_stack.pop()
print("\nUndo performed.")
self.display_state()
def redo_action(self):
if not self.redo_stack:
print("\nNo more actions to redo.")
else:
self.undo_stack.append(self.document)
self.document = self.redo_stack.pop()
print("\nRedo performed.")
self.display_state()
def display_state(self):
print("Current Document State:", repr(self.document))
if __name__ == "__main__":
# Example usage without interactive loop
editor = TextEditor()
editor.make_change("data structure")
editor.make_change(" FOP")
editor.undo_action()
editor.redo_action()
Assignment 4: Real-Time Event Processing System using deque
from collections import deque
class EventQueue:
def __init__(self):
self.queue = deque()
def add_event(self, event: str):
self.queue.append(event)
print(f"Event '{event}' added.")
def process_event(self):
if self.queue:
event = self.queue.popleft()
print(f"Processed event: '{event}'")
else:
print("No events to process.")
def display_events(self):
if self.queue:
print("Pending Events:")
for event in self.queue:
print(f"- {event}")
else:
print("No pending events.")
def cancel_event(self, event: str):
try:
self.queue.remove(event)
print(f"Event '{event}' canceled.")
except ValueError:
print(f"Event '{event}' not found or already processed.")
if __name__ == "__main__":
eq = EventQueue()
eq.add_event("engineers day")
eq.add_event("science day")
eq.add_event("independence day")
eq.process_event()
eq.display_events()
eq.cancel_event("science day")
eq.display_events()
Assignment 5: Call Center Queue Simulation
from collections import deque
class CallCenter:
def __init__(self):
self.call_queue = deque()
def add_call(self, customer_id, call_time):
call = {"CustomerID": customer_id, "CallTime": call_time}
self.call_queue.append(call)
print(f"Call from Customer {customer_id} added (Call Time: {call_time} mins)")
def answer_call(self):
if self.call_queue:
call = self.call_queue.popleft()
print(f"Answering call from Customer {call['CustomerID']} (Call Time: {call['CallTime']} mins)")
else:
print("No calls to answer.")
def view_queue(self):
if self.call_queue:
print("Current Call Queue:")
for i, call in enumerate(self.call_queue, start=1):
print(f"{i}. Customer {call['CustomerID']} - {call['CallTime']} mins")
else:
print("Call queue is empty.")
def is_queue_empty(self):
return len(self.call_queue) == 0
if __name__ == "__main__":
cc = CallCenter()
cc.add_call(101, 5)
cc.add_call(102, 3)
cc.add_call(103, 7)
cc.answer_call()
cc.view_queue()
print("Is queue empty?", cc.is_queue_empty())
Assignment 6: Hash Table with Chaining
class HashTable:
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)]
def _hash_function(self, key: int) -> int:
return key % self.size
def insert(self, key: int, value):
index = self._hash_function(key)
bucket = self.table[index]
for pair in bucket:
if pair[0] == key:
pair[1] = value
print(f"Updated key {key} with value {value}")
return
bucket.append([key, value])
print(f"Inserted key {key} with value {value}")
def search(self, key: int):
index = self._hash_function(key)
for pair in self.table[index]:
if pair[0] == key:
return pair[1]
return None
def delete(self, key: int):
index = self._hash_function(key)
bucket = self.table[index]
for i, pair in enumerate(bucket):
if pair[0] == key:
del bucket[i]
print(f"Deleted key {key}")
return
print(f"Key {key} not found for deletion.")
def display(self):
print("Hash Table:")
for i, bucket in enumerate(self.table):
print(f"Index {i}: {bucket}")
if __name__ == "__main__":
ht = HashTable()
ht.insert(15, "apple")
ht.insert(25, "banana")
ht.insert(35, "cherry")
print("Search 25:", ht.search(25))
ht.delete(25)
print("Search 25 after deletion:", ht.search(25))
ht.display()
# Assignment 7: Linear Probing Hash Table
class LinearProbingHashTable:
def __init__(self, size=10):
self.size = size
self.table = [None] * size
self.DELETED = "<DELETED>"
def _hash_function(self, key: int) -> int:
return key % self.size
def insert(self, key: int):
index = self._hash_function(key)
start = index
while self.table[index] is not None and self.table[index] != self.DELETED:
if self.table[index] == key:
print(f"Key {key} already exists at index {index}.")
return
index = (index + 1) % self.size
if index == start:
print("Hash table is full. Cannot insert.")
return
self.table[index] = key
print(f"Inserted key {key} at index {index}.")
def search(self, key: int):
index = self._hash_function(key)
start = 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:
break
print(f"Key {key} not found.")
return None
def delete(self, key: int):
idx = self.search(key)
if idx is not None:
self.table[idx] = self.DELETED
print(f"Key {key} deleted from index {idx}.")
def display(self):
print("Hash Table:")
for i, key in enumerate(self.table):
print(f"Index {i}: {key}")
if __name__ == "__main__":
ht = LinearProbingHashTable()
ht.insert(10)
ht.insert(20)
ht.insert(30)
ht.insert(20) # duplicate
ht.display()
ht.search(20)
ht.search(99)
ht.delete(20)
ht.search(20)
ht.display()
Assignment 8: BFS (adj list) and DFS (adj matrix)
from collections import deque
locations = ['A', 'B', 'C', 'D']
location_index = {name: idx for idx, name in enumerate(locations)}
# adjacency matrix for DFS
adj_matrix = [
# A B C D
[0,1,1,0], # A
[1,0,0,1], # B
[1,0,0,1], # C
[0,1,1,0], # D
]
def dfs_matrix(start):
visited = [False] * len(locations)
result = []
def dfs(node):
visited[node] = True
result.append(locations[node])
for neighbor in range(len(adj_matrix)):
if adj_matrix[node][neighbor] == 1 and not visited[neighbor]:
dfs(neighbor)
dfs(location_index[start])
return result
# adjacency list for BFS
adj_list = {
'A': ['B','C'],
'B': ['A','D'],
'C': ['A','D'],
'D': ['B','C'],
}
def bfs_list(start):
visited = set()
queue = deque([start])
result = []
while queue:
node = queue.popleft()
if node not in visited:
visited.add(node)
result.append(node)
for neighbor in adj_list.get(node, []):
if neighbor not in visited:
queue.append(neighbor)
return result
if __name__ == "__main__":
start = 'A'
print("DFS Traversal (using adjacency matrix):", dfs_matrix(start))
print("BFS Traversal (using adjacency list):", bfs_list(start))
Assignment 9: Construct expression tree from prefix, non-recursive postorder, delete
class Node:
def __init__(self, value):
self.data = value
self.left = None
self.right = None
def is_operator(c):
return c in "+-*/"
def construct_tree_from_prefix(prefix):
stack = []
# scan from right to left
for ch in reversed(prefix):
if not is_operator(ch):
stack.append(Node(ch))
else:
# operator: pop two nodes if available
if len(stack) < 2:
raise ValueError("Invalid prefix expression")
node = Node(ch)
node.left = stack.pop()
node.right = stack.pop()
stack.append(node)
if not stack:
return None
return stack[-1]
def postorder_non_recursive(root):
if root is None:
return []
s1 = [root]
s2 = []
while s1:
node = s1.pop()
s2.append(node)
if node.left:
s1.append(node.left)
if node.right:
s1.append(node.right)
# s2 reversed is postorder
return [n.data for n in reversed(s2)]
def delete_tree(root):
# Explicitly break references (help GC)
if root is None:
return
stack = [root]
while stack:
node = stack.pop()
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
node.left = None
node.right = None
node.data = None
if __name__ == "__main__":
prefix = "+--a*bc/def"
root = construct_tree_from_prefix(prefix)
postorder = postorder_non_recursive(root)
print("Postorder Traversal (Non-Recursive):", " ".join(postorder))
delete_tree(root)
print("Tree deleted (references cleared).")
टिप्पणियाँ
एक टिप्पणी भेजें