Program: Fibonacci

def fibonacci(n):
if n<0:
return 'Incorrect input'
elif n==0 or n==1:
return 1
else:
return fibonacci(n-1)+fibonacci(n-2)
n=int(input('Enter the number:'))
for i in range(n):
print(fibonacci(i),end=' ')
Output:

Enter the number:5

11235
Program: Insertion Sort
# Insertion sort:
def insertionSort(arr):
n = len(arr)
if n <= 1:
return arr
for i in range(1, n):
key = arr[i]
j = i-1
while j >= 0 and key < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key

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

insertionSort(arr)
print(arr)
Output:

[5, 6, 11, 12, 13]

Program: Strassen’s matrix multiplication
# strassen matrix multiplication:
import numpy as np

def strassen_algorithm(x, y):

if x.size == 1 or y.size == 1:
return x * y
n = x.shape[0]
if n % 2 != 0:
x = np.pad(x, ((0, 1), (0, 1)), mode='constant')
y = np.pad(y, ((0, 1), (0, 1)), mode='constant')
n += 1
m = n // 2
a = x[:m, :m]
b = x[:m, m:]
c = x[m:, :m]
d = x[m:, m:]
e = y[:m, :m]
f = y[:m, m:]
g = y[m:, :m]
h = y[m:, m:]
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)
result = np.zeros((n, n), dtype=np.int32)
result[:m, :m] = p5 + p4 - p2 + p6
result[:m, m:] = p1 + p2
result[m:, :m] = p3 + p4
result[m:, m:] = p1 + p5 - p3 - p7
return result[:x.shape[0], :x.shape[1]]

x = np.array([[1, 1, 1, 1],
[2, 2, 2, 2],
[3, 3, 3, 3],
[2, 2, 2, 2]])
y = np.array([[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: Topological Sorting
# topological ordering a graph
from collections import defaultdict
class Graph:
def __init__(self, vertices):
self.graph = defaultdict(list)
self.V = vertices
def addEdge(self, u, v):
self.graph[u].append(v)
def topologicalSortUtil(self, v, visited, stack):
visited[v] = True
for i in self.graph[v]:
if visited[i] == False:
self.topologicalSortUtil(i, visited, stack)
stack.append(v)
def topologicalSort(self):
visited = [False]*self.V
stack = []
for i in range(self.V):
if visited[i] == False:
self.topologicalSortUtil(i, visited, stack)
print("Topological Sort of the given graph:")
print(stack[::-1])
g = Graph(6)
g.addEdge(5, 2)
g.addEdge(5, 0)
g.addEdge(4, 0)
g.addEdge(4, 1)
g.addEdge(2, 3)
g.addEdge(3, 1)
g.topologicalSort()
Output:

Topological Sort of the given graph:

[5, 4, 2, 3, 1, 0]
Sorted array is
5
6
7
11
12
13
Program: Heap Sort
def heapify(arr, n, i):
largest = i
l=2*i+1
r=2*i+2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print('Sorted array is')
for i in range(n):
print(arr[i])
Output:

Sorted array is
5
6
7
11
12
13
Program: Coin Changing Problem
print("coin change")
def count(S, m, n):
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
result = count(arr, m, n)
print("Number of ways to make change:", result)
Output:

coin change
Number of ways to make change: 4
Program: Warshall’s and Floyd’s algorithm
print("warshall’s floyd's algorithm")
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):
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:

warshall floyd’s algorithm

0 5 15 10
20 0 10 5
30 35 0 15
15 20 5 0
Program: Knapsack
def knapSack(W, wt, val, n):
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:

knapsack algorithm
220
Program: Dijkstra’s Algorithm
print("dijkstra's algorithm")
num_of_vertex = 7
def minimumDistance(distance, visited):
_min = float("inf")
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 = list()
visited = list()
parent = list()
for i in range(num_of_vertex):
parent.append(-1)
distance.append(1e11)
visited.append(False)
distance[src] = 0
for i in range(num_of_vertex - 1):
U = minimumDistance(distance, visited)
 visited[U] = True
for j in range(num_of_vertex):
curr_distance = distance[U] + graph[U][j]
if not visited[j] and graph[U][j] and curr_distance < distance[j]:
parent[j] = U
distance[j] = curr_distance
print("Vertex\t\tDistance\tPath")
for i in range(num_of_vertex):
path = getPath(parent, src, i)
print("{}->{}\t\t{}\t\t{}".format(src + 1, i + 1, distance[i], path))
def getPath(parent, src, j):
if parent[j] == -1:
return str(src + 1)
return getPath(parent, src, parent[j]) + " " + str(j + 1)
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, 1, 0, 0, 3, 0]
]
dijkstra(graph, 0)
Output:

