Assignment no: 1
class TelephoneBook:
def __init__(self, name, tel_no): # Fixed __init__ spelling
[Link] = name
self.tel_no = tel_no
def Insertion_QuadProbing():
hashtable = [None for _ in range(10)]
num_records = int(input("\nEnter number of records: "))
for _ in range(num_records):
n = input("Enter name: ")
t = int(input("Enter telephone no.: "))
hashValue = t % 10 # Primary hash function
i=1
original_hash = hashValue
while hashtable[hashValue] is not None:
hashValue = (original_hash + i * i) % 10
i += 1
if i > 10: # Prevent infinite loop
print("Hashtable full! Cannot insert.")
return hashtable
hashtable[hashValue] = TelephoneBook(n, t)
return hashtable
def Insertion_DoubleHashing():
hashtable = [None for _ in range(10)]
num_records = int(input("\nEnter number of records: "))
for _ in range(num_records):
n = input("Enter name: ")
t = int(input("Enter telephone no.: "))
h1 = t % 10
h2 = 7 - (t % 7)
hashvalue = h1
i=1
while hashtable[hashvalue] is not None:
hashvalue = (h1 + i * h2) % 10
i += 1
if i > 10:
print("Hashtable full! Cannot insert.")
return hashtable
hashtable[hashvalue] = TelephoneBook(n, t)
return hashtable
def Display_Table(hash_table, method_name):
print("\n--- Hashtable:", method_name, "---")
print("-------------------------------")
print("Index\tName\tTelephone No.")
print("-------------------------------")
for i, obj in enumerate(hash_table):
if obj is None:
print(f"{i}\t-\t-")
else:
print(f"{i}\t{[Link]}\t{obj.tel_no}")
print("-------------------------------")
def Search(hash1, hash2):
n = input("Enter name to search: ")
f1 = f2 = 0
comparisons_qp = comparisons_dh = 0
# Search in Quadratic Probing HashTable
for i, obj in enumerate(hash1):
comparisons_qp += 1
if obj and [Link] == n:
print("\n Found in Quadratic Probing HashTable!")
print("-------------------------------")
print("Index\tName\tTelephone No.")
print(f"{i}\t{[Link]}\t{obj.tel_no}")
print("-------------------------------")
f1 = 1
break
# Search in Double Hashing HashTable
for i, obj in enumerate(hash2):
comparisons_dh += 1
if obj and [Link] == n:
print("\n Found in Double Hashing HashTable!")
print("-------------------------------")
print("Index\tName\tTelephone No.")
print(f"{i}\t{[Link]}\t{obj.tel_no}")
print("-------------------------------")
f2 = 1
break
if not f1 and not f2:
print("\n Not found in either hashtable!")
# Show comparisons
print("\n Search Comparison Summary:")
print(f"Quadratic Probing: {comparisons_qp} comparisons")
print(f"Double Hashing: {comparisons_dh} comparisons")
def main():
hash1 = [None for _ in range(10)]
hash2 = [None for _ in range(10)]
while True:
print("\n-------------------------")
print("\t1. Insert Value")
print("\t2. Display")
print("\t3. Search")
print("\t4. Exit")
print("-------------------------")
try:
ch = int(input("Enter choice: "))
except ValueError:
print("Please enter a valid integer.")
continue
if ch == 1:
print("\nSelect collision method:")
print("\t1. Quadratic Probing")
print("\t2. Double Hashing")
try:
c = int(input("Enter choice: "))
if c == 1:
hash1 = Insertion_QuadProbing()
elif c == 2:
hash2 = Insertion_DoubleHashing()
else:
print("Invalid method choice.")
except ValueError:
print("Invalid input. Try again.")
elif ch == 2:
print("\n1. Display Quadratic Probing Table")
print("2. Display Double Hashing Table")
try:
c1 = int(input("Enter choice: "))
if c1 == 1:
Display_Table(hash1, "Quadratic Probing")
elif c1 == 2:
Display_Table(hash2, "Double Hashing")
else:
print("Invalid display choice.")
except ValueError:
print("Invalid input. Try again.")
elif ch == 3:
Search(hash1, hash2)
elif ch == 4:
print("Exiting...")
break
else:
print("! Enter valid choice.")
main()
Output:
Assignment no: 2
set1 = set()
set2 = set()
def add_element():
global set1, set2
set1Size = int(input("Enter size of set 1: "))
set1 = set()
for _ in range(set1Size):
element = int(input("Enter element: "))
[Link](element)
print("Set 1:", set1)
set2Size = int(input("Enter size of set 2: "))
set2 = set()
for _ in range(set2Size):
element = int(input("Enter element: "))
[Link](element)
print("Set 2:", set2)
def remove_element():
global set1, set2
selec = int(input("1. SET 1\n2. SET 2\nChoose an option (1/2):\t"))
elem = int(input("Element to be deleted:\t"))
if selec == 1:
if elem in set1:
[Link](elem)
print("After deletion:", set1)
else:
print("Element does not exist in SET 1.")
elif selec == 2:
if elem in set2:
[Link](elem)
print("After deletion:", set2)
else:
print("Element does not exist in SET 2.")
else:
print("Invalid selection.")
def isElementPresent():
global set1, set2
selec = int(input("Choose a set to search in:\n1. SET 1\n2. SET 2\nEnter choice (1/2): "))
num = int(input("Enter element to search: "))
if selec == 1:
print(f"Element {num} exists in SET 1.") if num in set1 else print(f"Element {num} does not exist in
SET 1.")
elif selec == 2:
print(f"Element {num} exists in SET 2.") if num in set2 else print(f"Element {num} does not exist in
SET 2.")
else:
print("Invalid selection. Please choose 1 or 2.")
def sizeOfSet():
print("\nThe size of SET 1 is", len(set1))
print("The size of SET 2 is", len(set2))
def unionOfSets():
print("\nUnion of sets:", [Link](set2))
def intersectionOfSets():
print("\nIntersection of sets:", [Link](set2))
def differenceOfSets():
print("\nDifference of sets (SET 1 - SET 2):", [Link](set2))
def subSetOrNot():
print("\nIs SET 1 a subset of SET 2?", [Link](set2))
def printElements():
print("\nElements in SET 1:", *set1)
print("Elements in SET 2:", *set2)
def main():
while True:
print("\nSelect an option:")
print("1. Add Elements to Sets")
print("2. Remove Element")
print("3. Check if Element is Present")
print("4. Get Size of Sets")
print("5. Union of Sets")
print("6. Intersection of Sets")
print("7. Difference of Sets")
print("8. Check if Subset")
print("9. Print Elements")
print("10. Exit")
choice = int(input("Enter choice: "))
if choice == 1:
add_element()
elif choice == 2:
remove_element()
elif choice == 3:
isElementPresent()
elif choice == 4:
sizeOfSet()
elif choice == 5:
unionOfSets()
elif choice == 6:
intersectionOfSets()
elif choice == 7:
differenceOfSets()
elif choice == 8:
subSetOrNot()
elif choice == 9:
printElements()
elif choice == 10:
print("Exiting program.")
break
else:
print("Invalid choice. Please try again.")
main()
Output:
Assignment no: 3
class Node:
def __init__(self, name):
[Link] = name
[Link] = []
def add_child(self, child_node):
[Link](child_node)
def print_tree(self, level=0):
print(' ' * level + [Link])
for child in [Link]:
child.print_tree(level + 1)
def count_nodes(self):
count = 1 # Count self
for child in [Link]:
count += child.count_nodes()
return count
def count_operations(self):
# Count 1 operation for printing each node
ops = 1
for child in [Link]:
ops += child.count_operations()
return ops
def build_book_tree():
total_chapters = 0
total_sections = 0
total_subsections = 0
book_name = input("Enter the name of the Book: ")
book = Node(book_name)
num_chapters = int(input(f"Enter number of chapters in '{book_name}': "))
total_chapters = num_chapters
for i in range(num_chapters):
chapter_name = input(f"Enter name of Chapter {i + 1}: ")
chapter = Node(chapter_name)
num_sections = int(input(f" Enter number of sections in '{chapter_name}': "))
total_sections += num_sections
for j in range(num_sections):
section_name = input(f" Enter name of Section {j + 1} in '{chapter_name}': ")
section = Node(section_name)
num_subsections = int(input(f" Enter number of subsections in '{section_name}': "))
total_subsections += num_subsections
for k in range(num_subsections):
subsection_name = input(f" Enter name of Subsection {k + 1} in '{section_name}': ")
subsection = Node(subsection_name)
section.add_child(subsection)
chapter.add_child(section)
book.add_child(chapter)
return book, total_chapters, total_sections, total_subsections
# Main
book_tree, c, s, ss = build_book_tree()
print("\n--- Book Structure ---")
book_tree.print_tree()
# Count total nodes
total_nodes = book_tree.count_nodes()
# Count printing operations
operations = book_tree.count_operations()
print("\n--- Time and Space Complexity (Based on Actual Input) ---")
print(f"Total Chapters : {c}")
print(f"Total Sections : {s}")
print(f"Total Subsections : {ss}")
print(f"Total Nodes : {total_nodes}")
print(f"Estimated Operations to Print Tree (Time) : {operations}")
print(f"Estimated Space Used (Node Objects) : {total_nodes} units (1 per node)")
print("Asymptotic Time Complexity : O(n)")
print("Asymptotic Space Complexity : O(n)")
Output:
Assignment no: 4:
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None
class BST:
def __init__(self):
[Link] = None
def insert(self, root, data):
if root is None:
return Node(data)
elif data < [Link]:
[Link] = [Link]([Link], data)
else:
[Link] = [Link]([Link], data)
return root
def display_inorder(self, root):
if root:
self.display_inorder([Link])
print([Link], end=" ")
self.display_inorder([Link])
def search(self, root, key):
if root is None:
return None
if key == [Link]:
return root
elif key < [Link]:
return [Link]([Link], key)
else:
return [Link]([Link], key)
def min_value(self, root):
current = root
while current and [Link]:
current = [Link]
return [Link] if current else None
def mirror(self, root):
if root:
[Link]([Link])
[Link]([Link])
[Link], [Link] = [Link], [Link]
def longest_path(self, root):
if root is None:
return 0
left = self.longest_path([Link])
right = self.longest_path([Link])
return max(left, right) + 1
#main
bst = BST()
values = list(map(int, input("Enter space-separated values to insert into BST: ").split()))
for val in values:
[Link] = [Link]([Link], val)
while True:
print("\n--- Binary Search Tree Operations ---")
print("1. Insert a new node")
print("2. Display In-order traversal")
print("3. Find longest path from root")
print("4. Find minimum value in BST")
print("5. Mirror the BST")
print("6. Search for a value")
print("7. Exit")
choice = input("Enter your choice (1-7): ")
if choice == "1":
val = int(input("Enter value to insert: "))
[Link] = [Link]([Link], val)
print(f"{val} inserted into BST.")
elif choice == "2":
print("In-order traversal of BST:")
bst.display_inorder([Link])
print()
elif choice == "3":
height = bst.longest_path([Link])
print(f"Longest path from root (Height): {height}")
elif choice == "4":
min_val = bst.min_value([Link])
print(f"Minimum value in the BST: {min_val}")
elif choice == "5":
[Link]([Link])
print("BST has been mirrored.")
elif choice == "6":
key = int(input("Enter value to search: "))
found = [Link]([Link], key)
if found:
print(f"Value {key} found in the BST.")
else:
print(f"Value {key} not found in the BST.")
elif choice == "7":
print("Exiting program.")
break
else:
print("Invalid choice! Please enter a number between 1 and 7.")
Output:
Assignment no: 5
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None
[Link] = False
class ThreadedBinaryTree:
def __init__(self):
[Link] = None
[Link] = None
def insert(self, root, data):
"""
Insert a node into the BST.
Time Complexity: O(log n) in a balanced BST, O(n) in a skewed BST.
Space Complexity: O(h), where h is the height of the tree (recursive calls).
"""
if root is None:
return Node(data)
if data < [Link]:
[Link] = [Link]([Link], data)
else:
[Link] = [Link]([Link], data)
return root
def inorder_traversal_bst(self, root):
"""
Perform in-order traversal of BST.
Time Complexity: O(n) (Each node is visited once).
Space Complexity: O(h) (Recursive calls, where h is the tree height).
"""
if root:
self.inorder_traversal_bst([Link])
print([Link], end=" ")
self.inorder_traversal_bst([Link])
def convert_to_threaded(self, root):
"""
Convert the BST into a Threaded Binary Tree using in-order traversal.
Time Complexity: O(n) (Each node is visited once).
Space Complexity: O(h) (Recursive calls, where h is the tree height).
"""
if root is None:
return
self.convert_to_threaded([Link])
if [Link] and [Link] is None:
[Link] = root
[Link] = True # Mark it as a threaded link
[Link] = root
self.convert_to_threaded([Link])
def leftmost(self, node):
"""
Find the leftmost node in the tree.
Time Complexity: O(h) (Worst case: skewed tree).
Space Complexity: O(1).
"""
while node and [Link]:
node = [Link]
return node
def inorder_traversal_threaded(self, root):
"""
Perform in-order traversal using threaded links.
Time Complexity: O(n) (Each node is visited once).
Space Complexity: O(1) (No extra space used).
"""
cur = [Link](root)
while cur:
print([Link], end=" ")
# If the node is threaded, move to its in-order successor
if [Link]:
cur = [Link]
else:
cur = [Link]([Link])
tree = ThreadedBinaryTree()
values = list(map(int, input("Enter space-separated values to insert into BST: ").split()))
for val in values:
[Link] = [Link]([Link], val)
print("\nBST In-order Traversal:")
tree.inorder_traversal_bst([Link])
print()
tree.convert_to_threaded([Link])
print("\nTBST In-order Traversal (Using Threads):")
tree.inorder_traversal_threaded([Link])
print()
Output:
Assignment no: 6
class Graph:
def __init__(self, num_landmarks):
self.num_landmarks = num_landmarks
[Link] = []
self.adj_matrix = [[0] * num_landmarks for _ in range(num_landmarks)]
self.adj_list = {i: [] for i in range(num_landmarks)}
def add_landmarks(self):
print("\nEnter the names of landmarks:")
for i in range(self.num_landmarks):
name = input(f"Enter name of landmark {i+1}: ").strip()
[Link](name)
def add_edges(self, num_edges):
print("\nEnter connections (as landmark names, e.g., 'college library'):")
for _ in range(num_edges):
u_name, v_name = input().strip().split()
if u_name in [Link] and v_name in [Link]:
u = [Link](u_name)
v = [Link](v_name)
self.adj_matrix[u][v] = 1
self.adj_matrix[v][u] = 1 # Undirected graph
self.adj_list[u].append(v)
self.adj_list[v].append(u)
else:
print("Invalid landmark names. Please enter valid ones.")
def print_adj_matrix(self):
print("\nAdjacency Matrix Representation:")
print(" " + " ".join(f"{name:<10}" for name in [Link]))
for i in range(self.num_landmarks):
row_values = " ".join(f"{self.adj_matrix[i][j]:<10}" for j in range(self.num_landmarks))
print(f"{[Link][i]:<10} {row_values}")
def print_adj_list(self):
print("\nAdjacency List Representation:")
for i in range(self.num_landmarks):
neighbors = [[Link][j] for j in self.adj_list[i]]
print(f"{[Link][i]:<10} → {', '.join(neighbors)}")
def dfs_util(self, node, visited):
visited[node] = True
print([Link][node], end=" ")
for neighbor in range(self.num_landmarks):
if self.adj_matrix[node][neighbor] == 1 and not visited[neighbor]:
self.dfs_util(neighbor, visited)
def dfs(self, start_name):
if start_name not in [Link]:
print("Invalid starting landmark for DFS.")
return
start = [Link](start_name)
visited = [False] * self.num_landmarks
print("\nDFS Traversal (Adjacency Matrix):")
self.dfs_util(start, visited)
print()
def bfs(self, start_name):
if start_name not in [Link]:
print("Invalid starting landmark for BFS.")
return
start = [Link](start_name)
visited = [False] * self.num_landmarks
queue = [start]
visited[start] = True
print("\nBFS Traversal (Adjacency List):")
while queue:
node = [Link](0)
print([Link][node], end=" ")
for neighbor in self.adj_list[node]:
if not visited[neighbor]:
visited[neighbor] = True
[Link](neighbor)
print()
# Main Execution
num_landmarks = int(input("Enter the number of landmarks: "))
graph = Graph(num_landmarks)
graph.add_landmarks()
num_edges = int(input("Enter the number of connections (edges): "))
graph.add_edges(num_edges)
graph.print_adj_matrix()
graph.print_adj_list()
start_landmark = input("\nEnter the starting landmark for traversal: ").strip()
[Link](start_landmark)
[Link](start_landmark)
Output:
