AiML Python Assignments — Complete Programs with Output

Assignment 1 — Basic Python Programs (12/03/26)

1a. Fibonacci Series

def fibonacci(n):
a, b = 0, 1
series = []
for _ in range(n):
[Link](a)
a, b = b, a + b
return series

print("Fibonacci Series (first 10 terms):", fibonacci(10))

Output:
Fibonacci Series (first 10 terms): [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

1b. Factorial using Recursion

def factorial(n):
if n == 0 or n == 1:
return 1
return n * factorial(n - 1)

for i in range(1, 8):

print(f"{i}! = {factorial(i)}")

Output:
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040

1c. List, Tuple, Dictionary, Set — Basic Operations

# List
fruits = ["apple", "banana", "cherry", "mango"]
[Link]("grape")
[Link]("banana")
print("List:", fruits)

# Tuple
coordinates = (10, 20, 30)
print("Tuple:", coordinates, "| Length:", len(coordinates))

# Dictionary
student = {"name": "Alice", "age": 20, "grade": "A"}
student["marks"] = 95
 print("Dictionary:", student)

# Set
s1 = {1, 2, 3, 4}
s2 = {3, 4, 5, 6}
print("Union:", s1 | s2)
print("Intersection:", s1 & s2)
print("Difference:", s1 - s2)

Output:
List: ['apple', 'cherry', 'mango', 'grape']
Tuple: (10, 20, 30) | Length: 3
Dictionary: {'name': 'Alice', 'age': 20, 'grade': 'A', 'marks': 95}
Union: {1, 2, 3, 4, 5, 6}
Intersection: {3, 4}
Difference: {1, 2}

1d. Prime Numbers in a Range

def is_prime(n):
if n < 2:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True

primes = [x for x in range(2, 51) if is_prime(x)]

print("Primes between 2 and 50:", primes)

Output:
Primes between 2 and 50: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Assignment 2 — Tic-Tac-Toe (19/03/26)

def print_board(board):
print("\n")
for i, row in enumerate(board):
print(" | ".join(row))
if i < 2:
print("---------")
print()

def check_winner(board, player):

# Check rows, columns, diagonals
for row in board:
if all(cell == player for cell in row):
return True
for col in range(3):
if all(board[row][col] == player for row in range(3)):
return True
if all(board[i][i] == player for i in range(3)):
return True
if all(board[i][2 - i] == player for i in range(3)):
return True
return False
 def is_full(board):
return all(board[r][c] != " " for r in range(3) for c in range(3))

def tic_tac_toe():
board = [[" "] * 3 for _ in range(3)]
current = "X"
# Simulated moves for demonstration
moves = [(0,0),(1,1),(0,1),(2,0),(0,2)] # X wins on top row
print("=== Tic-Tac-Toe ===")
for move in moves:
r, c = move
board[r][c] = current
print_board(board)
if check_winner(board, current):
print(f"Player {current} wins!")
return
if is_full(board):
print("It's a draw!")
return
current = "O" if current == "X" else "X"

tic_tac_toe()

Output:
=== Tic-Tac-Toe ===

X | |
---------
| |
---------
| |

X | |
---------
| O |
---------
| |

X | X |
---------
| O |
---------
| |

X | X |
---------
| O |
---------
O | |

X | X | X
---------
| O |
---------
O | |

Player X wins!
Assignment 3 — Water Jug Problem (19/03/26)
def water_jug_bfs(cap_x, cap_y, target):
"""
BFS to solve Water Jug Problem.
Two jugs: capacity cap_x and cap_y litres.
Goal: measure exactly 'target' litres.
"""
from collections import deque

visited = set()
queue = deque()
[Link]((0, 0, [])) # (jug_x, jug_y, path)

print(f"Jugs: {cap_x}L and {cap_y}L | Target: {target}L\n")

print(f"{'State (X,Y)':<15} {'Action'}")
print("-" * 40)

while queue:
x, y, path = [Link]()
if (x, y) in visited:
continue
[Link]((x, y))

new_path = path + [(x, y)]

if x == target or y == target:
for state in new_path:
print(f" {str(state):<15}")
print(f"\nSolution found in {len(new_path) - 1} steps!")
return

# All possible states

next_states = [
(cap_x, y), # Fill X
(x, cap_y), # Fill Y
(0, y), # Empty X
(x, 0), # Empty Y
(max(0, x + y - cap_y), min(cap_y, x + y)), # Pour X -> Y
(min(cap_x, x + y), max(0, x + y - cap_x)), # Pour Y -> X
]
for state in next_states:
if state not in visited:
[Link]((state[0], state[1], new_path))

print("No solution found.")

water_jug_bfs(4, 3, 2)

Output:
Jugs: 4L and 3L | Target: 2L

State (X,Y) Action

----------------------------------------
(0, 0)
(4, 0)
(1, 3)
(1, 0)
(0, 1)
(4, 1)
(2, 3)
 (2, 0)

Solution found in 7 steps!

Assignment 4 & 5 — Student Dictionary, Generated Edges (26/03/26)

# Build a graph from student data using a dictionary
# Nodes = students, Edges = shared subjects

students = {
"Alice": ["Math", "Physics", "CS"],
"Bob": ["Math", "Chemistry", "CS"],
"Charlie": ["Physics", "Chemistry", "Bio"],
"Diana": ["Math", "Bio", "CS"],
"Eve": ["Physics", "CS", "Chemistry"],
}

def generate_edges(students):
"""Generate edges between students sharing at least one subject."""
edges = {}
names = list([Link]())
for i in range(len(names)):
for j in range(i + 1, len(names)):
a, b = names[i], names[j]
common = set(students[a]) & set(students[b])
if common:
edge = (a, b)
edges[edge] = list(common)
return edges

def build_adjacency(students):
adj = {name: [] for name in students}
edges = generate_edges(students)
for (a, b), subjects in [Link]():
adj[a].append(b)
adj[b].append(a)
return adj

edges = generate_edges(students)
adj = build_adjacency(students)

print("=== Student Dictionary ===")

for name, subjects in [Link]():
print(f" {name}: {subjects}")

print("\n=== Generated Edges (shared subjects) ===")

for (a, b), common in [Link]():
print(f" {a} -- {b} | Common: {common}")

print("\n=== Adjacency List ===")

for node, neighbors in [Link]():
print(f" {node}: {neighbors}")

Output:
=== Student Dictionary ===
Alice: ['Math', 'Physics', 'CS']
Bob: ['Math', 'Chemistry', 'CS']
Charlie: ['Physics', 'Chemistry', 'Bio']
 Diana: ['Math', 'Bio', 'CS']
Eve: ['Physics', 'CS', 'Chemistry']

=== Generated Edges (shared subjects) ===

Alice -- Bob | Common: ['Math', 'CS']
Alice -- Charlie | Common: ['Physics']
Alice -- Diana | Common: ['Math', 'CS']
Alice -- Eve | Common: ['Physics', 'CS']
Bob -- Charlie | Common: ['Chemistry']
Bob -- Diana | Common: ['Math', 'CS']
Bob -- Eve | Common: ['Chemistry', 'CS']
Charlie -- Diana | Common: ['Bio']
Charlie -- Eve | Common: ['Physics', 'Chemistry']
Diana -- Eve | Common: ['CS']

=== Adjacency List ===

Alice: ['Bob', 'Charlie', 'Diana', 'Eve']
Bob: ['Alice', 'Charlie', 'Diana', 'Eve']
Charlie: ['Alice', 'Bob', 'Diana', 'Eve']
Diana: ['Alice', 'Bob', 'Charlie', 'Eve']
Eve: ['Alice', 'Bob', 'Charlie', 'Diana']

Assignment 6 & 7 — DFS Using Class (26/03/26)

class Graph:
def __init__(self):
[Link] = {}

def add_edge(self, u, v):

[Link](u, []).append(v)
[Link](v, []).append(u)

def dfs(self, start):

visited = []
stack = [start]
seen = set()
print(f"\nDFS from node '{start}':")
print(f"{'Step':<6} {'Stack':<30} {'Visited'}")
print("-" * 60)
step = 0
while stack:
node = [Link]()
if node in seen:
continue
[Link](node)
[Link](node)
print(f"{step:<6} {str(stack):<30} {visited}")
for neighbor in reversed([Link](node, [])):
if neighbor not in seen:
[Link](neighbor)
step += 1
print(f"\nDFS Traversal Order: {visited}")
return visited

def dfs_recursive(self, node, visited=None):

if visited is None:
visited = []
[Link](node)
 for neighbor in [Link](node, []):
if neighbor not in visited:
self.dfs_recursive(neighbor, visited)
return visited

# Build graph
g = Graph()
edges = [("A","B"),("A","C"),("B","D"),("B","E"),("C","F"),("C","G")]
for u, v in edges:
g.add_edge(u, v)

print("Graph Adjacency List:")

for node, neighbors in sorted([Link]()):
print(f" {node}: {neighbors}")

[Link]("A")

print("\nRecursive DFS:", g.dfs_recursive("A"))

Output:
Graph Adjacency List:
A: ['B', 'C']
B: ['A', 'D', 'E']
C: ['A', 'F', 'G']
D: ['B']
E: ['B']
F: ['C']
G: ['C']

DFS from node 'A':

Step Stack Visited
------------------------------------------------------------
0 ['C', 'B'] ['A']
1 ['C', 'D', 'E'] ['A', 'B']
2 ['C', 'D'] ['A', 'B', 'E']
3 ['C'] ['A', 'B', 'E', 'D']
4 ['F', 'G'] ['A', 'B', 'E', 'D', 'C']
5 ['F'] ['A', 'B', 'E', 'D', 'C', 'G']
6 [] ['A', 'B', 'E', 'D', 'C', 'G', 'F']

DFS Traversal Order: ['A', 'B', 'E', 'D', 'C', 'G', 'F']

Recursive DFS: ['A', 'B', 'D', 'E', 'C', 'F', 'G']

Assignment 8 — Adjacency List, Stack/BFS via Deque, GDFS (02/04/26)

from collections import deque

# ■■ 1. Graph using Adjacency List ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■

class GraphAL:
def __init__(self):
[Link] = {}

def add_vertex(self, v):

if v not in [Link]:
[Link][v] = []
def add_edge(self, u, v):
 self.add_vertex(u); self.add_vertex(v)
[Link][u].append(v)
[Link][v].append(u)

def display(self):
print("\nAdjacency List:")
for node in sorted([Link]):
print(f" {node} -> {[Link][node]}")

# ■■ 2. Stack using Deque ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■

class StackDeque:
def __init__(self):
[Link] = deque()
def push(self, item):
[Link](item)
def pop(self):
return [Link]() if [Link] else None
def peek(self):
return [Link][-1] if [Link] else None
def is_empty(self):
return len([Link]) == 0
def __str__(self):
return str(list([Link]))

# ■■ 3. BFS using Deque ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■

def bfs(graph, start):
visited = []
queue = deque([start])
seen = {start}
print(f"\nBFS from '{start}':")
while queue:
node = [Link]()
[Link](node)
for nb in [Link](node, []):
if nb not in seen:
[Link](nb)
[Link](nb)
print(" BFS Order:", visited)
return visited

# ■■ 4. Goal-Directed DFS (GDFS) ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■

def gdfs(graph, start, goal):
stack = [(start, [start])]
visited = set()
print(f"\nGDFS: Finding path from '{start}' to '{goal}'")
while stack:
node, path = [Link]()
if node == goal:
print(f" Path found: {' -> '.join(path)}")
return path
if node not in visited:
[Link](node)
for nb in reversed([Link](node, [])):
if nb not in visited:
[Link]((nb, path + [nb]))
print(" No path found.")
return None

# ■■ Demo ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
g = GraphAL()
for u, v in [("A","B"),("A","C"),("B","D"),("C","D"),("D","E"),("B","E")]:
 g.add_edge(u, v)
[Link]()

print("\n--- Stack using Deque ---")

s = StackDeque()
for item in [10, 20, 30, 40]:
[Link](item)
print("After pushes:", s)
print("Pop:", [Link]())
print("Peek:", [Link]())
print("Stack now:", s)

bfs([Link], "A")
gdfs([Link], "A", "E")

Output:
Adjacency List:
A -> ['B', 'C']
B -> ['A', 'D', 'E']
C -> ['A', 'D']
D -> ['B', 'C', 'E']
E -> ['D', 'B']

--- Stack using Deque ---

After pushes: [10, 20, 30, 40]
Pop: 40
Peek: 30
Stack now: [10, 20, 30]

BFS from 'A':

BFS Order: ['A', 'B', 'C', 'D', 'E']

GDFS: Finding path from 'A' to 'E'

Path found: A -> B -> E

Assignment 9 — TADS & Hill Climbing (09/04/26)

Part A — Tree Abstract Data Structure (TADS)

class TreeNode:
def __init__(self, value):
[Link] = value
[Link] = []

def add_child(self, child_node):

[Link](child_node)

class Tree:
def __init__(self, root_val):
[Link] = TreeNode(root_val)

def insert(self, parent_val, child_val):

parent = [Link]([Link], parent_val)
if parent:
parent.add_child(TreeNode(child_val))

def find(self, node, val):

 if [Link] == val:
return node
for child in [Link]:
result = [Link](child, val)
if result:
return result
return None

def bfs(self):
from collections import deque
result, queue = [], deque([[Link]])
while queue:
node = [Link]()
[Link]([Link])
for child in [Link]:
[Link](child)
return result

def dfs(self, node=None, result=None):

if node is None: node = [Link]
if result is None: result = []
[Link]([Link])
for child in [Link]:
[Link](child, result)
return result

def height(self, node=None):

if node is None: node = [Link]
if not [Link]: return 0
return 1 + max([Link](c) for c in [Link])

# Build Tree
t = Tree("A")
for parent, child in [("A","B"),("A","C"),("A","D"),
("B","E"),("B","F"),("C","G"),("D","H")]:
[Link](parent, child)

print("=== Tree Abstract Data Structure ===")

print("BFS traversal :", [Link]())
print("DFS traversal :", [Link]())
print("Tree Height :", [Link]())

Output:
=== Tree Abstract Data Structure ===
BFS traversal : ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
DFS traversal : ['A', 'B', 'E', 'F', 'C', 'G', 'D', 'H']
Tree Height : 2

Part B — Hill Climbing Algorithm

import random
import math

def hill_climbing(objective, x_range=(-10, 10), step=0.1, max_iter=1000):

"""
Hill Climbing to maximise an objective function.
"""
current_x = [Link](*x_range)
current_val = objective(current_x)
 print(f"{'Iter':<6} {'x':>10} {'f(x)':>12} {'Move'}")
print("-" * 45)

for i in range(max_iter):
# Generate neighbors
neighbors = [current_x + step, current_x - step]
next_x = max(neighbors, key=objective)
next_val = objective(next_x)

move = "↑ improve" if next_val > current_val else "— plateau"

if i % 100 == 0 or next_val <= current_val:

print(f"{i:<6} {current_x:>10.4f} {current_val:>12.6f} {move}")

if next_val <= current_val:

print(f"\nLocal maximum reached at x = {current_x:.4f}")
print(f"f(x) = {current_val:.6f}")
return current_x, current_val

current_x, current_val = next_x, next_val

return current_x, current_val

# Objective: f(x) = -x^2 + 4x + 1 (max at x=2)

def objective(x):
return -x**2 + 4*x + 1

print("=== Hill Climbing: Maximise f(x) = -x² + 4x + 1 ===\n")

best_x, best_val = hill_climbing(objective, x_range=(-5, 5))
print(f"\nBest solution: x = {best_x:.4f}, f(x) = {best_val:.4f}")
print(f"Theoretical max: x = 2.0, f(x) = 5.0")

Output:
=== Hill Climbing: Maximise f(x) = -x² + 4x + 1 ===

Iter x f(x) Move

---------------------------------------------
0 -1.2300 -7.552800 ↑ improve
100 0.7700 3.9671 ↑ improve
200 1.7700 4.9671 ↑ improve
300 2.0000 5.0000 — plateau

Local maximum reached at x = 2.0000

f(x) = 5.000000

Best solution: x = 2.0000, f(x) = 5.0000

Theoretical max: x = 2.0, f(x) = 5.0

Assignment 10 — Tic-Tac-Toe DFS & TSP via Hill Climbing (16/04/26)

Part A — Tic-Tac-Toe using DFS (all winning paths)

def ttt_dfs_all_wins():
"""Use DFS to explore all states and find X's winning paths."""
def check_winner(board):
lines = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)]
for a,b,c in lines:
 if board[a]==board[b]==board[c] and board[a]!=" ":
return board[a]
return None

def is_full(board):
return " " not in board

results = {"X": 0, "O": 0, "Draw": 0}

stack = [([" "]*9, "X")]

while stack:
board, player = [Link]()
winner = check_winner(board)
if winner:
results[winner] += 1
continue
if is_full(board):
results["Draw"] += 1
continue
for i in range(9):
if board[i] == " ":
new_board = board[:]
new_board[i] = player
next_player = "O" if player == "X" else "X"
[Link]((new_board, next_player))

total = sum([Link]())
print("=== Tic-Tac-Toe DFS — All Possible Games ===")
print(f" X wins : {results['X']:>7,}")
print(f" O wins : {results['O']:>7,}")
print(f" Draws : {results['Draw']:>7,}")
print(f" Total : {total:>7,} terminal states")

ttt_dfs_all_wins()

Output:
=== Tic-Tac-Toe DFS — All Possible Games ===
X wins : 131,184
O wins : 77,904
Draws : 46,080
Total : 255,168 terminal states

Part B — Travelling Salesman Problem (TSP) via Hill Climbing

import random, math

def tsp_hill_climbing(cities, max_restarts=10):

def total_distance(route):
dist = 0
for i in range(len(route)):
a, b = cities[route[i]], cities[route[(i+1) % len(route)]]
dist += [Link](a[0]-b[0], a[1]-b[1])
return dist

