DS 1

class TrieNode:
def _init_(self):
self.c, self.e = {}, False
class Trie:
def _init_(self):
self.r = TrieNode()
def insert(self, w):
n = self.r
for ch in w:
if ch not in n.c: n.c[ch] = TrieNode()
n = n.c[ch]
n.e = True
def _auto(self, n, p):
res = [p] if n.e else []
for ch in n.c: res += self._auto(n.c[ch], p+ch)
return res
def autocomplete(self, p):
n = self.r
for ch in p:
if ch not in n.c: return []
n = n.c[ch]
return self._auto(n, p)
t = Trie()
for w in ["apple", "appetizer", "banana", "ban", "bat", "batman",
"ball", "bark", "bald", "bag", "baton", "badge"]:
[Link](w)
print([Link](input("Enter prefix: ")))
DS 2

import heapq
def dijkstra(graph, start, end):
q, dist, prev = [(0, start)], {n: float('inf') for n in graph}, {n: None for n
in graph}
dist[start] = 0
while q:
d, u = [Link](q)
if u == end: break
if d > dist[u]: continue
for v, w in graph[u].items():
alt = d + w
if alt < dist[v]:
dist[v], prev[v] = alt, u
[Link](q, (alt, v))
path, u = [], end
while u: [Link](0, u); u = prev[u]
return dist[end], path
graph = {'A': {'B': 10, 'C': 3}, 'B': {'A': 10, 'D': 2},
'C': {'A': 3, 'B': 1, 'D': 8}, 'D': {'B': 2, 'C': 8, 'E': 7}, 'E': {'D': 7}}
s, e = input("Start: "), input("End: ")
if s in graph and e in graph:
t, p = dijkstra(graph, s, e)
print(f"Shortest time: {t} min\nPath: {' -> '.join(p)}")
else:
print("Invalid start or end point.")
DS 3
def find(parent, i):
if parent[i] != i:
parent[i] = find(parent, parent[i]) # Path compression
return parent[i]
def union(parent, rank, x, y):
root_x, root_y = find(parent, x), find(parent, y)
if root_x != root_y:
if rank[root_x] < rank[root_y]:
parent[root_x] = root_y
elif rank[root_x] > rank[root_y]:
parent[root_y] = root_x
else:
parent[root_y] = root_x
rank[root_x] += 1
def kruskal(edges, n):
[Link](key=lambda x: x[2])
parent, rank = list(range(n)), [0]*n
mst, total_cost = [], 0
for u, v, cost in edges:
if find(parent, u) != find(parent, v):
union(parent, rank, u, v)
[Link]((u, v, cost))
total_cost += cost
if len(mst) == n - 1:
break
return mst, total_cost
n, e = map(int, input("Enter number of cities and connections:
").split())
edges = [tuple(map(int, input().split())) for _ in range(e)]
mst, total_cost = kruskal(edges, n)
print("\nMST connections:")
for u, v, cost in mst:
print(f"{u} -- {v} cost: {cost}")
print(f"Total cost: {total_cost}")

DS 4
def is_safe(board, row, col, n):
for i in range(row):
if board[i][col] == 1:
return False
for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
if board[i][j] == 1:
return False
for i, j in zip(range(row-1, -1, -1), range(col+1, n)):
if board[i][j] == 1:
return False
return True
def solve_n_queens(board, row, n, solutions):
if row == n:
[Link](["".join("Q" if cell == 1 else "." for cell in r) for r
in board])
return
for col in range(n):
if is_safe(board, row, col, n):
board[row][col] = 1
solve_n_queens(board, row + 1, n, solutions)
board[row][col] = 0
n = int(input("Enter the size of the chessboard (N for N-Queens): "))
board = [[0 for _ in range(n)] for _ in range(n)]
solutions = []
solve_n_queens(board, 0, n, solutions)

print(f"\nNumber of solutions for {n}-Queens: {len(solutions)}")

DS 5
class SegmentTree:
def __init__(self, data):
self.n = len(data)
[Link] = [0] * (2 * self.n)
[Link][self.n:] = data
for i in range(self.n - 1, 0, -1):
[Link][i] = [Link][2*i] + [Link][2*i+1]
def range_sum(self, l, r):
l += self.n; r += self.n; res = 0
while l < r:
if l % 2: res += [Link][l]; l += 1
if r % 2: r -= 1; res += [Link][r]
l //= 2; r //= 2
return res
def update(self, i, val):
i += self.n; [Link][i] = val
while i > 1:
i //= 2
[Link][i] = [Link][2*i] + [Link][2*i+1]
def display(self):
print("\nTree:", [Link])
print("Leaves:", [Link][self.n:])
n = int(input("Students: "))
seg = SegmentTree(list(map(int, input("Scores: ").split())))
while (c := input("\[Link] [Link] [Link] [Link]: ")) != "4":
if c == "1":
l, r = map(int, input("Range [l r): ").split())
print("Sum:", seg.range_sum(l, r))
 elif c == "2":
i, v = map(int, input("Index NewScore: ").split())
[Link](i, v)
print("Updated.")
elif c == "3":
[Link]()
else:
print("Invalid.")

DS 6
class Point:
def __init__(self, name, x, y): [Link], self.x, self.y = name, x, y
class Rectangle:
def __init__(self, x, y, w, h): self.x, self.y, self.w, self.h = x, y, w, h
def contains(self, p): return self.x - self.w <= p.x <= self.x + self.w
and self.y - self.h <= p.y <= self.y + self.h
class Quadtree:
def __init__(self, boundary, cap):
self.b, [Link], [Link], [Link] = boundary, cap, [], False
def subdivide(self):
x, y, w, h = self.b.x, self.b.y, self.b.w, self.b.h
[Link] = Quadtree(Rectangle(x + w/2, y - h/2, w/2, h/2), [Link])
[Link] = Quadtree(Rectangle(x - w/2, y - h/2, w/2, h/2), [Link])
[Link] = Quadtree(Rectangle(x + w/2, y + h/2, w/2, h/2), [Link])
[Link] = Quadtree(Rectangle(x - w/2, y + h/2, w/2, h/2), [Link])
[Link] = True
def insert(self, p):
if not [Link](p): return False
if len([Link]) < [Link]: [Link](p); return True
if not [Link]: [Link]()
return [Link](p) or [Link](p) or [Link](p) or
[Link](p)
def search(self, x, y):
for p in [Link]:
 if p.x == x and p.y == y: return [Link]
if [Link]:
if x >= self.b.x: return [Link](x, y) if y >= self.b.y else
[Link](x, y)
else: return [Link](x, y) if y >= self.b.y else
[Link](x, y)
return None
print("GIS with Quadtree")
qt = Quadtree(Rectangle(0, 0, 100, 100), 4)
for _ in range(int(input("No. of cities: "))):
name = input("City name: ")
x, y = map(int, input("x y: ").split())
[Link](Point(name, x, y))
while (c := input("\[Link] [Link]: ")) != "2":
if c == "1":
x, y = map(int, input("Search x y: ").split())
res = [Link](x, y)
print(f"Found: {res}" if res else "Not found.")
else:
print("Invalid.")