PROGRAM
import numpy as np
def strassen_algorithm(x, y):
if [Link] == 1:
return x * y
n = [Link][0]
if n % 2 != 0:
x = [Link](x, ((0,1), (0,1)), mode='constant')
y = [Link](y, ((0,1), (0,1)), mode='constant')
n += 1
m = n // 2
a, b, c, d = x[:m, :m], x[:m, m:], x[m:, :m], x[m:, m:]
e, f, g, h = y[:m, :m], y[:m, m:], y[m:, :m], y[m:, m:]
# 7 recursive multiplications
p1 = strassen_algorithm(a, f - h)
p2 = strassen_algorithm(a + b, h)
p3 = strassen_algorithm(c + d, e)
p4 = strassen_algorithm(d, g - e)
p5 = strassen_algorithm(a + d, e + h)
p6 = strassen_algorithm(b - d, g + h)
p7 = strassen_algorithm(a - c, e + f)
top_left = p5 + p4 - p2 + p6
top_right = p1 + p2
bottom_left = p3 + p4
bottom_right = p1 + p5 - p3 - p7
result = [Link]((n, n), dtype=int)
result[:m, :m] = top_left
result[:m, m:] = top_right
result[m:, :m] = bottom_left
result[m:, m:] = bottom_right
return result[:[Link][0], :[Link][1]]
x = [Link]([[1, 1, 1, 1], [2, 2, 2, 2], [3, 3, 3, 3], [2, 2, 2, 2]])
y = [Link]([[1, 1, 1, 1], [2, 2, 2, 2], [3, 3, 3, 3], [2, 2, 2, 2]])
print("Matrix multiplication result:")
print(strassen_algorithm(x, y))
OUTPUT
Matrix multiplication result:
[[ 8 8 8 8 ]
[16 16 16 16]
[24 24 24 24]
[16 16 16 16]]
PROGRAM:
from collections import defaultdict
class Graph:
def __init__(self, vertices):
[Link] = defaultdict(list)
self.V = vertices
# Function to add an edge to graph
def add_Edge(self, u, v):
[Link][u].append(v)
# A recursive function used by topologicalSort
def topological_Sort_Util(self, v, visited, stack):
# Mark the current node as visited
visited[v] = True
# Recur for all the vertices adjacent to this vertex
for i in [Link][v]:
if not visited[i]:
self.topological_Sort_Util(i, visited, stack)
# Push current vertex to stack which stores the result
[Link](v)
def topological_Sort(self):
visited = [False] * self.V
stack = []
# Call the recursive helper function to store Topological Sort
for i in range(self.V):
if not visited[i]:
[Link](i, visited, stack)
print(stack[::-1])
# Create a graph and test the topological sort
g = Graph(6)
[Link](5, 2)
[Link](5, 0)
[Link](4, 0)
[Link](4, 1)
[Link](2, 3)
[Link](3, 1)
print("Topological Sort of the given graph:")
[Link]()
OUTPUT:
Topological Sort of the given graph:
[5, 4, 2, 3, 1, 0]
PROGRAM
def heapify(arr, n, i):
largest = i
left_child = 2 * i + 1
right_child = 2 * i + 2
if left_child < n and arr[i] < arr[left_child]:
largest = left_child
if right_child < n and arr[larget] < arr[right_child]
largest = right_child
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 element one by one
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # swap
heapify(arr, i, 0)
If_name_ ==”_main_”:
arr = [12, 11, 13, 5, 6, 7]
heap_Sort(arr)
print("Sorted array is:")
print(arr)
OUTPUT
Sorted array is:
11
12
13
PROGRAM
Coin change Problem
def count(S, m, n):
# Create a table to store solutions
table = [[0 for x in range(m)] for x in range(n + 1)]
for i in range(m):
table[0][i] = 1
for i in range(1, n + 1):
for j in range(m):
x = table[i - S[j]][j] if i - S[j] >= 0 else 0
y = table[i][j - 1] if j >= 1 else 0
table[i][j] = x + y
return table[n][m - 1]
arr = [1, 2, 3]
m = len(arr)
n=4
print(count(arr, m, n))
OUTPUT
Warshall’s and Floyd‘s algorithms
nV = 4
INF = 999
def floyd(G):
dist = list(map(lambda p: list(map(lambda q: q, p)), G))
for r in range(nV):
for p in range(nV):
for q in range(nV):
dist[p][q] = min(dist[p][q], dist[p][r] + dist[r][q])
sol(dist)
def sol(dist):
print("Shortest distance matrix:")
for p in range(nV):
for q in range(nV):
if dist[p][q] == INF:
print("INF", end=" ")
else:
print(dist[p][q], end=" ")
print("")
G=[
[0, 5, INF, INF],
[50, 0, 15, 5],
[30, INF, 0, 15],
[15, INF, 5, 0]
]
floyd(G)
OUTPUT
0 5 15 10
20 0 10 5
30 35 0 15
15 20 5 0
knapsack problem
def knapSack(W, wt, val, n):
# Create a 2D DP table
K = [[0 for x in range(W + 1)] for x in range(n + 1)]
for i in range(n + 1):
for w in range(W + 1):
if i == 0 or w == 0:
K[i][w] = 0
elif wt[i - 1] <= w:
K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]],
K[i - 1][w])
else:
K[i][w] = K[i - 1][w]
return K[n][W]
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knapSack(W, wt, val, n))
OUTPUT
220
PROGRAM
Dijkstra’s algorithm
num_of_vertex = 7
def minimumDistance(distance, visited):
_min = 1e11
min_index = -1
for i in range(num_of_vertex):
if not visited[i] and distance[i] <= _min:
_min = distance[i]
min_index = i
return min_index
def printParentNode(parent, i):
if parent[i] == -1:
return
printParentNode(parent, parent[i])
print("{}".format(i + 1), end=" ")
def dijkstra(graph, src):
distance = []
visited = []
parent = []
for i in range(num_of_vertex):
[Link](-1)
[Link](1e11)
[Link](False)
distance[src] = 0
for _ in range(num_of_vertex - 1):
U = minimumDistance(distance, visited)
visited[U] = True
for j in range(num_of_vertex):
if graph[U][j] and not visited[j]:
curr_distance = distance[U] + graph[U][j]
if curr_distance < distance[j]:
parent[j] = U
distance[j] = curr_distance
print("Vertex\tDistance\tPath")
for i in range(num_of_vertex):
print("{} -> {}\t{}\t\t{}".format(src + 1, i + 1, int(distance[i]), src + 1), end=" ")
printParentNode(parent, i)
print("")
graph = [
[0, 1, 7, 6, 0, 0, 0],
[1, 0, 9, 0, 0, 3, 0],
[7, 9, 0, 0, 0, 0, 1],
[6, 0, 0, 0, 2, 0, 0],
[0, 0, 0, 2, 0, 0, 0],
[0, 3, 0, 0, 0, 0, 3],
[0, 0, 0, 0, 5, 3, 0]
]
dijkstra(graph, 0)
OUTPUT
Vertex Distance Path
1 -> 1 0 1
1 -> 2 1 12
1 -> 3 7 13
1 -> 4 6 14
1 -> 5 8 145
1 -> 6 4 126
1 -> 7 8 1267
Huffman Trees and codes
from collections import Counter
class NodeTree(object):
def __init__(self, left=None, right=None):
[Link] = left
[Link] = right
def children(self):
return [Link], [Link]
def __str__(self):
return f'{[Link]} {[Link]}'
def huffman_code_tree(node, binString=''):
if type(node) is str:
return {node: binString}
(l, r) = [Link]()
d = dict()
[Link](huffman_code_tree(l, binString + '0'))
[Link](huffman_code_tree(r, binString + '1'))
return d
def make_tree(nodes):
while len(nodes) > 1:
(key1, c1) = nodes[-1]
(key2, c2) = nodes[-2]
nodes = nodes[:-2]
node = NodeTree(key1, key2)
[Link]((node, c1 + c2))
nodes = sorted(nodes, key=lambda x: x[1], reverse=True)
return nodes[0][0]
if __name__ == '__main__':
string = 'BCAADDDCCACACAC'
freq = dict(Counter(string))
freq = sorted([Link](), key=lambda x: x[1], reverse=True)
node = make_tree(freq)
encoding = huffman_code_tree(node)
print("Character : Huffman Code")
for i in encoding:
print(f'{i} : {encoding[i]}')
OUTPUT
Character : Huffman Code
C:0
A : 11
D : 101
B : 100
PROGRAM
import numpy as np
from fractions import Fraction # for fractional display
print("\n**** Simplex Algorithm ****\n")
A = [Link]([[1, 1, 0, 1],[2, 1, 1, 0]])
b = [Link]([8, 10])
c = [Link]([1, 1, 0, 0])
B = [Link]([[3], [2]])
cb = [Link]([[c[3]], [c[2]]])
xb = [Link]([b])
# Construct initial tableau
table = [Link]((B, cb))
table = [Link]((table, xb))
table = [Link]((table, A))
table = [Link](table, dtype='float')
MIN = 0
print("Table at itr = 0")
print("B\tCB\tXB\ty1\ty2\ty3\ty4")
for row in table:
for el in row:
print(Fraction(str(el)).limit_denominator(100), end='\t')
print()
print()
reached = 0
itr = 1
unbounded = 0
alternate = 0
while reached == 0:
print("Iteration:", itr)
print("B\tCB\tXB\ty1\ty2\ty3\ty4")
for row in table:
for el in row:
print(Fraction(str(el)).limit_denominator(100), end='\t')
print()
rel_prof = []
for i in range(len(A[0])):
rel_prof.append(c[i] - [Link](table[:, 1] * table[:, 3 + i]))
print("Relative profit: ", end="")
for profit in rel_prof:
print(Fraction(str(profit)).limit_denominator(100), end=", ")
print("\n")
# Check for alternate solution
b_var = table[:, 0]
for i in range(len(A[0])):
present = False
for val in b_var:
if int(val) == i:
present = True
break
if not present and rel_prof[i] == 0:
alternate = 1
print("Case of Alternate found")
print()
flag = 0
for profit in rel_prof:
if profit > 0:
flag = 1
break
if flag == 0:
print("All relative profits <= 0. Optimality reached.")
reached = 1
break
k = rel_prof.index(max(rel_prof))
min_ratio = float('inf')
r = -1
for i in range(len(table)):
if table[i][2] > 0 and table[i][3 + k] > 0:
val = table[i][2] / table[i][3 + k]
if val < min_ratio:
min_ratio = val
r=i
if r == -1:
unbounded = 1
print("Case of Unbounded")
break
print("Pivot element index:", [r, 3 + k])
pivot = table[r][3 + k]
print("Pivot element:", Fraction(pivot).limit_denominator(100))
table[r, 2:len(table[0])] = table[r, 2:len(table[0])] / pivot
for i in range(len(table)):
if i != r:
table[i, 2:len(table[0])] = (
table[i, 2:len(table[0])] -
table[i][3 + k] * table[r, 2:len(table[0])]
)
table[r][0] = k
table[r][1] = c[k]
print()
itr += 1
print()
print("**************************************************")
if unbounded == 1:
print("UNBOUNDED LPP")
exit()
if alternate == 1:
print("ALTERNATE Solution")
print("Optimal table:")
print("B\tCB\tXB\ty1\ty2\ty3\ty4")
for row in table:
for el in row:
print(Fraction(str(el)).limit_denominator(100), end='\t')
print()
print()
basis = []
total = 0
for i in range(len(table)):
total += c[int(table[i][0])] * table[i][2]
[Link]("x" + str(int(table[i][0]) + 1))
if MIN == 1:
print("Value of Z at optimality:", -Fraction(str(total)).limit_denominator(100))
else:
print("Value of Z at optimality:", Fraction(str(total)).limit_denominator(100))
print("Final Basis:", basis)
print("\nSimplex Finished...")
OUTPUT
**** Simplex Algorithm ****
Table at itr = 0
B CB XB y1 y2 y3 y4
3 0 8 1 1 0 1
2 0 10 2 1 1 0
Iteration: 1
B CB XB y1 y2 y3 y4
3 0 8 1 1 0 1
2 0 10 2 1 1 0
Relative profit: 1, 1, 0, 0,
Pivot element index: [1, 4]
Pivot element: 1
**************************************************
Value of Z at optimality: 12
Final Basis: ['x2', 'x1']
Simplex Finished...
PROGRAM
N-Queen problem
N=4
def printSolution(board):
for i in range(N):
for j in range(N):
print(board[i][j], end=' ')
print()
def isSafe(board, row, col):
for i in range(col):
if board[row][i] == 1:
return False
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False
for i, j in zip(range(row, N, 1), range(col, -1, -1)):
if board[i][j] == 1:
return False
return True
def solveNQUtil(board, col):
if col >= N:
return True
for i in range(N):
if isSafe(board, i, col):
board[i][col] = 1 # Place queen
if solveNQUtil(board, col + 1):
return True
board[i][col] = 0
return False
def solveNQ():
board = [[0 for _ in range(N)] for _ in range(N)]
if not solveNQUtil(board, 0):
print("Solution does not exist")
return False
printSolution(board)
return True
solveNQ()
OUTPUT
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
Subset problem
def isSubsetSum(arr, n, total):
if total == 0:
return True
if n == 0:
return False
if arr[n - 1] > total:
return isSubsetSum(arr, n - 1, total)
return (isSubsetSum(arr, n - 1, total) or
isSubsetSum(arr, n - 1, total - arr[n - 1]))
arr = [3, 34, 4, 12, 5, 2]
total = 9
n = len(arr)
if isSubsetSum(arr, n, total):
print("✅ Found a subset with given sum")
else:
print("❌ No subset with given sum")
OUTPUT
Found a subset with given sum
PROGRAM
from sys import maxsize
from itertools import permutations
V=4
def travellingSalesmanProblem(graph, s):
vertex = [i for i in range(V) if i != s]
min_path = maxsize
for perm in permutations(vertex):
current_pathweight = 0
k=s
for j in perm:
current_pathweight += graph[k][j]
k=j
current_pathweight += graph[k][s]
min_path = min(min_path, current_pathweight)
return min_path
if __name__ == "__main__":
graph = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
s=0
print("Minimum cost of TSP:", travellingSalesmanProblem(graph, s))
OUTPUT
Minimum cost of TSP: 80