7/10/2021 Algo_ASS
Job Scheduling
In [1]: def printJobScheduling(arr, t):
n = len(arr)
for i in range(n):
for j in range(n - 1 - i):
if arr[j][2] < arr[j + 1][2]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
result = [False] * t
job = ['-1'] * t
for i in range(len(arr)):
for j in range(min(t - 1, arr[i][1] - 1), -1, -1):
if result[j] is False:
result[j] = True
job[j] = arr[i][0]
break
print(job)
arr = [['j1', 7, 14],
['j2', 2, 20],
['j3', 5, 30],
['j4', 3, 18],
['j5', 4, 18],
['j6', 5, 10],
['j7', 2, 23],
['j8', 7, 16],
['j9', 3, 25]]
print("Following is maximum profit sequence of jobs")
printJobScheduling(arr, 7)
Following is maximum profit sequence of jobs
['j2', 'j7', 'j9', 'j5', 'j3', 'j1', 'j8']
Fractional Knapsack
localhost:8888/nbconvert/html/Downloads/Algo_ASS.ipynb?download=false 1/13
7/10/2021 Algo_ASS
In [2]: class ItemValue:
def __init__(self, wt, val, ind):
self.wt = wt
self.val = val
self.ind = ind
self.cost = val // wt
def __lt__(self, other):
return self.cost < other.cost
class FractionalKnapSack:
def getMaxValue(wt, val, capacity):
iVal = []
for i in range(len(wt)):
iVal.append(ItemValue(wt[i], val[i], i))
iVal.sort(reverse=True)
totalValue = 0
for i in iVal:
curWt = int(i.wt)
curVal = int(i.val)
if capacity - curWt >= 0:
capacity -= curWt
totalValue += curVal
else:
fraction = capacity / curWt
totalValue += curVal * fraction
capacity = int(capacity - (curWt * fraction))
break
return totalValue
if __name__ == "__main__":
wt = [2 , 3, 5, 7, 1, 4, 1]
val = [10, 5, 15, 7, 6, 18, 3]
capacity = 15
maxValue = FractionalKnapSack.getMaxValue(wt, val, capacity)
print("Maximum value in Knapsack =", maxValue)
Maximum value in Knapsack = 55.333333333333336
Kruskal’s Algorithm
localhost:8888/nbconvert/html/Downloads/Algo_ASS.ipynb?download=false 2/13
7/10/2021 Algo_ASS
In [3]: from collections import defaultdict
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
def addEdge(self, u, v, w):
self.graph.append([u, v, w])
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1
def KruskalMST(self):
result = []
i = 0
e = 0
self.graph = sorted(self.graph,
key=lambda item: item[2])
parent = []
rank = []
for node in range(self.V):
parent.append(node)
rank.append(0)
while e < self.V - 1:
u, v, w = self.graph[i]
i = i + 1
x = self.find(parent, u)
y = self.find(parent, v)
if x != y:
localhost:8888/nbconvert/html/Downloads/Algo_ASS.ipynb?download=false 3/13
7/10/2021 Algo_ASS
e = e + 1
result.append([u, v, w])
self.union(parent, rank, x, y)
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)
g = Graph(5)
g.addEdge(0, 1, 8)
g.addEdge(0, 2, 5)
g.addEdge(1, 2, 9)
g.addEdge(1, 3, 11)
g.addEdge(2, 3, 15)
g.addEdge(2, 4, 10)
g.addEdge(3, 4, 7)
g.KruskalMST()
Edges in the constructed MST
0 -- 2 == 5
3 -- 4 == 7
0 -- 1 == 8
2 -- 4 == 10
Minimum Spanning Tree 30
Prims Algorithm
localhost:8888/nbconvert/html/Downloads/Algo_ASS.ipynb?download=false 4/13
7/10/2021 Algo_ASS
In [4]: import sys
class Graph():
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for column in range(vertices)]
for row in range(vertices)]
def printMST(self, parent):
minimumCost = 0
print ("Edge \tWeight")
for i in range(1, self.V):
minimumCost += self.graph[i][ parent[i] ]
print (parent[i], "-", i, "\t", self.graph[i][ parent[i] ])
print("Minimum Spanning Tree" , minimumCost)
def minKey(self, key, mstSet):
min = sys.maxsize
for v in range(self.V):
if key[v] < min and mstSet[v] == False:
min = key[v]
min_index = v
return min_index
def primMST(self):
key = [sys.maxsize] * self.V
parent = [None] * self.V
key[0] = 0
mstSet = [False] * self.V
parent[0] = -1
for cout in range(self.V):
u = self.minKey(key, mstSet)
mstSet[u] = True
for v in range(self.V):
if self.graph[u][v] > 0 and mstSet[v] == False and key[v] > se
lf.graph[u][v]:
key[v] = self.graph[u][v]
parent[v] = u
self.printMST(parent)
g = Graph(5)
g.graph = [ [0, 2, 0, 6, 0],
[2, 0, 3, 8, 5],
[0, 3, 0, 0, 7],
[6, 8, 0, 0, 9],
localhost:8888/nbconvert/html/Downloads/Algo_ASS.ipynb?download=false 5/13
7/10/2021 Algo_ASS
[0, 5, 7, 9, 0]]
g.primMST()
Edge Weight
0 - 1 2
1 - 2 3
0 - 3 6
1 - 4 5
Minimum Spanning Tree 16
The Longest Common Subsequence
localhost:8888/nbconvert/html/Downloads/Algo_ASS.ipynb?download=false 6/13
7/10/2021 Algo_ASS
In [5]: def lcs_algo(S1, S2, m, n):
L = [[0 for x in range(n+1)] for x in range(m+1)]
for i in range(m+1):
for j in range(n+1):
if i == 0 or j == 0:
L[i][j] = 0
elif S1[i-1] == S2[j-1]:
L[i][j] = L[i-1][j-1] + 1
else:
L[i][j] = max(L[i-1][j], L[i][j-1])
index = L[m][n]
lcs_algo = [""] * (index+1)
lcs_algo[index] = ""
i = m
j = n
while i > 0 and j > 0:
if S1[i-1] == S2[j-1]:
lcs_algo[index-1] = S1[i-1]
i -= 1
j -= 1
index -= 1
elif L[i-1][j] > L[i][j-1]:
i -= 1
else:
j -= 1
print("S1 : " + S1 + "\nS2 : " + S2)
print("LCS: " + "".join(lcs_algo))
S1 = "AGGTAB"
S2 = "GXTXAYB"
m = len(S1)
n = len(S2)
lcs_algo(S1, S2, m, n)
S1 : AGGTAB
S2 : GXTXAYB
LCS: GTAB
Fibonacci Sequence
localhost:8888/nbconvert/html/Downloads/Algo_ASS.ipynb?download=false 7/13
7/10/2021 Algo_ASS
In [6]: nterms = int(input("How many terms? "))
n1, n2 = 0, 1
count = 0
if nterms <= 0:
print("Please enter a positive integer")
elif nterms == 1:
print("Fibonacci sequence upto",nterms,":")
print(n1,end=" ")
else:
print("Fibonacci sequence:")
while count < nterms:
print(n1,end=" ")
nth = n1 + n2
# update values
n1 = n2
n2 = nth
count += 1
def Fibonacci(n):
if n < 0:
print("Incorrect input")
elif n == 0:
return 0
elif n == 1 or n == 2:
return 1
else:
return Fibonacci(n-1) + Fibonacci(n-2)
print("\nAddition of",nterms,"is = ", Fibonacci(nterms))
How many terms? 12
Fibonacci sequence:
0 1 1 2 3 5 8 13 21 34 55 89
Addition of 12 is = 144
Merge Sort
localhost:8888/nbconvert/html/Downloads/Algo_ASS.ipynb?download=false 8/13
7/10/2021 Algo_ASS
In [7]: def merge(arr, l, m, r):
n1 = m - l + 1
n2 = r- m
L = [0] * (n1)
R = [0] * (n2)
for i in range(0 , n1):
L[i] = arr[l + i]
for j in range(0 , n2):
R[j] = arr[m + 1 + j]
i = 0
j = 0
k = l
while i < n1 and j < n2 :
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < n1:
arr[k] = L[i]
i += 1
k += 1
while j < n2:
arr[k] = R[j]
j += 1
k += 1
def mergeSort(arr,l,r):
if l < r:
m = (l+(r-1))//2
mergeSort(arr, l, m)
mergeSort(arr, m+1, r)
merge(arr, l, m, r)
arr = [12, 11, 13, 5, 6, 81, 77, 7]
n = len(arr)
print ("Given array is")
for i in range(n):
print ("%d" %arr[i], end=" "),
mergeSort(arr,0,n-1)
print ("\n\nSorted array is")
for i in range(n):
print ("%d" %arr[i],end=" "),
localhost:8888/nbconvert/html/Downloads/Algo_ASS.ipynb?download=false 9/13
7/10/2021 Algo_ASS
Given array is
12 11 13 5 6 81 77 7
Sorted array is
5 6 7 11 12 13 77 81
Binary Search
In [8]: def binary_search(arr, low, high, x):
if high >= low:
mid = (high + low) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)
else:
return -1
arr = [ 2, 3, 4, 10, 40 ]
x = 10
result = binary_search(arr, 0, len(arr)-1, x)
if result != -1:
print(x,"Element is present at position", str(result))
else:
print(x,"Element is not present in array")
10 Element is present at position 3
Quick Sort
localhost:8888/nbconvert/html/Downloads/Algo_ASS.ipynb?download=false 10/13
7/10/2021 Algo_ASS
In [9]: def partition(arr, low, high):
i = (low-1)
pivot = arr[high]
for j in range(low, high):
if arr[j] <= pivot:
i = i+1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return (i+1)
def quickSort(arr, low, high):
if len(arr) == 1:
return arr
if low < high:
pi = partition(arr, low, high)
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr, 0, n-1)
print("Sorted array is:")
for i in range(n):
print("%d" % arr[i], end=" ")
Sorted array is:
1 5 7 8 9 10
Minimum and Maximum Element of an array Using
Divide and conquer
localhost:8888/nbconvert/html/Downloads/Algo_ASS.ipynb?download=false 11/13
7/10/2021 Algo_ASS
In [10]: import sys
INF = sys.maxsize
def findMinAndMax(A, left, right, min, max):
if left == right:
if min > A[right]:
min = A[right]
if max < A[left]:
max = A[left]
return min, max
if right - left == 1:
if A[left] < A[right]:
if min > A[left]:
min = A[left]
if max < A[right]:
max = A[right]
else:
if min > A[right]:
min = A[right]
if max < A[left]:
max = A[left]
return min, max
mid = (left + right) // 2
min, max = findMinAndMax(A, left, mid, min, max)
min, max = findMinAndMax(A, mid + 1, right, min, max)
return min, max
if __name__ == '__main__':
A = [7, 2, 9, 3, 1, 6, 22, 8, 4]
(min, max) = (INF, -INF)
(min, max) = findMinAndMax(A, 0, len(A) - 1, min, max)
print("The minimum element in the list is", min)
print("The maximum element in the list is", max)
The minimum element in the list is 1
The maximum element in the list is 22
localhost:8888/nbconvert/html/Downloads/Algo_ASS.ipynb?download=false 12/13
7/10/2021 Algo_ASS
In [ ]:
localhost:8888/nbconvert/html/Downloads/Algo_ASS.ipynb?download=false 13/13