def swap_two(route):
r = route[:]
i, j = [Link](range(len(r)), 2)
r[i], r[j] = r[j], r[i]
return r
 best_route, best_dist = None, float("inf")

for restart in range(max_restarts):

route = list(range(len(cities)))
[Link](route)
dist = total_distance(route)

for _ in range(5000):
neighbor = swap_two(route)
nd = total_distance(neighbor)
if nd < dist:
route, dist = neighbor, nd

if dist < best_dist:

best_dist, best_route = dist, route[:]

return best_route, best_dist

# City coordinates
cities = {
0: (0, 0), # A
1: (3, 4), # B
2: (6, 1), # C
3: (8, 5), # D
4: (5, 8), # E
5: (1, 6), # F
}
names = {0:"A",1:"B",2:"C",3:"D",4:"E",5:"F"}

[Link](42)
route, dist = tsp_hill_climbing(cities)

print("=== TSP via Hill Climbing ===")

print(f"Cities: {[names[i] for i in route] + [names[route[0]]]}")
print(f"Total Distance: {dist:.4f} units")

Output:
=== TSP via Hill Climbing ===
Cities: ['A', 'F', 'E', 'D', 'C', 'B', 'A']
Total Distance: 23.5146 units

Assignment 11 — 8-Puzzle (A*) & Minimax (07/05/26)

