1.
Singular Value Decomposition
# Singular-value decomposition
from numpy import array
from scipy.linalg import svd
# define a matrix
A = array([[5,7,-4], [-3,4,6]])
print(A)
# SVD
U, s, VT = svd(A)
print(U)
print(s)
print(VT)
Output
[[ 5 7 -4]
[-3 4 6]]
[[-0.94781097 0.31883282]
[ 0.31883282 0.94781097]]
[9.67989022 7.5696582 ]
[[-0.58839028 -0.55365768 0.58928775]
[-0.16503636 0.79568634 0.58279178]
[ 0.79155536 -0.24565511 0.55954775]]
2. Gram Schmidt
import numpy as np
def gram_schmidt(A):
n = A.shape[1]
for j in range(n):
for k in range(j):
A[:, j] == np.dot(A[:, k], A[:, j]) * A[:, k]
A[:, j] = A[:, j] / np.linalg.norm(A[:, j])
return A
if _name_ == '_main_':
A = np.array([[1.0, 1.0, 1.0], [1.0, 3.0, 1.0], [2.0, -1.0, 1.0]])
print(gram_schmidt(A))
Output
[[ 0.40824829 0.30151134 0.57735027]
[ 0.40824829 0.90453403 0.57735027]
[ 0.81649658 -0.30151134 0.57735027]]
3. Multiplication of Matrix
import numpy as np
x = int(input("Enter the number of rows of A: "))
y = int(input("Enter the number of columns of A & B: "))
z = int(input("Enter the number of rows of B: "))
#Creating the 1st matrux
R = x #number of rows
C = y #number of columns
print("Enter the entries of A in single line (separated by space): ")
# User input of entries in a
# single line separated by space
entries = list(map(int, input().split()))
# For printing the matrix
A = np.array(entries).reshape(R, C)
print('The first matrix is: \n', A)
#Creating 2nd matrix
R = y #number of rows
C = z #number of columns
print("Enter the entries of B in single line (separated by space): ")
# User input of entries in a
# single line separated by space
entries = list(map(int, input().split()))
# For printing the matrix
B = np.array(entries).reshape(R, C)
print("The second matrix is: \n", B)
X = np.dot(A,B) #Calculating matrix multiplication
print("The result matrix is: \n", X)
Output
Enter the number of rows of A: 3
Enter the number of columns of A & B: 3
Enter the number of rows of B: 3
Enter the entries of A in single line (separated by space):
123789456
The first matrix is:
[[1 2 3]
[7 8 9]
[4 5 6]]
Enter the entries of B in single line (separated by space):
987321456
The second matrix is:
[[9 8 7]
[3 2 1]
[4 5 6]]
The result matrix is:
[[ 27 27 27]
[123 117 111]
[ 75 72 69]]
4. EigenValue and EigenVector
import numpy as np
from numpy.linalg import eig
n = int(input("Enter the number of rows & columns:"))
R = n #number of rows
C = n #number of columns
print("Enter the entries in single line (separated by space): ")
# User input of entries in a
# single line separated by space
entries = list(map(int, input().split()))
# For printing the matrix
matrix = np.array(entries).reshape(R, C)
print(matrix)
w,v=eig(matrix)
print('E-value:', w)
print('E-vector:', v)
Output
Enter the number of rows & columns:3
Enter the entries in single line (separated by space):
3 4 6 7 8 3 -8 -2 6
[[ 3 4 6]
[ 7 8 3]
[-8 -2 6]]
E-value: [2.47250657+0.j 7.26374672+5.22672562j 7.26374672-5.22672562j]
E-vector: [[ 0.4065112 +0.j 0.02454257-0.35884786j
0.02454257+0.35884786j]
[-0.77629128+0.j -0.52995846-0.35043978j -0.52995846+0.35043978j]
[ 0.48178885+0.j 0.68334608+0.j 0.68334608-0.j ]]
5. Matrix Multiplication
import numpy as np
A = np.array([[2, 4, 1], [8, 3, 5], [9, 0, 7]])
print(A)
B = np.array([[5, 2, 1], [0, 4, 9], [2, 1, 3]])
print(B)
X = A*B
print(X)
Output
[[2 4 1]
[8 3 5]
[9 0 7]]
[[5 2 1]
[0 4 9]
[2 1 3]]
[[10 8 1]
[ 0 12 45]
[18 0 21]]
6.
#Calculation of AXI where A and I are 3X3 matrix
import numpy as np
A = np.array([[2, 4, 1], [8, 3, 5], [9, 0, 7]])
print(A)
I = np.array([[1, 0, 0], [0, 1, 0], [0, 0, 1]])
print(I)
X = A*I
print(X)
Output
[[2 4 1]
[8 3 5]
[9 0 7]]
[[1 0 0]
[0 1 0]
[0 0 1]]
[[2 0 0]
[0 3 0]
[0 0 7]]
7.
import numpy as np
a = np.array([[3,3,3,3,3],[3,3,3,3,3],[3,3,3,3,3],[3,3,3,3,3]])
print (a)
b = np.array([[5],[7],[3],[8],[9]])
print (b)
x = np.dot(a, b)
print (x)
Output
[[3 3 3 3 3]
[3 3 3 3 3]
[3 3 3 3 3]
[3 3 3 3 3]]
[[5]
[7]
[3]
[8]
[9]]
[[96]
[96]
[96]
[96]]
8.
import numpy as np
A = np.array([[1,2,3],[2,3,4],[3,4,5]])
print (A)
I = np.array([[1,0,0],[0,1,0],[0,0,1]])
print (I)
X = np.dot(A, I)
print (X)
Output
[[1 2 3]
[2 3 4]
[3 4 5]]
[[1 0 0]
[0 1 0]
[0 0 1]]
[[1 2 3]
[2 3 4]
[3 4 5]]
9.
from numpy import array
from numpy import diag
from numpy import dot
from numpy import zeros
from scipy.linalg import svd
# define a matrix
A = array([[1, 2], [3, 4], [5, 6]])
print(A)
# Singular-value decomposition
U, s, VT = svd(A)
# create m x n Sigma matrix
Sigma = zeros((A.shape[0], A.shape[1]))
# populate Sigma with n x n diagonal matrix
Sigma[:A.shape[1], :A.shape[1]] = diag(s)
# reconstruct matrix
B = U.dot(Sigma.dot(VT))
print(B)
Output
[[1 2]
[3 4]
[5 6]]
[[1. 2.]
[3. 4.]
[5. 6.]]
10.
#Initializing activities with start and finish times
activities = [["A1", 0, 6],
["A2", 3, 4],
["A3", 1, 2],
["A4", 5, 8],
["A5", 5, 7],
["A6", 8, 9]
]
#Function to solve the Activity Selection Problem
def printMaxActivities(activities):
activities.sort(key=lambda x: x[2])
i=0
firstA = activities[i][0]
print(firstA)
for j in range(len(activities)):
if activities[j][1] > activities[i][2]:
print(activities[j][0])
i=j
printMaxActivities(activities)
Output
A3
A2
A5
A6
11. Prim’s Algorithm
# Prim's Algorithm in Python
INF = 9999999
# number of vertices in graph
N=5
#creating graph by adjacency matrix method
G = [[0, 19, 5, 0, 0],
[19, 0, 5, 9, 2],
[5, 5, 0, 1, 6],
[0, 9, 1, 0, 1],
[0, 2, 6, 1, 0]]
selected_node = [0, 0, 0, 0, 0]
no_edge = 0
selected_node[0] = True
# printing for edge and weight
print("Edge : Weight\n")
while (no_edge < N - 1):
minimum = INF
a=0
b=0
for m in range(N):
if selected_node[m]:
for n in range(N):
if ((not selected_node[n]) and G[m][n]):
# not in selected and there is an edge
if minimum > G[m][n]:
minimum = G[m][n]
a=m
b=n
print(str(a) + "-" + str(b) + ":" + str(G[a][b]))
selected_node[b] = True
no_edge += 1
Output
Edge : Weight
0-2:5
2-3:1
3-4:1
4-1:2
12. Kruskal’s Algorithm
# Python program for Kruskal's algorithm to find
# Minimum Spanning Tree of a given connected,
# undirected and weighted graph
from collections import defaultdict
# Class to represent a graph
class Graph:
def _init_(self, vertices):
self.V = vertices # No. of vertices
self.graph = [] # default dictionary
# to store graph
# function to add an edge to graph
def addEdge(self, u, v, w):
self.graph.append([u, v, w])
# A utility function to find set of an element i
# (uses path compression technique)
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
# A function that does union of two sets of x and y
# (uses union by rank)
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
# Attach smaller rank tree under root of
# high rank tree (Union by Rank)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
# If ranks are same, then make one as root
# and increment its rank by one
else:
parent[yroot] = xroot
rank[xroot] += 1
# The main function to construct MST using Kruskal's
# algorithm
def KruskalMST(self):
result = [] # This will store the resultant MST
# An index variable, used for sorted edges
i=0
# An index variable, used for result[]
e=0
# Step 1: Sort all the edges in
# non-decreasing order of their
# weight. If we are not allowed to change the
# given graph, we can create a copy of graph
self.graph = sorted(self.graph,
key=lambda item: item[2])
parent = []
rank = []
# Create V subsets with single elements
for node in range(self.V):
parent.append(node)
rank.append(0)
# Number of edges to be taken is equal to V-1
while e < self.V - 1:
# Step 2: Pick the smallest edge and increment
# the index for next iteration
u, v, w = self.graph[i]
i=i+1
x = self.find(parent, u)
y = self.find(parent, v)
# If including this edge does't
# cause cycle, include it in result
# and increment the indexof result
# for next edge
if x != y:
e=e+1
result.append([u, v, w])
self.union(parent, rank, x, y)
# Else discard the edge
minimumCost = 0
print ("Edges in the constructed MST")
for u, v, weight in result:
minimumCost += weight
print("%d -- %d == %d" % (u, v, weight))
print("Minimum Spanning Tree" , minimumCost)
# Driver code
g = Graph(4)
g.addEdge(0, 1, 10)
g.addEdge(0, 2, 6)
g.addEdge(0, 3, 5)
g.addEdge(1, 3, 15)
g.addEdge(2, 3, 4)
# Function call
g.KruskalMST()
Output
Edges in the constructed MST
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
Minimum Spanning Tree 19
13. Dijkstra’s Algorithm
# Python program for Dijkstra's single
# source shortest path algorithm. The program is
# for adjacency matrix representation of the graph
class Graph():
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for column in range(vertices)]
for row in range(vertices)]
def printSolution(self, dist):
print("Vertex \t Distance from Source")
for node in range(self.V):
print(node, "\t\t", dist[node])
# A utility function to find the vertex with
# minimum distance value, from the set of vertices
# not yet included in shortest path tree
def minDistance(self, dist, sptSet):
# Initialize minimum distance for next node
min = 1e7
# Search not nearest vertex not in the
# shortest path tree
for v in range(self.V):
if dist[v] < min and sptSet[v] == False:
min = dist[v]
min_index = v
return min_index
# Function that implements Dijkstra's single source
# shortest path algorithm for a graph represented
# using adjacency matrix representation
def dijkstra(self, src):
dist = [1e7] * self.V
dist[src] = 0
sptSet = [False] * self.V
for cout in range(self.V):
# Pick the minimum distance vertex from
# the set of vertices not yet processed.
# u is always equal to src in first iteration
u = self.minDistance(dist, sptSet)
# Put the minimum distance vertex in the
# shortest path tree
sptSet[u] = True
# Update dist value of the adjacent vertices
# of the picked vertex only if the current
# distance is greater than new distance and
# the vertex in not in the shortest path tree
for v in range(self.V):
if (self.graph[u][v] > 0 and
sptSet[v] == False and
dist[v] > dist[u] + self.graph[u][v]):
dist[v] = dist[u] + self.graph[u][v]
self.printSolution(dist)
# Driver program
g = Graph(9)
g.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]
]
g.dijkstra(0)
Output
Vertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14
14. Chromatic Number
# algorithm for graph coloring
def addEdge(adj, v, w):
adj[v].append(w)
# Note: the graph is undirected
adj[w].append(v)
return adj
# Assigns colors (starting from 0) to all
# vertices and prints the assignment of colors
def greedyColoring(adj, V):
result = [-1] * V
# Assign the first color to first vertex
result[0] = 0;
# A temporary array to store the available colors.
# True value of available[cr] would mean that the
# color cr is assigned to one of its adjacent vertices
available = [False] * V
# Assign colors to remaining V-1 vertices
for u in range(1, V):
# Process all adjacent vertices and
# flag their colors as unavailable
for i in adj[u]:
if (result[i] != -1):
available[result[i]] = True
# Find the first available color
cr = 0
while cr < V:
if (available[cr] == False):
break
cr += 1
# Assign the found color
result[u] = cr
# Reset the values back to false
# for the next iteration
for i in adj[u]:
if (result[i] != -1):
available[result[i]] = False
# Print the result
for u in range(V):
print("Vertex", u, " ---> Color", result[u])
# Driver Code
if __name__ == '__main__':
g1 = [[] for i in range(5)]
g1 = addEdge(g1, 0, 1)
g1 = addEdge(g1, 0, 2)
g1 = addEdge(g1, 1, 2)
g1 = addEdge(g1, 1, 3)
g1 = addEdge(g1, 2, 3)
g1 = addEdge(g1, 3, 4)
print("Coloring of graph 1 ")
greedyColoring(g1, 5)
g2 = [[] for i in range(5)]
g2 = addEdge(g2, 0, 1)
g2 = addEdge(g2, 0, 2)
g2 = addEdge(g2, 1, 2)
g2 = addEdge(g2, 1, 4)
g2 = addEdge(g2, 2, 4)
g2 = addEdge(g2, 4, 3)
print("\nColoring of graph 2")
greedyColoring(g2, 5)
output
Coloring of graph 1
Vertex 0 ---> Color 0
Vertex 1 ---> Color 1
Vertex 2 ---> Color 2
Vertex 3 ---> Color 0
Vertex 4 ---> Color 1
Coloring of graph 2
Vertex 0 ---> Color 0
Vertex 1 ---> Color 1
Vertex 2 ---> Color 2
Vertex 3 ---> Color 0
Vertex 4 ---> Color 3
15. Maximun and minimum element
# Python program find maximum and minimum element
from sys import maxsize
INT_MAX = maxsize
INT_MIN = -maxsize
# A Tree node
class Node:
def _init_(self, key):
self.key = key
self.left = None
self.right = None
# Function to print a maximum and minimum element
# in a tree without recursion without stack
def printMinMax(root: Node):
if root is None:
print("Tree is empty")
return
current = root
pre = Node(0)
# Max variable for storing maximum value
max_value = INT_MIN
# Min variable for storing minimum value
min_value = INT_MAX
while current is not None:
# If left child does nor exists
if current.left is None:
max_value = max(max_value, current.key)
min_value = min(min_value, current.key)
current = current.right
else:
# Find the inorder predecessor of current
pre = current.left
while pre.right is not None and pre.right != current:
pre = pre.right
# Make current as the right child
# of its inorder predecessor
if pre.right is None:
pre.right = current
current = current.left
# Revert the changes made in the 'if' part to
# restore the original tree i.e., fix the
# right child of predecessor
else:
pre.right = None
max_value = max(max_value, current.key)
min_value = min(min_value, current.key)
current = current.right
# End of if condition pre->right == NULL
# End of if condition current->left == NULL
# End of while
# Finally print max and min value
print("Max value is :", max_value)
print("Min value is :", min_value)
# Driver Code
if _name_ == "_main_":
# /* 15
#/\
# 19 11
# /\
# 25 5
#/\/\
# 17 3 23 24
# Let us create Binary Tree as shown
# above */
root = Node(15)
root.left = Node(19)
root.right = Node(11)
root.right.left = Node(25)
root.right.right = Node(5)
root.right.left.left = Node(17)
root.right.left.right = Node(3)
root.right.right.left = Node(23)
root.right.right.right = Node(24)
# Function call for printing a max
# and min element in a tree
printMinMax(root)
Output
Max Value is : 25
Min Value is : 3
16. Traveling salesman problem
# traveling salesman
from sys import maxsize
from itertools import permutations
V=4
# implementation of traveling Salesman Problem
def travellingSalesmanProblem(graph, s):
# store all vertex apart from source vertex
vertex = []
for i in range(V):
if i != s:
vertex.append(i)
# store minimum weight Hamiltonian Cycle
min_path = maxsize
next_permutation=permutations(vertex)
for i in next_permutation:
# store current Path weight(cost)
current_pathweight = 0
# compute current path weight
k=s
for j in i:
current_pathweight += graph[k][j]
k=j
current_pathweight += graph[k][s]
# update minimum
min_path = min(min_path, current_pathweight)
return min_path
# Driver Code
if _name_ == "_main_":
# matrix representation of graph
graph = [[0, 10, 15, 20], [10, 0, 35, 25],
[15, 35, 0, 30], [20, 25, 30, 0]]
s=0
print(travellingSalesmanProblem(graph, s))
output
80
