[Link].

1(A) IMPLEMENTATION OF RECURSIVE ALGORITHM – FACTORIAL

CALCULATION

AIM

To implement a recursive algorithm in Python for calculating the factorial of a given

number.

ALGORITHM

Step 1: Start the program.

Step 2: Define a function factorial(n) that takes an integer n as input.
Step 3: Check if n is 0 or 1. if yes, return 1.
Step 4: Otherwise, return n * factorial(n - 1) .
Step 5: Get input from the user for the number n.
Step 6: Call the factorial(n) function and store the result.
Step 7: Display the factorial of the given number.
Step 8: Stop the program.
PROGRAM

def factorial(n):

if n == 0 or n == 1:

return 1

else:

return n * factorial(n - 1)

num = int(input("Enter a number: "))

if num < 0:

print("Factorial is not defined for negative numbers.")

else:

result = factorial(num)

print("Factorial of", num, "is:", result)

OUTPUT

Enter a non-negative integer: 5

Factorial of 5 is 120

RESULT

Thus, the recursive algorithm for factorial calculation was successfully implemented and
executed in Python.
[Link].1(B) IMPLEMENTATION OF NON-RECURSIVE ALGORITHM

AIM

To implement a non-recursive algorithm in Python to generate the Fibonacci sequence up

to a given number of terms

ALGORITHM

Step 1: Read the number of terms n from the user.

Step 2: Initialize the first two terms as a = 0 and b = 1.

Step 3: Use a loop to print each term and update a and b as:

a, b = b, a + b

Step 4: Repeat until all terms are printed.

PROGRAM

# Non-recursive Fibonacci sequence

n_terms = int(input("Enter number of terms: "))

if n_terms<= 0:

print("Please enter a positive integer.")

else:

a, b = 0, 1

print("Fibonacci sequence:")

for _ in range(n_terms):

print(a, end=" ")

a, b = b, a + b
OUTPUT

Enter number of terms: 7

Fibonacci sequence:

0112358

RESULT

Thus, the program successfully generates the Fibonacci sequence up to the given number
of terms using a non-recursive algorithm.
[Link].2 DIVIDE AND CONQUER – STRASSEN’S MATRIX MULTIPLICATION

AIM

To implement Strassen’s Matrix Multiplication algorithm using the divide and conquer
approach in Python.

ALGORITHM

Step 1: Start the program.

Step 2: Read two square matrices (of order 2×2 for simplicity).
Step 3: Divide each matrix into four submatrices (A11, A12, A21, A22 and B11, B12, B21, B22).
Step 4: Compute the following seven products recursively:
P1 = (A11 + A22) × (B11 + B22)
P2 = (A21 + A22) × B11
P3 = A11 × (B12 − B22)
P4 = A22 × (B21 − B11)
P5 = (A11 + A12) × B22
P6 = (A21 − A11) × (B11 + B12)
P7 = (A12 − A22) × (B21 + B22)
Step 5: Compute the final submatrices of result matrix C as:
C11 = P1 + P4 − P5 + P7
C12 = P3 + P5
C21 = P2 + P4
C22 = P1 − P2 + P3 + P6
Step 6: Combine the submatrices to get the final matrix C.
Step 7: Display the result.
Step 8: Stop the program.
PROGRAM

def strassen(a, b):

# Base case for 2x2 matrices
if len(a) == 1:
return [[a[0][0] * b[0][0]]]

# Splitting matrices into quarters

n = len(a)
mid = n // 2

a11 = [[a[i][j] for j in range(mid)] for i in range(mid)]

a12 = [[a[i][j] for j in range(mid, n)] for i in range(mid)]
a21 = [[a[i][j] for j in range(mid)] for i in range(mid, n)]
a22 = [[a[i][j] for j in range(mid, n)] for i in range(mid, n)]

b11 = [[b[i][j] for j in range(mid)] for i in range(mid)]

b12 = [[b[i][j] for j in range(mid, n)] for i in range(mid)]
b21 = [[b[i][j] for j in range(mid)] for i in range(mid, n)]
b22 = [[b[i][j] for j in range(mid, n)] for i in range(mid, n)]

# Calculating p1 to p7 using Strassen’s formula