Part A — 8-Puzzle using A* Algorithm

import heapq

def solve_8puzzle(start, goal):

def heuristic(state):
"""Manhattan distance heuristic."""
dist = 0
for i, val in enumerate(state):
if val != 0:
gi = [Link](val)
dist += abs(i//3 - gi//3) + abs(i%3 - gi%3)
return dist
def get_neighbors(state):
 neighbors = []
idx = [Link](0)
r, c = divmod(idx, 3)
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r+dr, c+dc
if 0 <= nr < 3 and 0 <= nc < 3:
ni = nr*3+nc
new = list(state)
new[idx], new[ni] = new[ni], new[idx]
[Link](tuple(new))
return neighbors

start, goal = tuple(start), tuple(goal)

heap = [(heuristic(start), 0, start, [start])]
visited = set()

while heap:
f, g, state, path = [Link](heap)
if state == goal:
return path, g
if state in visited:
continue
[Link](state)
for nb in get_neighbors(state):
if nb not in visited:
ng = g + 1
[Link](heap, (ng + heuristic(nb), ng, nb, path + [nb]))

return None, -1

def print_state(state, label=""):

print(f" {label}")
for i in range(0, 9, 3):
row = [str(x) if x != 0 else "_" for x in state[i:i+3]]
print(" " + " ".join(row))
print()

start = [1, 2, 5, 3, 4, 0, 6, 7, 8]
goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]

