1.
Linear Search:
import time
import [Link] as plt
def ln(a,n,k):
for i in range(n):
if a[i] == k:
return i
return -1
def res(runs):
results=[]
for _ in range(runs):
n=int(input("Enter number of elements"))
a=list(map(int,input("Enter the list").split()))
k=int(input("enter the key to be searched"))
rep=10000
result=-1
s=[Link]()
for _ in range(rep):
result=ln(a,n,k)
if result == -1:
print("not found")
else:
print("fount at",result)
e=[Link]()
tt=(s-e)*1000
[Link]((n, tt))
return results
def plotting(res):
value=[i[0] for i in res]
timetaken=[i[1] for i in res]
[Link]()
[Link](value,timetaken,"gD--")
[Link]("X label")
[Link]("Y label")
[Link]("Linear Search")
[Link](True)
[Link]()
runs=int(input("enter the number of runs"))
result = res(runs)
plotting(result)
2. Binary Search:
import time
import [Link] as plt
def ln(a,h,l,k):
while l<=h:
mid=(l+h)//2
if a[mid]==k:
return mid
if a[mid]>k:
h=mid-1
else:
l=mid+1
return -1
def res(runs):
results=[]
for _ in range(runs):
n=int(input("Enter number of elements"))
a=sorted(list(map(int,input("Enter the list").split())))
k=int(input("enter the key to be searched"))
rep=10000
result=-1
s=[Link]()
for _ in range(rep):
result=ln(a,n-1,0,k)
if result == -1:
print("not found")
else:
print("fount at",result)
e=[Link]()
tt=(e-s)*1000
[Link]((n,tt))
return results
def plotting(res):
value=[i[0] for i in res]
timetaken=[i[1] for i in res]
[Link]()
[Link](value,timetaken,"o-")
[Link]("X label")
[Link]("Y label")
[Link]("Binary Search")
[Link](True)
[Link]()
runs=int(input("enter the number of runs"))
result = res(runs)
plotting(result)
3. Tower Of Hanoi:
def toh(n,s,d,a):
if n==1:
print("Move disk 1 from source",s,"to destination",d)
return
toh(n-1,s,a,d)
print("Moved disk",n,"From source",s,"to destination",d)
toh(n-1,a,d,s)
n=int(input("Enter the number of disks"))
toh(n,'A','B','C')
4. Power of N:
a) Brute force
b) Divide and conquer
def pb(a,n):
res=1
for i in range(n):
res *= a
return res
def pdc(a,n):
if n==0:
return 1
elif n%2==0:
return pdc(a*a,n//2)
else:
return a*pdc(a*a,n//2)
a,n=map(int,input("Enter two numbers").split())
print("Brute Force",pb(a,n))
print("Divide an Conquer",pdc(a,n))
5. Selection Sort
import random
import time
import timeit
import [Link] as plt
def rnd(arr,n):
for i in range(0,n):
ele=[Link](0,50)
[Link](ele)
def ss(a,n):
for i in range(n):
min=i
for j in range(i+1,n):
if a[min]>a[j]:
min=j
a[i],a[min]=a[min],a[i]
N=[]
CPU=[]
tr=int(input("Enter number of trails"))
for t in range(tr):
print("Trail",t)
n=int(input("Enter Number Of Elements"))
arr=[]
rnd(arr,n)
s=timeit.default_timer()
ss(arr,n)
e=timeit.default_timer()-s
print("Sorted Array")
print(arr)
[Link](n)
[Link](round(float(e)*10000000,2))
print("N CPU")
for t in range(tr):
print(N[t],CPU[t])
[Link](N,CPU)
[Link](N,CPU,color="red",marker="*",s=50)
[Link]("Selection Sort")
[Link]("Number of Values")
[Link]("Number of Time Taken")
[Link]()
6. Quick Sort
import random
import time
import timeit
import [Link] as plt
def rnd(arr,n):
for i in range(0,n):
ele=[Link](0,50)
[Link](ele)
def p(a,l,h):
i=l-1
pivote=a[h]
for j in range(l,h):
if a[j]<=pivote:
i+=1
a[i],a[j]=a[j],a[i]
a[i+1],a[h]=a[h],a[i+1]
return i+1
def qs(a,l,h):
if l<h:
pi=p(a,l,h)
qs(a,l,pi-1)
qs(a,pi+1,h)
N=[]
CPU=[]
tr=int(input("Enter number of trails"))
for t in range(tr):
print("Trail",t)
n=int(input("Enter Number Of Elements"))
arr=[]
rnd(arr,n)
s=timeit.default_timer()
qs(arr,0,n-1)
e=timeit.default_timer()-s
print("Sorted Array")
print(arr)
[Link](n)
[Link](round(float(e)*10000000,2))
print("N CPU")
for t in range(tr):
print(N[t],CPU[t])
[Link](N,CPU)
[Link](N,CPU,color="red",marker="*",s=50)
[Link]("Quick Sort")
[Link]("Number of Values")
[Link]("Number of Time Taken")
[Link]()
7. Binomial Co Efficient
a) Brute force
b) Dynamic Programmimg
def fact(n):
f=1
for i in range(1,n+1):
f = f*i
return f
def bnc(n,k):
return fact(n)//(fact(k)*fact(n-k))
def bncc(n,k):
c = [[0 for j in range(k+1)] for i in range(n+1)]
for i in range(n+1):
for j in range(min(i,k)+1):
if j==0 or j==i:
c[i][j]=1
else:
c[i][j]=c[i-1][j-1]+c[i-1][j]
return c[n][k]
n=int(input("Enter a number"))
k=int(input("Enter a number"))
r=bnc(n,k)
r2=bncc(n,k)
print(r)
print(r2)
8. Program to implement BFS
MAX = 100
visited = [0] * MAX
queue = [0] * MAX
def BFS(v):
visited[v] = 1
queue[0] = v
front = 0
rear = 0
while front <= rear:
v = queue[front]
print(f" {v}", end="")
front += 1
for i in range(1, n + 1):
if cost[v][i] == 1 and visited[i] == 0:
visited[i] = 1
rear += 1
queue[rear] = i
if __name__ == "__main__":
print("Enter the number of vertices in the graph: ")
n = int(input())
cost = [[0] * (n + 1) for _ in range(n + 1)]
print("Enter the cost matrix of the graph:")
for i in range(1, n + 1):
row_input = list(map(int, input().split()))
for j in range(n):
cost[i][j+1] = row_input[j]
for i in range(1,n+1):
visited[i] = 0
print("Enter the starting vertex:")
v = int(input())
print("BFS traversal of the graph is: ", end="")
BFS(v)
9. Polynomial
import time
import math
def bf(c, n, x):
sum = 0.0
for i in range(n + 1):
sum += (c[i] * [Link](x, i))
return sum
def hx(c, n, x):
r = c[0]
for i in range(1, n + 1):
r = r * x + c[i]
return r
n = int(input("Enter the degree of polynomial"))
c = [0] * (n + 1)
print("Enter the co-efficients from highest to lowest degree.")
for i in range(n, -1, -1):
c[i] = float(input())
x = float(input("Enter value of x."))
s = [Link]()
bf_res = bf(c, n, x)
e = [Link]()
tused = e - s
print("Brute Force result =", bf_res, ", time used =", tused, "sec.")
s = [Link]()
hx_res = hx(c, n, x)
e = [Link]()
tused = e - s
print("Horner's rule result =", hx_res, ", time used =", tused, "sec.")
10. MST Using Prims
import sys
def mk(k,ms,n):
mv=[Link]
for v in range(n):
if ms[v]==False and k[v] < mv:
mv=k[v]
mi=v
return mi
def pm(p,c,n):
tw=0
print("Edge Weight")
for i in range(1,n):
print(str(p[i]+1)+"-"+str(i+1)+" "+str(c[i][p[i]]))
tw+=c[i][p[i]]
return tw
def prm(c,n):
p=[None]*n
k=[[Link]]*n
ms=[False]*n
k[0]=0
p[0]=-1
for count in range(n):
u=mk(k,ms,n)
ms[u]=True
for v in range(n):
if c[u][v]>0 and ms[v]==False and c[u][v] < k[v]:
p[v]=u
k[v]=c[u][v]
tw=pm(p,c,n)
print("Total Cost of Minimum Spanning Tree:"+str(tw))
n=int(input("Enter the number of vertices: "))
c=[]
print("Enter the cost adjacency matrix:")
for i in range(n):
[Link](list(map(int,input().split())))
prm(c,n)
11. String Matching Problem Using Boyer-Moore
MAX_CHARS = 256
def max_val(a, b):
return a if a > b else b
def badCharHeuristic(pat, size, badchar):
for i in range(MAX_CHARS):
badchar[i] = -1
for i in range(size):
badchar[ord(pat[i])] = i
def patternsearch(text, pat):
m = len(pat)
n = len(text)
badchar = [-1] * MAX_CHARS
badCharHeuristic(pat, m, badchar)
s = 0 # s is shift of the pattern with respect to text
while s <= (n - m):
j=m-1
while j >= 0 and pat[j] == text[s + j]:
j -= 1
if j < 0:
print("Pattern occurs at position =", s)
s += (m - badchar[ord(text[s + m])] if s + m < n else 1)
else:
s += max_val(1, j - badchar[ord(text[s + j])])
# Main Code
text = input("Enter the text: ").rstrip('\n')
pat = input("Enter the pattern: ").rstrip('\n')
patternsearch(text, pat)
12. String Match Using KMP
def computeLPSArray(pat, M, lps):
length = 0 # length of the previous longest prefix suffix
lps[0] = 0 # lps[0] is always 0
i=1
while i < M:
if pat[i] == pat[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
def KMPSearch(pat, txt):
M = len(pat)
N = len(txt)
lps = [0] * M
computeLPSArray(pat, M, lps)
i = 0 # index for txt
j = 0 # index for pat
while i < N:
if pat[j] == txt[i]:
i += 1
j += 1
if j == M:
print(f"Found pattern at index {i - j}")
j = lps[j - 1]
elif i < N and pat[j] != txt[i]:
if j != 0:
j = lps[j - 1]
else:
i += 1
# Main Code
txt = input("Enter the text: ")
pat = input("Enter the pattern: ")
KMPSearch(pat, txt)
13. Programs:
a) Topological Ordering
def main():
n = int(input("Enter the no of vertices: "))
c = [[0 for j in range(n)] for i in range(n)]
indeg = [0] * n
flag = [0] * n
k=0
i=0
print("Enter the cost matrix (row by row):")
for i in range(n):
r = input().split()
for j in range(n):
c[i][j] = int(r[j])
for i in range(n):
for j in range(n):
indeg[j] += c[i][j]
print("Topological Order:")
while k < n:
for i in range(n):
if indeg[i] == 0 and flag[i] == 0:
print(i + 1, end = " ")
flag[i] = 1
k += 1
for j in range(n):
if c[i][j] >= 1:
indeg[j] -= 1
return
if __name__ == "__main__":
main()
b) Warshell
def warshall(c, n):
for k in range(n):
for i in range(n):
for j in range(n):
c[i][j] = c[i][j] or (c[i][k] and c[k][j])
print("Transitive Closure of the graph:")
for i in range(n):
for j in range(n):
print(c[i][j], end=" ")
print()
def main():
n = int(input("Enter the no of vertices: "))
c = []
print("Enter the adjacency matrix:")
for i in range(n):
row = list(map(int, input().split()))
[Link](row)
warshall(c, n)
main()
14. Floyd’s
INF = 999
# Print the solution matrix
def printSolution(V, D):
print("The following matrix shows the shortest distances between every pair of vertices")
for i in range(V):
for j in range(V):
if D[i][j] == INF:
print("%7s" % "INF", end=" ")
else:
print("%7d" % D[i][j], end=" ")
print()
# Implementing Floyd Warshall Algorithm
def floyd(V, C):
# Initialize distance matrix D
D = [[0] * V for _ in range(V)]
for i in range(V):
for j in range(V):
D[i][j] = C[i][j]
# Floyd-Warshall core logic
for k in range(V):
for i in range(V):
for j in range(V):
if D[i][j] > D[i][k] + D[k][j]:
D[i][j] = D[i][k] + D[k][j]
printSolution(V, D)
# Main Code
V = int(input("Enter the number of vertices: "))
# Create cost matrix
C = []
print("Enter the cost matrix row by row (space-separated):")
print("[Use 999 for Infinity, 0 for diagonal]")
for i in range(V):
row = list(map(int, input().split()))
[Link](row)
floyd(V, C)
15. Program to Find Subset
def sum_of_subsets(s,k,r):
global count,x,w,d,i
x[k]=1
if s+w[k]==d:
print("\nSubset %d="%(count+1),end="")
for i in range(k+1):
if x[i]:
print("%d"%w[i],end=" ")
count+=1
elif s+w[k]+w[k+1]<=d:
sum_of_subsets(s+w[k],k+1,r-w[k])
if s+r-w[k]>=d and s+w[k+1]<=d:
x[k]=0
sum_of_subsets(s,k+1,r-w[k])
if _name=="main_":
w=[0]*10
x=[0]*10
count=0
i=0
n=int(input("Enter the number of elements: "))
print("Enter the elements in ascending order:")
for i in range(n):
w[i]=int(input())
d=int(input("Enter the sum: "))
total_sum=0
for i in range(n):
x[i]=0
total_sum+=w[i]
if total_sum<d or w[0]>d:
print("\nNo subset possible\n")
else:
sum_of_subsets(0,0,total_sum)