p1 = strassen(add(a11, a22), add(b11, b22))
p2 = strassen(add(a21, a22), b11)
p3 = strassen(a11, sub(b12, b22))
p4 = strassen(a22, sub(b21, b11))
p5 = strassen(add(a11, a12), b22)
p6 = strassen(sub(a21, a11), add(b11, b12))
p7 = strassen(sub(a12, a22), add(b21, b22))

# Combining results into a single matrix

c11 = add(sub(add(p1, p4), p5), p7)
 c12 = add(p3, p5)
c21 = add(p2, p4)
c22 = add(sub(add(p1, p3), p2), p6)

# Joining the four submatrices into one

new_matrix = []
for i in range(mid):
new_matrix.append(c11[i] + c12[i])
for i in range(mid):
new_matrix.append(c21[i] + c22[i])
return new_matrix

# Helper functions
def add(x, y):
n = len(x)
return [[x[i][j] + y[i][j] for j in range(n)] for i in range(n)]

def sub(x, y):

n = len(x)
return [[x[i][j] - y[i][j] for j in range(n)] for i in range(n)]
# Main program
a = [[1, 2], [3, 4]]
b = [[5, 6], [7, 8]]
print("Matrix A:", a)
print("Matrix B:", b)
result = strassen(a, b)
print("Resultant Matrix after Strassen's Multiplication:")
for row in result:
print(row)
OUTPUT

Matrix A: [[1, 2], [3, 4]]

Matrix B: [[5, 6], [7, 8]]

Resultant Matrix after Strassen's Multiplication:

[19, 22]

[43, 50]
RESULT

Thus, the Strassen’s Matrix Multiplication algorithm was successfully implemented using
the divide and conquer approach in Python.
[Link].3 DECREASE AND CONQUER – TOPOLOGICAL SORT

AIM

To perform topological sorting of a Directed Acyclic Graph (DAG) using depth-first

search (DFS) in the decrease and conquer approach.

ALGORITHM

1. Input the number of vertices and edges.

2. Store the graph as an adjacency list.

3. Maintain a visited array to mark visited nodes.

4. For each unvisited vertex, call DFS:

o Mark the vertex as visited.

o Recursively call DFS for all unvisited neighbors.

o Push the vertex to a stack after visiting all neighbors.

5. Reverse the stack to get the topological order.

6. Display the order.

PROGRAM
def dfs(v, visited, graph, stack):

visited[v] = True

for neighbor in graph[v]:

if not visited[neighbor]:

dfs(neighbor, visited, graph, stack)

[Link](v)

def topological_sort(n, edges):

graph = [[] for _ in range(n)]

for u, v in edges:

graph[u].append(v)

visited = [False] * n

stack = []

for i in range(n):

if not visited[i]:

dfs(i, visited, graph, stack)

return stack[::-1] # reverse stack for topo order

# Example usage

n=6

edges = [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)]

print("Topological Order:", topological_sort(n, edges))

OUTPUT

Topological Order: [5, 4, 2, 3, 1, 0]

RESULT

Thus, the Topological Sort using the DFS method was successfully implemented
using the Decrease and Conquer strategy in Python.
[Link].4 TRANSFORM AND CONQUER – HEAP SORT

AIM

To sort an array using Heap Sort, which transforms the array into a heap and then extracts
elements in sorted order.

ALGORITHM

1. Build a max heap from the input array.

2. Repeat until the heap size is 1:

o Swap the root (largest) with the last element.

o Reduce heap size by 1.

o Heapify the root to maintain the max heap property.

3. The array is now sorted in ascending order.

PROGRAM

def heapify(arr, n, i):

largest = i

left = 2 * i + 1

right = 2 * i + 2

if left < n and arr[left] >arr[largest]:

largest = left

if right < n and arr[right] >arr[largest]:

largest = right

if largest != i:

arr[i], arr[largest] = arr[largest], arr[i]

heapify(arr, n, largest)

def heap_sort(arr):

n = len(arr)

# Build max heap

