Program:
import numpy as np
def strassen_matrix_multiply(A, B):
# Check if matrices are compatible for multiplication
if A.shape[1] != B.shape[0]:
raise ValueError("Matrices are not compatible for multiplication")
# Base case: If matrices are 1x1, perform simple multiplication
if A.shape[0] == 1 and A.shape[1] == 1 and B.shape[0] == 1 and B.shape[1] ==
1:
return np.dot(A, B)
# Split matrices into quadrants
n = A.shape[0]
m = n // 2
A11 = A[:m, :m]
A12 = A[:m, m:]
A21 = A[m:, :m]
A22 = A[m:, m:]
B11 = B[:m, :m]
B12 = B[:m, m:]
B21 = B[m:, :m]
B22 = B[m:, m:]
# Recursive steps
P1 = strassen_matrix_multiply(A11 + A22, B11 + B22)
P2 = strassen_matrix_multiply(A21 + A22, B11)
P3 = strassen_matrix_multiply(A11, B12 - B22)
P4 = strassen_matrix_multiply(A22, B21 - B11)
P5 = strassen_matrix_multiply(A11 + A12, B22)
P6 = strassen_matrix_multiply(A21 - A11, B11 + B12)
P7 = strassen_matrix_multiply(A12 - A22, B21 + B22)
# Combine the results
C11 = P1 + P4 - P5 + P7
C12 = P3 + P5
C21 = P2 + P4
C22 = P1 - P2 + P3 + P6
# Concatenate the quadrants to form the resulting matrix
result = np.vstack((np.hstack((C11, C12)), np.hstack((C21, C22))))
return result
# Example usage
A = np.array([[1, 2, 3, 4],[5, 6, 7, 8],[9, 10, 11, 12],[13, 14, 15, 16]])
B = np.array([[17, 18, 19, 20],[21, 22, 23, 24],[25, 26, 27, 28],[29, 30, 31, 32]])
product = strassen_matrix_multiply(A, B)
print("Product of A and B:")
print(product)
Program:
from collections import defaultdict
def topological_sort(graph):
def dfs(node):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
sorted_nodes.append(node)
visited = set()
sorted_nodes = []
for node in graph:
if node not in visited:
dfs(node)
return sorted_nodes[::-1]
# Example usage
graph = defaultdict(list)
graph[1] = [2, 3]
graph[2] = [4]
graph[3] = [4, 5]
graph[4] = [6]
graph[5] = []
graph[6] = []
sorted_order = topological_sort(graph)
print("Topological Sort Order:")
print(sorted_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)
# Perform sorting
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
# Example usage
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("Sorted array:")
print(arr)
Program :
def coin_change(coins, target):
dp = [float('inf')] * (target + 1)
dp[0] = 0
for coin in coins:
for i in range(coin, target + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
if dp[target] == float('inf'):
return -1
# Retrieve coin combination (optional)
coins_used = []
i = target
while i > 0:
for coin in coins:
if i - coin >= 0 and dp[i] - dp[i - coin] == 1:
coins_used.append(coin)
i -= coin
break
coins_used.reverse()
return dp[target], coins_used
# Example usage
coins = [1, 2, 5]
target = 11
min_coins, coin_combination = coin_change(coins, target)
print("Minimum number of coins needed:", min_coins)
print("Coin combination:", coin_combination)
Program:
Code for Warshall's Algorithm:
def warshall(adj_matrix):
num_vertices = len(adj_matrix)
tc = [row[:] for row in adj_matrix] # Create a copy of the adjacency matrix
for k in range(num_vertices):
for i in range(num_vertices):
for j in range(num_vertices):
tc[i][j] = tc[i][j] or (tc[i][k] and tc[k][j])
return tc
# Example usage
adj_matrix = [[0, 1, 0, 0],[0, 0, 0, 1],[0, 0, 0, 0],[1, 0, 1, 0]]
transitive_closure = warshall(adj_matrix)
print("Transitive Closure Matrix:")
for row in transitive_closure:
print(row)
Code for Floyd's Algorithm:
def floyd(adj_matrix):
num_vertices = len(adj_matrix)
dist = [row[:] for row in adj_matrix] # Create a copy of the adjacency matrix
for k in range(num_vertices):
for i in range(num_vertices):
for j in range(num_vertices):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
# Example usage
adj_matrix = [[0, 1, float('inf'), 3],[2, 0, 4, float('inf')],[float('inf'), float('inf'), 0, 2],
[float('inf'), float('inf'), 1, 0]]
shortest_distances = floyd(adj_matrix)
print("Shortest Distance Matrix:")
for row in shortest_distances:
print(row)
Program :
def knapsack(items, weights, values, capacity):
n = len(items)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, capacity + 1):
if weights[i - 1] <= j:
dp[i][j] = max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]])
else:
dp[i][j] = dp[i - 1][j]
max_value = dp[n][capacity]
# Retrieve selected items (optional)
selected_items = []
i=n
j = capacity
while i > 0 and j > 0:
if dp[i][j] != dp[i - 1][j]:
selected_items.append(items[i - 1])
j -= weights[i - 1]
i -= 1
selected_items.reverse()
return max_value, selected_items
# Example usage
items = ['Item1', 'Item2', 'Item3', 'Item4', 'Item5']
weights = [2, 3, 4, 5, 6]
values = [5, 7, 9, 11, 13]
capacity = 10
max_value, selected_items = knapsack(items, weights, values, capacity)
print("Maximum value:", max_value)
print("Selected items:", selected_items)
Program:
import heapq
def dijkstra(graph, source):
distances = [float('inf')] * len(graph)
distances[source] = 0
pq = [(0, source)] # (distance, vertex)
while pq:
dist, u = heapq.heappop(pq)
if dist > distances[u]:
continue
for v, weight in graph[u]:
new_dist = dist + weight
if new_dist < distances[v]:
distances[v] = new_dist
heapq.heappush(pq, (new_dist, v))
return distances
# Example usage
graph = [[(1, 4), (2, 2)],[(2, 5), (3, 2)],[(1, 1), (3, 1)],[(4, 3)], []]
source_vertex = 0
shortest_distances = dijkstra(graph, source_vertex)
print("Shortest distances from vertex", source_vertex)
print(shortest_distances)
Program:
from queue import PriorityQueue
class Node:
def __init__(self, char, frequency):
self.char = char
self.frequency = frequency
self.left = None
self.right = None
def build_huffman_tree(characters, frequencies):
pq = PriorityQueue()
for i in range(len(characters)):
node = Node(characters[i], frequencies[i])
pq.put((node.frequency, node))
while pq.qsize() > 1:
freq1, node1 = pq.get()
freq2, node2 = pq.get()
new_node = Node(None, freq1 + freq2)
new_node.left = node1
new_node.right = node2
pq.put((new_node.frequency, new_node))
root = pq.get()[1]
return root
def generate_huffman_codes(root):
codes = {}
def dfs(node, code):
if node.char:
codes[node.char] = code
else:
dfs(node.left, code + '0')
dfs(node.right, code + '1')
dfs(root, '')
return codes
# Example usage
characters = ['A', 'B', 'C', 'D', 'E']
frequencies = [10, 7, 15, 4, 12]
root = build_huffman_tree(characters, frequencies)
huffman_codes = generate_huffman_codes(root)
print("Huffman Codes:")
for char, code in huffman_codes.items():
print(char, ":", code)
Program:
import numpy as np
from scipy.optimize import linprog
# Define the objective function coefficients
c = [3, 2]
# Define the constraint coefficients and RHS values
A = [[-1, 1],[3, 2],[1, 0]]
b = [1, 12, 3]
# Define the bounds for the variables
x_bounds = [(0, None), (0, None)]
# Solve the linear programming problem using the simplex method
result = linprog(c, A_ub=A, b_ub=b, bounds=x_bounds, method='simplex')
# Print the optimal solution and objective function value
print("Optimal Solution:")
print(result.x)
print("Objective Function Value:")
print(result.fun)
Program:
def is_safe(row, col, board, N):
# Check if a queen can be placed at the current position without conflicts
# Check column
for i in range(row):
if board[i][col] == 1:
return False
# Check upper diagonal
i = row - 1
j = col - 1
while i >= 0 and j >= 0:
if board[i][j] == 1:
return False
i -= 1
j -= 1
# Check lower diagonal
i = row - 1
j = col + 1
while i >= 0 and j < N:
if board[i][j] == 1:
return False
i -= 1
j += 1
return True
def place_queens(row, board, N, solutions):
if row == N:
# All queens have been placed successfully
solutions.append(board.copy())
return
for col in range(N):
if is_safe(row, col, board, N):
# Place the queen at the current position
board[row][col] = 1
# Recursively place queens in the next row
place_queens(row + 1, board, N, solutions)
# Remove the queen from the current position
board[row][col] = 0
def solve_n_queen(N):
board = [[0] * N for _ in range(N)]
solutions = []
place_queens(0, board, N, solutions)
return solutions
# Example usage
N=4
solutions = solve_n_queen(N)
print("Number of solutions:", len(solutions))
for i, solution in enumerate(solutions):
print("Solution", i + 1)
for row in solution:
print(row)
print()
Program:
def find_subsets(nums, target_sum, index, subset, subsets):
if target_sum == 0:
subsets.append(subset[:]) # Add a copy of the subset to the subsets list
return
for i in range(index, len(nums)):
if nums[i] <= target_sum:
subset.append(nums[i])
find_subsets(nums, target_sum - nums[i], i + 1, subset, subsets)
subset.pop()
def subset_sum(nums, target_sum):
subsets = []
find_subsets(nums, target_sum, 0, [], subsets)
return subsets
# Example usage
nums = [2, 4, 6, 8]
target_sum = 8
result = subset_sum(nums, target_sum)
print("Subsets with a sum of", target_sum)
for subset in result:
print(subset)
Program:
import numpy as np
def branch_and_bound(cost_matrix):
N = cost_matrix.shape[0]
assignment_matrix = np.zeros((N, N), dtype=int)
selected_tasks = []
min_cost = float('inf')
def backtrack(selected_tasks, current_cost):
nonlocal min_cost
if current_cost > min_cost:
return
if len(selected_tasks) == N:
min_cost = current_cost
assignment_matrix.fill(0)
for i, task in enumerate(selected_tasks):
assignment_matrix[task][i] = 1
return
for task in range(N):
if task not in selected_tasks:
agent = np.argmin([cost_matrix[task][i] for i in range(N) if i not in
selected_tasks])
selected_tasks.append(task)
backtrack(selected_tasks, current_cost + cost_matrix[task][agent])
selected_tasks.remove(task)
backtrack(selected_tasks, 0)
return assignment_matrix, min_cost
# Example usage
cost_matrix = np.array([[5, 7, 3, 8],[9, 2, 6, 4],[1, 3, 8, 6],[7, 6, 4, 2]])
assignment, min_cost = branch_and_bound(cost_matrix)
print("Assignment Matrix:")
print(assignment)
print("Minimum Cost:", min_cost)
Program:
import numpy as np
def branch_and_bound(current_city, visited_cities, path, distance):
global min_distance, best_path
if len(visited_cities) == N and distances[current_city][0] < min_distance:
min_distance = distance + distances[current_city][0]
best_path = path[:]
return
for city in range(N):
if city not in visited_cities:
visited_cities.add(city)
path.append(city)
new_distance = distance + distances[current_city][city]
if new_distance < min_distance:
branch_and_bound(city, visited_cities, path, new_distance)
visited_cities.remove(city)
path.pop()
# Example usage
distances = np.array([[0, 2, 9, 10],[1, 0, 6, 4],[15, 7, 0, 8],[6, 3, 12, 0]])
N = distances.shape[0]
min_distance = float('inf')
best_path = []
branch_and_bound(0, {0}, [0], 0)
print("Best Path:", best_path)
print("Minimum Distance:", min_distance)