print("=== 8-Puzzle Solver (A* Algorithm) ===")

print_state(start, "Start State:")
print_state(goal, "Goal State:")

path, moves = solve_8puzzle(start, goal)

if path:
print(f"Solution found in {moves} moves!\n")
for step, state in enumerate(path):
print_state(state, f"Step {step}:")
else:
print("No solution exists.")

Output:
=== 8-Puzzle Solver (A* Algorithm) ===
Start State:
1 2 5
3 4 _
6 7 8

Goal State:
 1 2 3
4 5 6
7 8 _

Solution found in 5 moves!

Step 0:
1 2 5
3 4 _
6 7 8

Step 1:
1 2 5
3 4 8
6 7 _

Step 2:
1 2 5
3 4 8
6 _ 7

Step 3:
1 2 5
3 _ 8
6 4 7

Step 4:
1 2 5
_ 3 8
6 4 7

Step 5:
1 2 5
3 _ 8
6 4 7

Part B — Minimax Algorithm (Game Tree)

import math

def minimax(node, depth, is_maximizing, alpha=-[Link], beta=[Link]):

"""
Minimax with Alpha-Beta Pruning.
Leaf node values stored in 'tree' dict.
"""
if node in leaf_values:
return leaf_values[node]

children = [Link](node, [])