for i in range(n // 2 - 1, -1, -1):

heapify(arr, n, i)

# Extract elements from heap

for i in range(n - 1, 0, -1):

arr[0], arr[i] = arr[i], arr[0]

heapify(arr, i, 0)

arr = [12, 11, 13, 5, 6, 7]

heap_sort(arr)

print("Sorted array:", arr)

OUTPUT

Sorted array: [5, 6, 7, 11, 12, 13]

RESULT

Thus, the Heap Sort algorithm was successfully implemented using the Transform and Conquer
approach in Python.
[Link].5(A) DYNAMIC PROGRAMMING – COIN CHANGE PROBLEM

AIM

To find the minimum number of coins required to make a given amount using dynamic
programming.

ALGORITHM

1. Input the coin denominations and the target amount.

2. Create a DP array of size amount + 1 initialized to infinity (or a large number), except
dp[0] = 0.

3. For each coin, update the DP array:

o For i from coin value to amount:

 dp[i] = min(dp[i], dp[i - coin] + 1)

4. If dp[amount] is infinity, return -1 (no solution).

5. Else, return dp[amount].

PROGRAM

def coin_change(coins, amount):

dp = [float('inf')] * (amount + 1)

dp[0] = 0

for coin in coins:

for i in range(coin, amount + 1):

dp[i] = min(dp[i], dp[i - coin] + 1)

return dp[amount] if dp[amount] != float('inf') else -1

coins = [1, 2, 5]

amount = 11

result = coin_change(coins, amount)

print("Minimum coins required:", result)

OUTPUT

Minimum coins required: 3

RESULT

Thus,the program successfully computes the minimum number of coins required to make
the given amount using Dynamic Programming.
[Link].5(B) DYNAMIC PROGRAMMING- WARSHALL’S ALGORITHM AND FLOYD’S

ALGORITHM

AIM

To implement Warshall’s Algorithm (for transitive closure) and Floyd’s Algorithm (for
shortest path) using Dynamic Programming in Python.

ALGORITHM

A. Warshall’s Algorithm

Step 1: Start the program.

Step 2: Input the adjacency matrix of the graph.
Step 3: For each vertex k, update path[i][j] = path[i][j] or (path[i][k] and path[k][j]).
Step 4: After all iterations, path[i][j] will show if there is a path from vertex i to j.
Step 5: Display the final transitive closure matrix.

B. Floyd’s Algorithm

Step 1: Start the program.

Step 2: Input the weighted adjacency matrix of the graph.
Step 3: For each vertex k, update
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
Step 4: After all iterations, dist[i][j] contains the shortest distance from i to j.
Step 5: Display the result matrix.
PROGRAM

def warshall(matrix):
n = len(matrix)
reach = [row[:] for row in matrix] # copy matrix
for k in range(n):
for i in range(n):
for j in range(n):
reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])
return reach
# ---------- Floyd’s Algorithm ----------
def floyd(matrix):
n = len(matrix)
dist = [row[:] for row in matrix] # copy matrix
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
# ---------- Main Program ----------
INF = 9999
adj_warshall = [
[1, 1, 0],
[0, 1, 1],
[0, 0, 1]
]

adj_floyd = [
[0, 4, INF],
[INF, 0, 2],
[1, INF, 0]
]
print("Original Matrix for Warshall’s Algorithm:")
for row in adj_warshall:
print(row)

print("\nTransitive Closure (Warshall’s Algorithm):")

result1 = warshall(adj_warshall)
for row in result1:
print(row)

print("\nOriginal Matrix for Floyd’s Algorithm:")

for row in adj_floyd:
print(row)

print("\nAll-Pairs Shortest Path (Floyd’s Algorithm):")

result2 = floyd(adj_floyd)
for row in result2:
print(row)
OUTPUT

Original Matrix for Warshall’s Algorithm:

[1, 1, 0]

[0, 1, 1]

[0, 0, 1]

Transitive Closure (Warshall’s Algorithm):

[1, 1, 1]

[0, 1, 1]

[0, 0, 1]

Original Matrix for Floyd’s Algorithm:

[0, 4, 9999]

[9999, 0, 2]

[1, 9999, 0]

All-Pairs Shortest Path (Floyd’s Algorithm):

[0, 4, 6]

[3, 0, 2]

[1, 5, 0]
RESULT

Thus, the Warshall’s Algorithm and Floyd’s Algorithm were successfully implemented
using the Dynamic Programming approach in Python
[Link].5(C) DYNAMIC PROGRAMMING - KNAPSACK PROBLEM

