CYCLE 1
[Link] assignment problem using brute force Method
import itertools
def brute_force_assignment(cost_matrix):
n = len(cost_matrix)
# Generate all possible assignments (permutations)
permutations = [Link](range(n))
min_cost = float('inf')
best_assignment = None
# Check each permutation
for perm in permutations:
total_cost = 0
for i in range(n):
total_cost += cost_matrix[i][perm[i]]
# Update minimum cost
if total_cost < min_cost:
min_cost = total_cost
best_assignment = perm
return best_assignment, min_cost
# ----------- Example Usage -----------
cost_matrix = [
[9, 2, 7],
[6, 4, 3],
[5, 8, 1]
assignment, cost = brute_force_assignment(cost_matrix)
print("Optimal Assignment:")
for worker, task in enumerate(assignment):
print(f"Worker {worker} -> Task {task}")
print("Minimum Cost:", cost)
Optimal Assignment:
Worker 0 -> Task 1
Worker 1 -> Task 0
Worker 2 -> Task 2
Minimum Cost: 9
2. Perform multiplication of large integers using divide and conquer method
The Karatsuba Algorithm is a divide and conquer algorithm used for efficient multiplication
of large integers. It improves upon the traditional grade-school multiplication method by
reducing the number of recursive multiplications.
Basic Idea
Instead of multiplying two large numbers directly, the algorithm:
1. Divides each number into two halves
2. Recursively computes partial products
3. Combines the results using a mathematical formula
Let’s go through a clear step-by-step example of the Karatsuba Algorithm so it’s easy to
explain in exams or class.
Why this is efficient?
Normal method → 4 multiplications
Karatsuba → only 3 multiplications
Saves time for large numbers
Example
Program
def karatsuba(x, y):
# Base case: if numbers are small, multiply directly
if x < 10 or y < 10:
return x * y
# Calculate the size of the numbers
n = max(len(str(x)), len(str(y)))
half = n // 2
# Split the digit sequences
high1 = x // (10 ** half)
low1 = x % (10 ** half)
high2 = y // (10 ** half)
low2 = y % (10 ** half)
# Recursive calls
z0 = karatsuba(low1, low2)
z1 = karatsuba((low1 + high1), (low2 + high2))
z2 = karatsuba(high1, high2)
# Combine results
return (z2 * 10**(2 * half)) + ((z1 - z2 - z0) * 10**half) + z0
# Example usage
x = 12345678
y = 87654321
result = karatsuba(x, y)
print("Multiplication Result:", result)
3. Implement a solution for knapsack problem using greedy method.
The greedy method works for the Fractional Knapsack Problem (not the 0/1 knapsack). In
this approach, items can be taken partially, and we select items based on the highest value-to-
weight ratio.
Algorithm Idea (Greedy Strategy)
1. Compute value/weight ratio for each item
2. Sort items in descending order of this ratio
3. Pick items one by one:
o If fully possible → take whole item
o Otherwise → take fractional part
Problem
Program
def fractional_knapsack(values, weights, capacity):
n = len(values)
# Create list of items with value, weight, ratio
items = []
for i in range(n):
ratio = values[i] / weights[i]
[Link]((values[i], weights[i], ratio))
# Sort items by ratio in descending order
[Link](key=lambda x: x[2], reverse=True)
total_value = 0.0
for value, weight, ratio in items:
if capacity >= weight:
# Take full item
capacity -= weight
total_value += value
else:
# Take fractional part
total_value += value * (capacity / weight)
break
return total_value
# Example usage
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
max_value = fractional_knapsack(values, weights, capacity)
print("Maximum value in Knapsack =", max_value)
Output
Maximum value in Knapsack = 240.0
ASSIGNMENT
Do the same program using Dynamic programming(0/1 Knapsack)
4. Implement Gaussian elimination method.
Gaussian Elimination Method (Step-by-Step Implementation)
Gaussian elimination is a systematic method used to solve a system of linear equations by converting
it into an upper triangular matrix and then applying back substitution.
Mathematical Representation
Ax= b
Algorithm Steps
1. Form Augmented Matrix [A∣B][A|B][A∣B]
2. Forward Elimination
o Make elements below the pivot (diagonal element) zero
3. Back Substitution
o Solve variables starting from the last equation
Program
def gaussian_elimination(A, B, n):
# Forward Elimination
for i in range(n):
# Pivot check (avoid division by zero)
if A[i][i] == 0:
print("Mathematical Error: Division by zero")
return None
for j in range(i+1, n):
ratio = A[j][i] / A[i][i]
for k in range(i, n):
A[j][k] -= ratio * A[i][k]
B[j] -= ratio * B[i]
# Back Substitution
X = [0] * n
for i in range(n-1, -1, -1):
X[i] = B[i]
for j in range(i+1, n):
X[i] -= A[i][j] * X[j]
X[i] = X[i] / A[i][i]
return X
# 🔽 Main Program
n = int(input("Enter number of variables: "))
A = []
print("Enter coefficients row-wise:")
for i in range(n):
row = list(map(float, input(f"Row {i+1}: ").split()))
if len(row) != n:
print("Invalid input! Enter exactly", n, "values.")
exit()
[Link](row)
B = list(map(float, input("Enter constants (B vector): ").split()))
if len(B) != n:
print("Invalid input! Enter exactly", n, "values.")
exit()
# Solve system
solution = gaussian_elimination(A, B, n)
# Output
if solution:
print("\nSolution:")
for i in range(n):
print(f"x{i+1} = {solution[i]:.2f}")
Input
Enter number of variables: 3
Enter coefficients row-wise:
Row 1: 2 1 -1
Row 2: -3 -1 2
Row 3: -2 1 2
Enter constants (B vector): 8 -11 -3
Output
x1 = 2.00
x2 = 3.00
x3 = -1.00
5. Implement LU decomposition
LU Decomposition (Doolittle Method) – Complete Program
LU decomposition factorizes a matrix AAA into:
LLL: Lower triangular matrix
UUU: Upper triangular matrix
Mathematical Form
A=LU
Algorithm (Doolittle Method)
Diagonal elements of L = 1
Compute U row-wise
Compute L column-wise
PROGRAM
def lu_decomposition(A, n):
# Initialize L and U
L = [[0.0]*n for _ in range(n)]
U = [[0.0]*n for _ in range(n)]
for i in range(n):
# Upper Triangular
for k in range(i, n):
sum_u = 0
for j in range(i):
sum_u += (L[i][j] * U[j][k])
U[i][k] = A[i][k] - sum_u
# Lower Triangular
for k in range(i, n):
if i == k:
L[i][i] = 1 # Diagonal = 1
else:
sum_l = 0
for j in range(i):
sum_l += (L[k][j] * U[j][i])
if U[i][i] == 0:
print("Division by zero error")
return None, None
L[k][i] = (A[k][i] - sum_l) / U[i][i]
return L, U
# 🔽 Main Program
n = int(input("Enter number of variables: "))
A = []
print("Enter matrix A row-wise:")
for i in range(n):
row = list(map(float, input(f"Row {i+1}: ").split()))
if len(row) != n:
print("Invalid input! Enter exactly", n, "values.")
exit()
[Link](row)
L, U = lu_decomposition(A, n)
# Output
if L and U:
print("\nLower Triangular Matrix (L):")
for row in L:
print(["{:.2f}".format(x) for x in row])
print("\nUpper Triangular Matrix (U):")
for row in U:
print(["{:.2f}".format(x) for x in row])
INPUT
Enter number of variables: 3
Enter matrix A row-wise:
Row 1: 2 -1 -2
Row 2: -4 6 3
Row 3: -4 -2 8
OUTPUT
Lower Triangular Matrix (L):
['1.00', '0.00', '0.00']
['-2.00', '1.00', '0.00']
['-2.00', '-1.00', '1.00']
Upper Triangular Matrix (U):
['2.00', '-1.00', '-2.00']
['0.00', '4.00', '-1.00']
['0.00', '0.00', '3.00']