Dijkstra's algorithm
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 7 1267
Program: Huffman Trees and codes
print("huffman trees and codes")
import heapq
class node:
def __init__(self, freq, symbol, left=None, right=None):
self.freq = freq
self.symbol = symbol
self.left = left
self.right = right
self.huff = ''
def __lt__(self, nxt):
return self.freq < nxt.freq
def printNodes(node, val=''):
newVal = val + str(node.huff)
if(node.left):
printNodes(node.left, newVal)
if(node.right):
printNodes(node.right, newVal)
if(not node.left and not node.right):
print(f"{node.symbol} -> {newVal}")
chars = ['a', 'b', 'c', 'd', 'e', 'f']
freq = [5, 9, 12, 13, 16, 45]
nodes = []
for x in range(len(chars)):
heapq.heappush(nodes, node(freq[x], chars[x]))
while len(nodes) > 1:
left = heapq.heappop(nodes)
right = heapq.heappop(nodes)
left.huff = 0
right.huff = 1
newNode = node(left.freq+right.freq, left.symbol+right.symbol, left,
right)
heapq.heappush(nodes, newNode)
printNodes(nodes[0])
Output:

huffman trees and codes (alter)

f -> 0
c -> 100
d -> 101
a -> 1100
b -> 1101
e -> 111
Program: Simplex Method
import numpy as np
from fractions import Fraction
print("\n**** Simplex Algorithm ****\n\n")
A = np.array([[1, 1, 0, 1], [2, 1, 1, 0]])
b = np.array([8, 10])
c = np.array([1, 1, 0, 0])
cb = np.array(c[3])
B = np.array([[3], [2]])
cb = np.vstack((cb, c[2]))
xb = np.transpose([b])
table = np.hstack((B, cb))
table = np.hstack((table, xb))
table = np.hstack((table, A))
table = np.array(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()
print("Simplex Working....")
reached = 0
itr = 1
unbounded = 0
alternate = 0
while reached == 0:
print("Iteration: ", end=' ')
print(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()
i=0
rel_prof = []
while i < len(A[0]):
rel_prof.append(c[i] - np.sum(table[:, 1] * table[:, 3 + i]))
i=i+1
print("rel profit: ", end=" ")
for profit in rel_prof:
print(Fraction(str(profit)).limit_denominator(100), end=", ")
print()
i=0
b_var = table[:, 0]
while i < len(A[0]):
j=0
present = 0
while j < len(b_var):
if int(b_var[j]) == i:
present = 1
break
 j += 1
if present == 0:
if rel_prof[i] == 0:
alternate = 1
print("Case of Alternate found")
print(i,end=" ")
i += 1
print()
flag = 0
for profit in rel_prof:
if profit > 0:
flag = 1
break
if flag == 0:
print("All profits are <= 0, optimality reached")
reached = 1
break
k = rel_prof.index(max(rel_prof))
min = 99999
i=0
r = -1
while i < len(table):
if (table[:, 2][i] > 0 and table[:, 3 + k][i] > 0):
val = table[:, 2][i] / table[:, 3 + k][i]
if val < min:
min = val
r=i
 i += 1
if r == -1:
unbounded = 1
print("Case of Unbounded")
break
print("pivot element index:", end=' ')
print(np.array([r, 3 + k]))
pivot = table[r][3 + k]
print("pivot element: ", end=" ")
print(Fraction(pivot).limit_denominator(100))
table[r, 2:len(table[0])] = table[r, 2:len(table[0])] / pivot
i=0
while i < 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])]
i += 1
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()
print("value of Z at optimality: ", end=" ")
basis = []
i=0
sum = 0
while i < len(table):
sum += c[int(table[i][0])]*table[i][2]
temp = "x"+str(int(table[i][0])+1)
basis.append(temp)
i += 1
if MIN == 1:
print(-Fraction(str(sum)).limit_denominator(100))
else:
print(Fraction(str(sum)).limit_denominator(100))
print("Final Basis: ", end=" ")
print(basis)
print("Simplex Finished")
print()
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