AIM

To implement the 0/1 Knapsack Problem using Dynamic Programming in Python to

find the maximum profit for a given weight capacity.

ALGORITHM

Step 1: Start the program.

Step 2: Input the number of items n, weights array wt[], values array val[], and maximum
capacity W.
Step 3: Create a 2D array dp[n+1][W+1] where dp[i][w] stores maximum value for first i items
and weight w.
Step 4: Initialize dp[0][w] = 0 for all w (0 items) and dp[i][0] = 0 for all i (0 capacity).
Step 5: Fill the dp table using:
If wt[i-1] <= w:
dp[i][w] = max(val[i-1] + dp[i-1][w - wt[i-1]], dp[i-1][w])
Else:
dp[i][w] = dp[i-1][w]
Step 6: The maximum profit is dp[n][W].
Step 7: Display the result.
Step 8: Stop the program.
PROGRAM

def knapsack(val, wt, W):

n = len(val)

dp = [[0 for _ in range(W+1)] for _ in range(n+1)]

for i in range(1, n+1):

for w in range(1, W+1):

if wt[i-1] <= w:

dp[i][w] = max(val[i-1] + dp[i-1][w - wt[i-1]], dp[i-1][w])

else:

dp[i][w] = dp[i-1][w]

return dp[n][W]

# Main Program

val = [60, 100, 120]

wt = [10, 20, 30]

W = 50

print("Values:", val)

print("Weights:", wt)

print("Maximum Capacity:", W)

max_profit = knapsack(val, wt, W)

print("Maximum Profit:", max_profit)

OUTPUT

Values: [60, 100, 120]

Weights: [10, 20, 30]

Maximum Capacity: 50

Maximum Profit: 220

RESULT

Thus, the 0/1 Knapsack Problem was successfully implemented using Dynamic
Programming, and the maximum profit for the given weight capacity was obtained.
[Link].6(A) GREEDY TECHNIQUE - DIJKSTRA’S ALGORITHM

AIM

To implement Dijkstra’s Algorithm using the Greedy technique in Python to find the
shortest path from a source vertex to all other vertices in a weighted graph.

ALGORITHM

Step 1: Start the program.

Step 2: Input the number of vertices V and the adjacency matrix of the graph.
Step 3: Initialize dist[] array to store the shortest distance from the source (set all distances to ∞
except the source, which is 0).
Step 4: Initialize a visited[] array to track vertices whose shortest distance is finalized.
Step 5: Repeat V times:
• Pick the unvisited vertex u with the minimum distance.
• Mark u as visited.
• For all neighbors v of u, if v is unvisited and dist[u] + weight(u, v) <dist[v], update dist[v].
Step 6: After all iterations, dist[] contains shortest distances from the source.
Step 7: Display the result.
Step 8: Stop the program.
PROGRAM

def dijkstra(graph, src):

V = len(graph)

dist = [float('inf')] * V

dist[src] = 0

visited = [False] * V

for _ in range(V):

# Pick the vertex with minimum distance

u = min((d for d in range(V) if not visited[d]), key=lambda x: dist[x])

visited[u] = True

# Update distances of adjacent vertices

for v in range(V):

if graph[u][v] > 0 and not visited[v] and dist[u] + graph[u][v] <dist[v]:

dist[v] = dist[u] + graph[u][v]

return dist