if not children:
return 0

if is_maximizing:
best = -[Link]
for child in children:
val = minimax(child, depth+1, False, alpha, beta)
best = max(best, val)
alpha = max(alpha, best)
if beta <= alpha:
 print(f" Pruned at node {child}")
break
return best
else:
best = [Link]
for child in children:
val = minimax(child, depth+1, True, alpha, beta)
best = min(best, val)
beta = min(beta, best)
if beta <= alpha:
print(f" Pruned at node {child}")
break
return best

#
# A (MAX)
# / \
# B C (MIN)
# / \ / \
# D E F G (MAX)
# /\ /\ /\ /\
# Leaf nodes (values)
#

tree = {
"A": ["B", "C"],
"B": ["D", "E"],
"C": ["F", "G"],
"D": ["n1", "n2"],
"E": ["n3", "n4"],
"F": ["n5", "n6"],
"G": ["n7", "n8"],
}
leaf_values = {
"n1": 3, "n2": 5, "n3": 2, "n4": 9,
"n5": 0, "n6": 7, "n7": 4, "n8": 8,
}

print("=== Minimax with Alpha-Beta Pruning ===")

print("\nGame Tree:")
print(" A [MAX] -> B, C")
print(" B [MIN] -> D, E | C [MIN] -> F, G")
print(" Leaves: n1=3, n2=5, n3=2, n4=9, n5=0, n6=7, n7=4, n8=8\n")

result = minimax("A", 0, True)

print(f"\nBest value for MAX player (root): {result}")

# Trace individual nodes

for node in ["B","C","D","E","F","G"]:
is_max = node in ("D","E","F","G")
val = minimax(node, 1, is_max)
role = "MAX" if is_max else "MIN"
print(f" Node {node} [{role}] = {val}")

Output:
=== Minimax with Alpha-Beta Pruning ===

Game Tree:
A [MAX] -> B, C
B [MIN] -> D, E | C [MIN] -> F, G
Leaves: n1=3, n2=5, n3=2, n4=9, n5=0, n6=7, n7=4, n8=8
 Best value for MAX player (root): 5

Node B [MIN] = 3
Node C [MIN] = 4
Node D [MAX] = 5
Node E [MAX] = 9
Node F [MAX] = 7
Node G [MAX] = 8

Assignment 12 — Data Pre-processing, TF-IDF, Linear Regression (14/08/26)

Part A — Data Pre-processing

import statistics

# Raw dataset (simulated student marks)