Simplex Working....
Iteration: 1
B CB XB y1 y2 y3 y4
3 0 8 1 1 0 1
2 0 10 2 1 1 0
rel profit: 1, 1, 0, 0,

pivot element index: [1 3]

pivot element: 2

Iteration: 2
B CB XB y1 y2 y3 y4
3 0 3 0 1/2 -1/2 1
0 1 5 1 1/2 1/2 0
rel profit: 0, 1/2, -1/2, 0,

pivot element index: [0 4]

pivot element: 1/2
Iteration: 3
B CB XB y1 y2 y3 y4
1 1 6 0 1 -1 2
0 1 2 1 0 1 -1
rel profit: 0, 0, 0, -1,
Case of Alternate found
2
All profits are <= 0, optimality reached

************************************
ALTERNATE Solution
optimal table:
B CB XB y1 y2 y3 y4
1 1 6 0 1 -1 2
0 1 2 1 0 1 -1

value of Z at optimality: 8
Final Basis: ['x2', 'x1']
Simplex Finished
Program: N-Queens problem
print("N-Queens problems")
global N
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
if solveNQUtil(board, col + 1):
 return True
board[i][col] = 0
return False
def solveNQ():
board = [
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
if solveNQUtil(board, 0) is False:
print("Solution does not exist")
return False
printSolution(board)
return True
solveNQ()
Output:

N-Queens problems
0010
1000
0001
0100
Program: Subset sum problem
print("subset sum problem")
def isSubsetSum(arr, n, target_sum):
if target_sum == 0:
return True
if n == 0:
return False
if arr[n - 1] > target_sum:
return isSubsetSum(arr, n - 1, target_sum)
return isSubsetSum(arr, n - 1, target_sum) or isSubsetSum(arr, n - 1,
target_sum - arr[n - 1])
set = [3, 34, 4, 12, 5, 2]
target_sum = 9
n = len(set)
if isSubsetSum(set, n, target_sum):
print("Found a subset with the given sum",target_sum)
else:
print("No subset with the given sum")
Output:

Subset sum problem

Found a subset with the given sum 9
Program: Assignment Problem
import numpy as np
def cal_cost(asgmnt, cost_mat):
total_cost = 0
for person, job in enumerate(asgmnt):
total_cost += cost_mat[person][job]
return total_cost

def branch_and_bound(cost_mat):
num_people = len(cost_mat)
assigned_jobs = [-1] * num_people
min_cost = [float('inf')]
best_asgmnt = None

def assign_jobs(person, total_cost):

nonlocal best_asgmnt
if person == num_people:
if total_cost < min_cost[0]:
min_cost[0] = total_cost
best_asgmnt = assigned_jobs.copy()
return
for job in range(num_people):
if assigned_jobs[job] == -1:
assigned_jobs[job] = person
assign_jobs(person + 1, total_cost + cost_mat[person][job])
assigned_jobs[job] = -1
assign_jobs(0, 0)
 return best_asgmnt, min_cost[0]

cost_mat = np.array([
[5, 9, 1],
[10, 3, 2],
[8, 7, 4],
])
best_asgmnt, min_cost = branch_and_bound(cost_mat)
for person, job in enumerate(best_asgmnt):
print(f"Person {person + 1} - Job {job + 1}")
print(f"Minimum assignment cost: {min_cost}")
Output:

Person 1 - Job 1
Person 2 - Job 2
Person 3 - Job 3
Minimum assignment cost: 12
Program: Travelling Salesman Problem
from sys import maxsize
from itertools import permutations
V=4
def travellingSalesmanProblem(graph, s):
vertex = []
for i in range(V):
if i != s:
vertex.append(i)
min_path = maxsize
next_permutation = permutations(vertex)
for i in next_permutation:
current_pathweight = 0
k=s
for j in i:
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("the minimum cost is:",travellingSalesmanProblem(graph, s))
Output:

the minimum cost is: 80