graph = [

[0, 4, 0, 0, 0, 0, 0, 8, 0],

[4, 0, 8, 0, 0, 0, 0, 11, 0],

[0, 8, 0, 7, 0, 4, 0, 0, 2],

[0, 0, 7, 0, 9, 14, 0, 0, 0],

[0, 0, 0, 9, 0, 10, 0, 0, 0],

[0, 0, 4, 14, 10, 0, 2, 0, 0],

 [0, 0, 0, 0, 0, 2, 0, 1, 6],

[8, 11, 0, 0, 0, 0, 1, 0, 7],

[0, 0, 2, 0, 0, 0, 6, 7, 0]

source = 0

distances = dijkstra(graph, source)

print("Shortest distances from vertex", source, "to all other vertices:")

for i, d in enumerate(distances):

print(f"Vertex {i}: {d}")

OUTPUT

Shortest distances from vertex 0 to all other vertices:

Vertex 0: 0

Vertex 1: 4

Vertex 2: 12

Vertex 3: 19

Vertex 4: 21

Vertex 5: 11

Vertex 6: 9

Vertex 7: 8

Vertex 8: 14
RESULT

Thus, the Dijkstra’s Algorithm was successfully implemented using the Greedy technique
in Python to find the shortest distances from a source vertex to all other vertices.
[Link].6(B) GREEDY TECHNIQUE – HUFFMAN TREES AND CODES

AIM

To implement Huffman Coding using the Greedy technique in Python to generate prefix-
free binary codes for characters based on their frequencies.

ALGORITHM

Step 1: Start the program.

Step 2: Input the set of characters and their frequencies.
Step 3: Create a priority queue (min-heap) of nodes, each node containing a character and its
frequency.
Step 4: Repeat until only one node remains in the queue:
• Extract two nodes with the smallest frequencies.
• Create a new internal node with frequency equal to the sum of the two nodes.
• Set the two extracted nodes as the left and right children of the new node.
• Insert the new node back into the priority queue.
Step 5: The remaining node is the root of the Huffman Tree.
Step 6: Traverse the tree to assign binary codes:
• Go left → append 0, go right → append 1.
Step 7: Display the Huffman codes for all characters.
Step 8: Stop the program.
PROGRAM

import heapq

class Node:

def __init__(self, char, freq):

[Link] = char

[Link] = freq

[Link] = None

[Link] = None

# Define comparators for priority queue

def __lt__(self, other):

return [Link]<[Link]

def huffman_codes(char_freq):

heap = [Node(char, freq) for char, freq in char_freq.items()]

[Link](heap)

while len(heap) > 1:

left = [Link](heap)

right = [Link](heap)

merged = Node(None, [Link] + [Link])

[Link] = left

[Link] = right

[Link](heap, merged)

root = heap[0]

codes = {}

def assign_codes(node, code):

if node is None:
 return

if [Link] is not None:

codes[[Link]] = code

assign_codes([Link], code + "0")

assign_codes([Link], code + "1")

assign_codes(root, "")

return codes

# Main Program

char_freq = {'A': 5, 'B': 9, 'C': 12, 'D': 13, 'E': 16, 'F': 45}

codes = huffman_codes(char_freq)

print("Character Frequencies:", char_freq)

print("\nHuffman Codes:")

for char, code in [Link]():

print(f"{char}: {code}")
OUTPUT

Character Frequencies: {'A': 5, 'B': 9, 'C': 12, 'D': 13, 'E': 16, 'F': 45}

Huffman Codes:

F: 0

C: 100

D: 101

A: 1100

B: 1101

E: 111
RESULT

Thus, the Huffman Coding was successfully implemented using the Greedy technique
[Link] ITERATIVEIMPROVEMENT – SIMPLEX METHOD

AIM

To implement the Simplex Method using Iterative Improvement in Python to solve a

linear programming problem (maximize or minimize objective function).

ALGORITHM

Step 1: Convert inequalities into equalities by adding slack variables.

Step 2: Set up the initial simplex tableau.

Step 3: Identify the pivot column (most negative value in bottom row → entering variable).

Step 4: Identify the pivot row using the minimum positive ratio test (b / pivot column element).

Step 5: Perform pivot operations to make pivot element = 1 and other column entries = 0.

Step 6: Repeat Steps 3–5 until there are no negative values in the bottom row.

Step 7: Read off the optimal solution and maximum Z.

PROGRAM

import numpy as np

def simplex(c, A, b):

n = len(c)

m = len(b)

# Step 1: Create initial tableau

tableau = [Link]((m + 1, n + m + 1))

tableau[:m, :n] = A

tableau[:m, n:n + m] = [Link](m) # slack variables

tableau[:m, -1] = b

tableau[-1, :n] = -c # objective function

while True:

# Step 2: Check for optimality

if all(tableau[-1, :-1] >= 0):

break # optimal reached

# Step 3: Entering variable (most negative coefficient)

pivot_col = [Link](tableau[-1, :-1])

# Step 4: Leaving variable (min ratio test)

ratios = []

for i in range(m):

if tableau[i, pivot_col] > 0:

[Link](tableau[i, -1] / tableau[i, pivot_col])

else:

[Link]([Link])

pivot_row = [Link](ratios)
 # Step 5: Pivot operation

pivot = tableau[pivot_row, pivot_col]

tableau[pivot_row, :] /= pivot

for i in range(m + 1):

if i != pivot_row:

tableau[i, :] -= tableau[i, pivot_col] * tableau[pivot_row, :]

# Step 6: Extract results

solution = [Link](n)

for i in range(m):

col = tableau[i, :n]

if list(col).count(1) == 1 and list(col).count(0) == n - 1:

j = [Link](col == 1)[0][0]

solution[j] = tableau[i, -1]

Z = tableau[-1, -1]

return solution, Z, tableau

# Example usage:

c = [Link]([3, 2]) # Coefficients of objective function

A = [Link]([[1, 1], [1, 2]]) # Coefficients of constraints

b = [Link]([4, 6]) # RHS of constraints

solution, Z, tableau = simplex(c, A, b)

print("Optimal solution (x):", solution)

print("Maximum Z value:", Z)

print("\nFinal Tableau:\n", tableau)

OUTPUT

Optimal solution (x): [0. 2.]

Maximum Z value: 12.0

Final Tableau:

[[ 1. 1. 1. 0. 4.]

[ 0. 1. -1. 1. 2.]

[ 0. 1. 3. 0. 12.]]

RESULT

Thus, the Simplex Method using Iterative Improvement was implemented successfully.
[Link](A) BACKTRACKING–NQUEENPROBLEM

AIM

To solve the N-Queen problem using the backtracking algorithm, where we must place N
queens on an N×N chessboard such that no two queens attack each other (i.e., no two queens
share the same row, column, or diagonal).

ALGORITHM

1. Start with an empty chessboard.

2. Place a queen in the first column of the first row.

3. Check if placing a queen is safe (no other queen attacks this position).

4. If it’s safe, place the queen and move to the next row.

5. If it’s not safe, try the next column in the current row.

6. If all columns in a row lead to conflicts, backtrack to the previous row and move the
queen to the next column.

7. Repeat until:

o All N queens are placed safely → solution found, or

o No position is possible → no solution exists.

8. Display the board configuration(s).

PROGRAM

def print_board(board):

for row in board:

print(" ".join(row))

print()

def is_safe(board, row, col, n):

# Check column

for i in range(row):

if board[i][col] == 'Q':

return False

# Check upper-left diagonal

i, j = row - 1, col - 1

while i >= 0 and j >= 0:

if board[i][j] == 'Q':

return False

i -= 1

j -= 1

# Check upper-right diagonal

i, j = row - 1, col + 1

while i >= 0 and j < n:

if board[i][j] == 'Q':

return False

i -= 1

j += 1

return True
def solve_n_queens(board, row, n):

if row == n:

print_board(board)

return True

res = False

for col in range(n):

if is_safe(board, row, col, n):

board[row][col] = 'Q'

res = solve_n_queens(board, row + 1, n) or res

board[row][col] = '.' # Backtrack

return res

def n_queen(n):

board = [['.' for _ in range(n)] for _ in range(n)]

if not solve_n_queens(board, 0, n):

print("No solution exists for", n, "Queens")

# Example usage:

n=4

n_queen(n)
OUTPUT

.Q..

...Q

Q...

..Q.

..Q.

Q...

...Q

.Q..

RESULT

Thus, the N-Queen problem was successfully solved using the Backtracking technique.
[Link](B) BACKTRACKING – SUBSET SUM PROBLEM

AIM

To write a Python program to solve the Subset Sum Problem using the backtracking
algorithm.

ALGORITHM

1. Start.

2. Input the number of elements in the set and the required target sum.

3. Generate all possible subsets using backtracking.

4. For each element:

o Include the element in the subset and recursively check the next element.

o Exclude the element and recursively check the next element.

5. If the current subset’s sum equals the target sum, display the subset.

6. If all elements are processed, backtrack to explore other possibilities.

7. Stop.
PROGRAM

def subset_sum(nums, target, partial=[]):

s = sum(partial)

# Check if the current subset sums to target

if s == target:

print("Subset:", partial)

if s >= target:

return # Stop if the sum exceeds target

for i in range(len(nums)):

n = nums[i]

remaining = nums[i+1:]

subset_sum(remaining, target, partial + [n])

# Main Program

nums = [3, 4, 5, 2]

target = 7

print("Given set:", nums)

print("Target sum:", target)

print("Subsets that sum to target are:")

subset_sum(nums, target)
OUTPUT

Given set: [3, 4, 5, 2]

Target sum: 7

Subsets that sum to target are:

Subset: [3, 4]

Subset: [5, 2]
RESULT

Thus, the Subset Sum Problem was successfully implemented using the Backtracking
algorithm, and all subsets whose sum equals the target value were displayed.
[Link]: 9(A) BRANCH AND BOUND – ASSIGNMENT PROBLEM

AIM

To write a Python program to solve the Assignment Problem using the Branch and Bound
algorithm.

ALGORITHM

1. Start.

2. Represent the problem as an n × n cost matrix.

3. Create a state-space tree where each level represents a worker.

4. At each node, assign the worker to one of the unassigned jobs.

5. Compute a cost bound (lower bound) for each node:

o Add the cost of the current assignment.

o Add the minimum possible cost from the remaining unassigned workers.

6. Use a priority queue to explore the node with the least cost bound first.

7. When all workers are assigned, record the total cost.

8. The node leading to the minimum total cost gives the optimal assignment.

9. Stop.
PROGRAM

from itertools import permutations

def assignment_problem(cost):

n = len(cost)

jobs = [i for i in range(n)]

min_cost = float('inf')

best_perm = None

# Try all possible job assignments (permutations)

for perm in permutations(jobs):

total = 0

for i in range(n):

total += cost[i][perm[i]]

if total <min_cost:

min_cost = total

best_perm = perm

print("Best Assignment:", best_perm)

print("Minimum Cost:", min_cost)

# Main Program
cost = [

[9, 2, 7, 8],

[6, 4, 3, 7],

[5, 8, 1, 8],

[7, 6, 9, 4]

print("Cost Matrix:")

for row in cost:

print(row)

assignment_problem(cost)
OUTPUT

Cost Matrix:

[9, 2, 7, 8]

[6, 4, 3, 7]

[5, 8, 1, 8]

[7, 6, 9, 4]

Best Assignment: (1, 0, 2, 3)

Minimum Cost: 13
RESULT

Thus, the Assignment Problem was successfully solved using the Branch and Bound
approach
 [Link](B) BRANCH AND BOUND – TRAVELLING SALESMAN \

PROBLEM

AIM

To write a Python program to solve the Travelling Salesman Problem (TSP) using the
Branch and Bound technique.

ALGORITHM

1. Start.

2. Represent the travel costs between cities using a cost matrix.

3. Select a city as the starting point.

4. Generate all possible paths that visit each city exactly once.

5. For each path, calculate the total cost (including returning to the start).

6. Keep track of the minimum total cost and the corresponding route.

7. Display the shortest path and minimum cost.

8. Stop.
PROGRAM

from itertools import permutations

def travelling_salesman(cost):

n = len(cost)

cities = [i for i in range(n)]

min_cost = float('inf')

best_path = []

# Try all possible routes starting from city 0

for perm in permutations(cities[1:]):

current_cost = 0

path = [0] + list(perm) + [0] # start and end at city 0

# Calculate total cost of this route

for i in range(len(path) - 1):

current_cost += cost[path[i]][path[i + 1]]

# Update minimum cost and path

if current_cost<min_cost:

min_cost = current_cost

best_path = path

print("Shortest Path:", " → ".join(str(c) for c in best_path))

print("Minimum Cost:", min_cost)

# Main Program

cost = [

[0, 10, 15, 20],

[10, 0, 35, 25],

[15, 35, 0, 30],

[20, 25, 30, 0]

print("Cost Matrix:")

for row in cost:

print(row)

travelling_salesman(cost)
OUTPUT

Cost Matrix:

[0, 10, 15, 20]

[10, 0, 35, 25]

[15, 35, 0, 30]

[20, 25, 30, 0]

Shortest Path: 0 → 1 → 3 → 2 → 0

Minimum Cost: 80
RESULT

Thus, the Travelling Salesman Problem (TSP) was successfully solved using the
Branch and Bound technique.