PGM: 1

import time

import matplotlib.pyplot as plt

def linear_search(arr,n,key):

for i in range(n):

if arr[i]== key:

return i

return -1

def record(r):

results =[]

for _ in range(r):

n=int(input("\nEnter the number of elements of an array:"))

arr=list(map(int,input("Enter the elements of an array:").split()))

key=int(input("Enter the key element to be searched:"))

repeat = 10000

result = -1

start = time.time()

for _ in range(repeat):

result = linear_search(arr,n,key)

end=time.time()

if result!= -1:

print(f"Key {key} found at position {result}")

else:

print(f"Key {key} not found")

time_taken = (end-start)*1000

print(f"Time taken to search a key element = {time_taken} ms\n")

results.append((n,time_taken))

return results

def plot_results(results):

n_values = [result[0] for result in results]

times = [result[1] for result in results]

plt.figure()

plt.plot(n_values,times,'o-')

plt.xlabel('Number of Elements (n)')

plt.title('Linear Search Time Complexity')

plt.grid(True)

plt.show()

r=int(input("Enter the number of runs:"))

results = record(r)

plot_results(results)

PGM: 2

import matplotlib.pyplot as plt

import time

def binary_search(arr,low,high,key):

while low <= high:

mid = low + (high - low) // 2

if arr[mid] == key:

return mid

if arr[mid] < key:

low = mid +1

else:

high = mid - 1

return -1

def main():

n_values = []

times = []

r = int(input("Enter the number of runs: "))

for _ in range(r):

n=int(input("\nEnter the size of an array:"))

arr=list(map(int,input("Enter the array elements:").split()))

key=int(input("Enter the element to be searched:"))

repeat = 10000

result = -1

start = time.time()

for _ in range(repeat):

result = binary_search(arr,0,n-1,key)
 end=time.time()

if result!= -1:

print(f"Key {key} found at position{result}")

else:

print(f"Key {key} not found")

time_taken = (end-start)*1000

print(f"Time taken to search a element = {time_taken} milli second")

n_values.append(n)

times.append(time_taken)

plt.figure()

plt.plot(n_values,times,'o-')

plt.xlabel('Number of Elements')

plt.ylabel('Time Taken (milli second)')

plt.title('Binary Search Time complexity')

plt.grid(True)

plt.show()

if __name__ == "__main__":

main()

PGM: 3

def toh(n,source,temp,dest):

global count

if n > 0:

toh(n-1,source,dest,temp)

print(f"Move Disk{n}{source}->{dest}")

count += 1

toh(n-1,temp,source,dest)

source = 'S'

temp = 'T'

dest = 'D'

count = 0

n = int(input("Enter the number of disks: "))

print("Sequence is:")

toh(n,source,temp,dest)
print("The number of Moves: ",count)

PGM: 4

import timeit

import random

import matplotlib.pyplot as plt

def Input(array,n):

for i in range(0,n):

ele = random.randrange(1,50)

array.append(ele)

def selection_sort(array,size):

for ind in range(size):

mid_index = ind

for j in range(ind + 1,size):

if array[j] < array[mid_index]:

mid_index = j

(array[ind],array[mid_index]) = (array[mid_index],array[ind])

N = []

cpu = []

trial = int(input("Enter no of trials: "))

for t in range(0,trial):

array = []

print("-----> Trial no: ",t+1)

n = int(input("Enter the number of elements: "))

Input(array,n)

start = timeit.default_timer()

selection_sort(array,n)

times = timeit.default_timer() - start

print("Sorted array: ")

print(array)

N.append(n)

cpu.append(round(float(times) * 1000000,2))

print("N cpu")

for t in range(0, trial):

print(N[t],cpu[t])
plt.plot(N,cpu)

plt.scatter(N,cpu,color="red",marker="*",s=50)

plt.xlabel('Array Size - N')

plt.ylabel('CPU processing time')

plt.title('Selection Sort Time Efficiency')

plt.grid(True)

plt.show()

PGM: 5

def power_bruteforce(a,n):

result=1

for i in range(n):

result*=a

return result

def power_divide_conquer(a,n):

if n==0:

return 1

elif n%2==0:

return power_divide_conquer(a*a,n//2)

else:

return a*power_divide_conquer(a*a,n//2)

a,n=map(int, input("Enter the value of a and n:").split())

result_brute=power_bruteforce(a,n)

result_divide_conquer=power_divide_conquer(a,n)

print("Result using brute force:",result_brute)

print("Result using divide and conquer:",result_divide_conquer)

PGM: 6

import timeit

import random

import matplotlib.pyplot as plt

def Input(Array, n):

for i in range(0, n):

ele = random.randrange(1, 50)

def partition(Array, low, high):

i = (low - 1)

pivot = Array[high]

for j in range(low, high):

if Array[j] <= pivot:

i=i+1

Array[i], Array[j] = Array[j], Array[i]

Array[i + 1], Array[high] = Array[high], Array[i + 1]

return (i + 1)

def quickSort(Array, low, high):

if low < high:

pi = partition(Array, low, high)

quickSort(Array, low, pi - 1)

quickSort(Array, pi + 1, high)

N = []

CPU = []

trail = int(input("Enter no of trails: "))

for t in range(0, trail):

Array = []

print("-----> Trail no:", t + 1)

n = int(input("Enter number of elements: "))

Input(Array, n)

start = timeit.default_timer()

quickSort(Array, 0, n - 1)

times = timeit.default_timer() - start

print("Sorted Array:")

print(Array)

N.append(n)

CPU.append(round(float(times) * 1000000, 2))

print("N CPU")

for t in range(0, trail):

print(N[t], CPU[t])

plt.plot(N, CPU)
plt.scatter(N, CPU, color="red", marker="*", s=50)

plt.xlabel('Array Size - N')

plt.ylabel('CPU Processing Time')

plt.title('Quick Sort Time efficiency')

plt.show()

PGM: 7

def factorial(n):

fact=1

for i in range(2,n+1):

fact*=i

return fact

def binomialCoeff_bruteForce(n,k):

return factorial(n) // (factorial(k)*factorial(n-k))

def binomialCoeff_DP(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 the value of n: "))

k=int(input("Enter the value of k: "))

result_bruteForce=binomialCoeff_bruteForce(n,k)

result_DP=binomialCoeff_DP(n,k)

print(f"Binomial Coefficient(Brute Force):{result_bruteForce}")

print(f"Binomial Coefficient(Dynamic Programming):{result_DP}")

PGM: 8

INF = 99999

def printSolution(V, D):

print("The following matrix shows the shortest distance 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()

def floyd(V, C):

D = [[0]*V for _ in range(V)]

for i in range(V):

for j in range(V):

D[i][j] = C[i][j]

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)

V = int(input("Enter the number of vertices: "))

C = [[0]*V for _ in range(V)]

print("Enter the cost matrix row by row (space-separated):")

print("[Enter 99999 for Infinity]")

print("[Enter 0 for cost(i,i)]")

for i in range(V):

C[i] = list(map(int, input().split()))

floyd(V, C)

PGM: 9

import time

import math

def bruteforce(coef, n, x):

sum = 0.0

for i in range(n+1):

sum += coef[i] * math.pow(x, i)

return sum
def hornersrule(coef, n, x):

result = coef[n]

for i in range(n-1, -1, -1):

result = result * x + coef[i]

return result

n = int(input("Enter the degree of the polynomial: "))

coef = [0]*(n+1)

print("Enter the coefficients from highest degree to lowest:")

for i in range(n, -1, -1):

coef[i] = int(input())

x = float(input("Enter the value of x: "))

start = time.time()

brute_force_result = bruteforce(coef, n, x)

end = time.time()

time_used = end - start

print(f"Brute force result: {brute_force_result:.2f}, time used: {time_used:.6f} seconds")

start = time.time()

horners_rule_result = hornersrule(coef, n, x)

end = time.time()

time_used = end - start

print(f"Horner's rule result: {horners_rule_result:.2f}, time used: {time_used:.6f} seconds")

PGM: 10

MAX_CHARS = 256

def max(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

while s <= (n - m):

j = m-1

while j >= 0 and pat[j] == text[s + j]:

j -= 1

if j < 0:

print("\n Pattern occurs at position =", s)

s += m - badchar[ord(text[s + m])] if (s + m)<n else 1

else:

s += max(1, j-badchar[ord(text[s + j])])

text = input("Enter the text:").rstrip('\n')

pat =input("Enter the pattern:").rstrip('\n')

patternsearch(text,pat)

PGM: 11

def computeLPSArray(pat, M, lps):

length = 0

lps[0] = 0

i=1

while i < M:

if pat[i] == pat[length]:

length += 1

lps[i] = length

i += 1

else:

if length !=0:

lenght = 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=j=0

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

txt = input("Enter the txt:")

pat = input("Enter the pattern:")

KMPSearch(pat, txt)

PGM:12

MAX = 100

c= [[0]*MAX for _ in range(MAX)]

visited = [0]*MAX

queue = [0]*MAX

def BFS(v):

front = 0

rear = -1

visited[v] = 1

queue[rear + 1] = v

rear +=1

while front <= rear:

v = queue[front]

front += 1
 print(f"{v} ", end="")

for i in range(1, n+1):

if c[v][i] == 1 and visited[i] == 0:

queue[rear +1] = i

rear += 1

visited[i] = 1

if __name__=="__main__":

print("Enter the number of vertices in the graph: ")

n = int(input())

print("Enter the cost matrix of the graph: ")

for i in range(1, n+1):

c[i] = [0] + list(map(int, input().split()))

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)

PGM:13

import sys

def minKey(key, mstSet, n):

min_value = sys.maxsize

for v in range(n):

if mstSet[v] == False and key[v] < min_value:

min_value = key[v]

min_index = v

return min_index

def printMST(parent, c, n):

totalWeight = 0

print("Edge Weight")

for i in range(1, n):

print(str(parent[i]+1) + " - " + str(i+1) + " " + str(c[i][parent[i]]))

totalWeight += c[i][parent[i]]
 return totalWeight

def primMST(c, n):

parent = [None]*n

key = [sys.maxsize]*n

mstSet = [False]*n

key[0] = 0

parent[0] = -1

for count in range(n):

u = minKey(key, mstSet, n)

mstSet[u] = True

for v in range(n):

if c[u][v] > 0 and mstSet[v] == False and c[u][v] < key[v]:

parent[v] = u

key[v] = c[u][v]

totalWeight = printMST(parent, c, n)

print("Total cost of the minimum spanning tree: " + str(totalWeight))

n = int(input("Enter the number of vertices: "))

c = []

print("Enter the cost adjacency matrix:")

for i in range(n):

c.append(list(map(int, input().split())))

primMST(c, n)

PGM: 14A

def main():

n = int(input("Enter the number of vertices: "))

count = 0

c = [[0 for _ in range(n)] for _ in range(n)]

indeg = [0] * n

flag = [0] * n

i, j, k = 0, 0, 0

print("Enter the cost matrix (roe by row):")

for i in range(n):

row = input().split()
 for j in range(n):

c[i][j] = int(row[j])

for i in range(n):

for j in range(n):

indeg[i] += c[j][i]

print("The topological order is:")

while count < n:

for k in range(n):

if indeg[k] == 0 and flag[k] == 0:

print(f"{k+1:3}", end="")

flag[k] = 1

count += 1

for i in range(n):

if c[k][i] == 1:

indeg[i] -=1

return 0

if __name__ == "__main__":

main()

PGM: 14B

def warshalls(c, n):

for k in range(n):

for i in range(n):

for j in range(n):

if c[i][j] or (c[i][k] and c[k][j]):

c[i][j] = 1

print("The transitive closure of the graph is:")

for i in range(n):

for j in range(n):

print(c[i][j], end=" ")

print()

def main():

n = int(input("Enter the number of vertices: "))

c = []
 print("Enter the adjacency cost matrix:")

for i in range(n):

row = list(map(int, input().split()))

c.append(row)

warshalls(c, n)

main()

PGM: 15

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="")

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:"))

sum = 0

for i in range(n):

x[i] = 0
 sum += w[i]

if sum < d or w[0] > d:

print("\nNo subset possible\n")

else:

sum_of_subsets(0, 0, sum)