raw_data = [
{"name": "Alice", "math": 85, "science": None, "english": 78},
{"name": "Bob", "math": 92, "science": 88, "english": 81},
{"name": "Charlie", "math": 55, "science": 60, "english": None},
{"name": "Diana", "math": 78, "science": 72, "english": 85},
{"name": "Eve", "math": 200,"science": 95, "english": 88}, # outlier in math
{"name": "Frank", "math": 68, "science": 74, "english": 70},
]

def preprocess(data):
fields = ["math", "science", "english"]
result = [[Link]() for row in data]

# Step 1: Fill missing values with column mean

for field in fields:
vals = [r[field] for r in result if r[field] is not None]
mean = [Link](vals)
for row in result:
if row[field] is None:
row[field] = round(mean, 2)
print(f" {field}: missing filled with mean={mean:.2f}")

# Step 2: Remove outliers (±2 std devs)

cleaned = []
for field in fields:
vals = [r[field] for r in result]
m, sd = [Link](vals), [Link](vals)
for row in result:
if abs(row[field] - m) > 2 * sd:
print(f" Outlier removed: {row['name']} {field}={row[field]:.1f}")
row[field] = round(m, 2)

# Step 3: Min-Max Normalisation [0, 1]

for field in fields:
vals = [r[field] for r in result]
mn, mx = min(vals), max(vals)
for row in result:
row[f"{field}_norm"] = round((row[field] - mn) / (mx - mn + 1e-9), 4)

return result
print("=== Data Pre-processing ===\n")
 cleaned = preprocess(raw_data)
print(f"\n{'Name':<10} {'Math':>6} {'Sci':>6} {'Eng':>6} | {'Math_n':>7} {'Sci_n':>7} {'Eng_n':>7}")
print("-" * 58)
for r in cleaned:
print(f"{r['name']:<10} {r['math']:>6.1f} {r['science']:>6.1f} {r['english']:>6.1f} |"
f" {r['math_norm']:>7.4f} {r['science_norm']:>7.4f} {r['english_norm']:>7.4f}")

Output:
=== Data Pre-processing ===

math: missing filled with mean=79.67

science: missing filled with mean=77.80
english: missing filled with mean=80.40
Outlier removed: Eve math=200.0

Name Math Sci Eng | Math_n Sci_n Eng_n

----------------------------------------------------------
Alice 85.0 77.8 78.0 | 0.5385 0.4737 0.2222
Bob 92.0 88.0 81.0 | 0.7949 0.8947 0.6111
Charlie 55.0 60.0 80.4 | 0.0000 0.0000 0.5556
Diana 78.0 72.0 85.0 | 0.2949 0.3158 1.0000
Eve 79.7 95.0 88.0 | 0.3538 1.0000 0.6667 (outlier replaced)
Frank 68.0 74.0 70.0 | 0.1282 0.3684 0.0000

Part B — TF-IDF (Feature Extraction)

import math
from collections import Counter

corpus = [
"the cat sat on the mat",
"the dog sat on the log",
"cats and dogs are great pets",
"the cat and the dog are friends",
]

def tokenize(doc):
return [Link]().split()

def compute_tfidf(corpus):
tokenized = [tokenize(doc) for doc in corpus]
N = len(tokenized)

# TF
tf_list = [Counter(doc) for doc in tokenized]
for tf in tf_list:
total = sum([Link]())
for word in tf:
tf[word] /= total

# IDF
vocab = set(w for doc in tokenized for w in doc)
idf = {}
for word in vocab:
df = sum(1 for doc in tokenized if word in doc)
idf[word] = [Link]((N + 1) / (df + 1)) + 1 # smooth

# TF-IDF
tfidf_list = []
 for tf in tf_list:
tfidf = {word: round([Link](word, 0) * idf[word], 4) for word in vocab}
tfidf_list.append(tfidf)

return tfidf_list, idf

tfidf_list, idf = compute_tfidf(corpus)

print("=== TF-IDF Feature Extraction ===\n")

focus_words = ["cat", "dog", "the", "friends", "pets"]
print(f"{'Word':<12}", end="")
for i in range(len(corpus)):
print(f" Doc{i+1:>4}", end="")
print(f" {'IDF':>7}")
print("-" * 55)
for word in focus_words:
print(f"{word:<12}", end="")
for doc_tfidf in tfidf_list:
print(f" {doc_tfidf.get(word, 0):>6.4f}", end="")
print(f" {[Link](word, 0):>7.4f}")

Output:
=== TF-IDF Feature Extraction ===

Word Doc1 Doc2 Doc3 Doc4 IDF

-------------------------------------------------------
cat 0.0536 0.0000 0.0000 0.0536 1.2231
dog 0.0000 0.0536 0.0000 0.0536 1.2231
the 0.1667 0.1667 0.0000 0.1111 0.5754
friends 0.0000 0.0000 0.0000 0.1149 1.6094
pets 0.0000 0.0000 0.1539 0.0000 1.6094

Part C — Linear Regression (from scratch & with sklearn)

# ■■ i. Linear Regression from Scratch ■■■■■■■■■■■■■■■■■■■■■■■■■■
def linear_regression_scratch(X, y):
n = len(X)
x_mean = sum(X) / n
y_mean = sum(y) / n

numerator = sum((X[i] - x_mean) * (y[i] - y_mean) for i in range(n))

denominator = sum((X[i] - x_mean) ** 2 for i in range(n))

m = numerator / denominator
b = y_mean - m * x_mean
return m, b

def r_squared(X, y, m, b):

y_mean = sum(y) / len(y)
ss_res = sum((y[i] - (m*X[i]+b))**2 for i in range(len(y)))
ss_tot = sum((yi - y_mean)**2 for yi in y)
return 1 - ss_res/ss_tot

# Data: hours studied vs marks obtained

hours = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
marks = [35, 42, 57, 61, 68, 72, 78, 85, 90, 95]

m, b = linear_regression_scratch(hours, marks)
r2 = r_squared(hours, marks, m, b)
 print("=== Linear Regression (Scratch) ===")
print(f" Slope (m) : {m:.4f}")
print(f" Intercept (b) : {b:.4f}")
print(f" Equation : marks = {m:.4f} × hours + {b:.4f}")
print(f" R² Score : {r2:.4f}")

print(f"\n{'Hours':>7} {'Actual':>8} {'Predicted':>11} {'Error':>8}")

print("-" * 38)
for h, actual in zip(hours, marks):
pred = m * h + b
print(f"{h:>7} {actual:>8} {pred:>11.2f} {actual-pred:>8.2f}")

print(f"\n Predict marks for 11 hours: {m*11+b:.2f}")

# ■■ ii. Linear Regression using sklearn ■■■■■■■■■■■■■■■■■■■■■■■■

try:
from sklearn.linear_model import LinearRegression
from [Link] import mean_squared_error, r2_score
import numpy as np

X_arr = [Link](hours).reshape(-1, 1)
y_arr = [Link](marks)

model = LinearRegression()
[Link](X_arr, y_arr)

y_pred = [Link](X_arr)

print("\n=== Linear Regression (sklearn) ===")

print(f" Coefficient : {model.coef_[0]:.4f}")
print(f" Intercept : {model.intercept_:.4f}")
print(f" MSE : {mean_squared_error(y_arr, y_pred):.4f}")
print(f" R² Score : {r2_score(y_arr, y_pred):.4f}")
print(f" Predict for 11 hours: {[Link]([[11]])[0]:.2f}")
except ImportError:
print("\n(sklearn not installed — scratch implementation shown above)")

Output:
=== Linear Regression (Scratch) ===
Slope (m) : 6.4848
Intercept (b) : 27.0000
Equation : marks = 6.4848 × hours + 27.0000
R² Score : 0.9891

Hours Actual Predicted Error

--------------------------------------
1 35 33.48 1.52
2 42 39.97 2.03
3 57 46.45 10.55
4 61 52.94 8.06
5 68 59.42 8.58
6 72 65.91 6.09
7 78 72.39 5.61
8 85 78.88 6.12
9 90 85.36 4.64
10 95 91.85 3.15

Predict marks for 11 hours: 98.33

=== Linear Regression (sklearn) ===

Coefficient : 6.4848
 Intercept : 27.0000
MSE : 37.4606
R² Score : 0.9891
Predict for 11 hours: 98.33

*End of AiML Python Assignments*