INDEX
[Link]. DATE NAME OF THE EXPERIMENT SIGN
Implement recursive and non-recursive algorithms and study
1
the order of growth from log2n to n!..
Divide and Conquer - Strassen’s Matrix Multiplication
2
Decrease and Conquer - Topological Sorting
3
4 Transform and Conquer - Heap Sort
Dynamic programming - Coin change Problem, Warshall’s and
5 Floyd‘s algorithms, Knapsack Problem
Greedy Technique – Dijkstra’s algorithm, Huffman Trees and
6
codes
Iterative improvement - Simplex Method
7
Backtracking – N-Queen problem, Subset Sum Problem
8
Branch and Bound - Assignment problem, Traveling Salesman
9 Problem
1
EXP NO: 1 RECURSIVE ALGORITHM
Date:
EX-1.1 FIBONACCI SERIES
AIM:
ALGORITHM:
2
CODING:
def recursive_fibonacci(n):
if n <= 1:
return n
else:
return(recursive_fibonacci(n-1) + recursive_fibonacci(n-2))
n_terms = 10
# check if the number of terms is valid
if n_terms <= 0:
print("Invalid input ! Please input a positive value")
else:
print("Fibonacci series:")
for i in range(n_terms):
print(recursive_fibonacci(i))
# Coding 2 For Recursive
def recursive_algorithm(n):
if n <= 1:
return 1
return recursive_algorithm(n-1) * n
# Coding 3 For Recursive
def non_recursive_algorithm(n):
result = 1
for i in range(1, n+1):
result *= i
return result
3
Output
Fibonacci series:
0
1
1
2
3
5
8
13
21
34
RESULT:
4
EX-1.2 BINARY SEARCH USING RECURSION
Date:
AIM:
ALGORITHM:
5
CODING:
def binarySearch(arr, l, r, x):
if r >= l:
mid = l + (r - l) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)
else:
return binarySearch(arr, mid + 1, r, x)
else:
return -1
arr = [2, 3, 4, 10, 40]
x = 10
result = binarySearch(arr, 0, len(arr)-1, x)
if result != -1:
print("Element is present at index % d" % result)
else:
print("Element is not present in array")
OUTPUT:
Element is present at index 3
Time Complexity: O(log n)
RESULT:
6
EX-1.3 BINARY SEARCH USING ITERATION METHOD
Date:
AIM:
ALGORITHM:
7
CODING:
def binarySearch(v, To_Find):
lo = 0
hi = len(v) - 1
while hi - lo > 1:
mid = (hi + lo) // 2
if v[mid] < To_Find:
lo = mid + 1
else:
hi = mid
if v[lo] == To_Find:
print("Found At Index", lo)
elif v[hi] == To_Find:
print("Found At Index", hi)
else:
print("Not Found")
if name == ' main ':
v = [1, 3, 4, 5, 6]
To_Find = 1
binarySearch(v, To_Find)
To_Find = 10
binarySearch(v, To_Find)
OUTPUT:
Found At Index 4
Not Found
RESULT:
8
EXP NO: 2 FINDING MINIMUM AND MAXIMUM ELEMENT IN ARRAY USING DIVIDE
AND CONQUER
Date:
AIM:
ALGORITHM:
9
CODING:
def divideAndConquer_Max(arr, ind, len):
maximum = -1;
if (ind >= len - 2):
if (arr[ind] > arr[ind + 1]):
return arr[ind];
else:
return arr[ind + 1];
maximum = divideAndConquer_Max(arr, ind + 1, len);
if (arr[ind] > maximum):
return arr[ind];
else:
return maximum;
def divideAndConquer_Min(arr, ind, len):
minimum = 0;
if (ind >= len - 2):
if (arr[ind] < arr[ind + 1]):
return arr[ind];
else:
return arr[ind + 1];
minimum = divideAndConquer_Min(arr, ind + 1, len);
if (arr[ind] < minimum):
return arr[ind];
else:
return minimum;
if __name == '__main__':
minimum, maximum = 0, -1;
# array initialization
arr = [6, 4, 8, 90, 12, 56, 7, 1, 63];
maximum = divideAndConquer_Max(arr, 0, 9);
minimum = divideAndConquer_Min(arr, 0, 9);
print("The minimum number in the array is: ", minimum);
print("The maximum number in the array is: ", maximum);
10
OUTPUT
The minimum number in the array is: 1
The maximum number in the array is: 90
RESULT:
11
EXP NO: 2-2 STRASSEN’S MULTIPLICATION
Date:
AIM:
ALGORITHM:
12
CODING:
import numpy as np
def strassen(A, B):
if [Link] == (1, 1): # base case
return A * B
else: # divide matrices into quadrants
n = [Link][0]
m = n // 2
a = A[:m, :m]
b = A[:m, m:]
c = A[m:, :m]
d = A[m:, m:]
e = B[:m, :m]
f = B[:m, m:]
g = B[m:, :m]
h = B[m:, m:]
# compute 7 matrix multiplications
p1 = strassen(a, f - h)
p2 = strassen(a + b, h)
p3 = strassen(c + d, e)
p4 = strassen(d, g - e)
p5 = strassen(a + d, e + h)
p6 = strassen(b - d, g + h)
p7 = strassen(a - c, e + f)
# compute the final product
c1 = p5 + p4 - p2 + p6
c2 = p1 + p2
c3 = p3 + p4
c4 = p1 + p5 - p3 - p7
# concatenate the quadrants
C = [Link](([Link]((c1, c2), axis=1), [Link]((c3, c4), axis=1)), axis=0)
return C
# test the function
A = [Link]([[1, 2], [3, 4]])
B = [Link]([[5, 6], [7, 8]])
print(strassen(A, B))
OUTPUT:
[[19 22]
[43 50]]
RESULT:
13
EXP NO: 3 DECREASE AND CONQUER - TOPOLOGICAL SORTING
Date:
AIM:
ALGORITHM:
14
CODING:
from collections import defaultdict
class Graph:
def __init__(self,vertices):
[Link] = defaultdict(list) #dictionary containing adjacency List
self.V = vertices #No. of vertices
def addEdge(self,u,v):
[Link][u].append(v)
def topologicalSortUtil(self,v,visited,stack):
visited[v] = True
for i in [Link][v]:
if visited[i] == False:
[Link](i,visited,stack)
[Link](0,v)
def topologicalSort(self):
visited = [False]*self.V
stack =[]
for i in range(self.V):
if visited[i] == False:
[Link](i,visited,stack)
print (stack)
g= Graph(6)
[Link](5, 2);
[Link](5, 0);
[Link](4, 0);
[Link](4, 1);
[Link](2, 3);
[Link](3, 1);
print ("Following is a Topological Sort of the given graph")
15
[Link]()
OUTPUT
Following is a Topological Sort of the given graph
[5, 4, 2, 3, 1, 0]
RESULT:
16
EXP NO:4 TRANSFORM AND CONQUER - HEAP SORT
Date:
AIM:
ALGORITHM:
17
CODING
def heapify(arr, n, i):
largest = il
= 2 * i + 1r
=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]) # swap
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])
18
OUTPUT
Sorted array is
11
12
13
RESULT:
19
Exp No: 5 DYNAMIC CODINGMING
Date:
EX-5.1 COIN CHANGE PROBLEM
AIM:
ALGORITHM
20
CODING
INF = 100000
def min(x, y):
if x < y:
return x
return y
def coin_change(d, n, k):
M = [0]*(n+1)
for j in range(1, n+1):
minimum = INF
for i in range(1, k+1):
if(j >= d[i]):
minimum = min(minimum, 1+M[j-d[i]])
M[j] = minimum
return M[n]
if name == '__main ':
d = [0, 1, 2, 3]
print(coin_change(d, 5, 3))
OUTPUT
RESULT:
21
EX-5.2 WARSHALL’S AND FLOYD’S ALGORITHM
Date:
AIM:
ALGORITHM:
22
CODING:
nV = 4
INF = 999
def floyd_warshall(G):
distance = list(map(lambda i: list(map(lambda j: j, i)), G))
for k in range(nV):
for i in range(nV):
for j in range(nV):
distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
print_solution(distance)
def print_solution(distance):
for i in range(nV):
for j in range(nV):
if(distance[i][j] == INF):
print("INF", end=" ")
else:
print(distance[i][j], end=" ")
print(" ")
G = [[0, 3, INF, 5],
[2, 0, INF, 4],
[INF, 1, 0, INF],
[INF, INF, 2, 0]]
floyd_warshall(G)
23
OUTPUT
0 3 7 5
2 0 6 4
3 1 0 5
5 3 2 0
RESULT:
24
EX-5.3 KNAPSACK PROBLEM
Date:
AIM:
ALGORITHM
25
CODING:
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
220
RESULT
26
EXP NO: 6 GREEDY TECHNIQUES
Date:
EX-6.1 DIJIKSTRA’S ALGORITHM
AIM
ALGORITHM
27
CODING:
class Graph():
def __init__(self, vertices):
self.V = vertices
[Link] = [[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])
def minDistance(self, dist, sptSet):
min = 1e7
for v in range(self.V):
if dist[v] < min and sptSet[v] == False:
min = dist[v]
min_index = v
return min_index
def dijkstra(self, src):
dist = [1e7] * self.V
dist[src] = 0
sptSet = [False] * self.V
for cout in range(self.V):
u = [Link](dist, sptSet)
sptSet[u] = True
for v in range(self.V):
if ([Link][u][v] > 0 and
sptSet[v] == False and
dist[v] > dist[u] + [Link][u][v]):
dist[v] = dist[u] + [Link][u][v]
28
[Link](dist)
g = Graph(9)
[Link] = [[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]
]
[Link](0)
OUTPUT
Vertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14
RESULT
29
EX-6.2 HUFFMAN TREES AND CODES
Date:
AIM
ALGORITHM
30
CODING:
string = 'BCAADDDCCACACAC'
class NodeTree(object):
def __init__(self, left=None, right=None):
[Link] = left
[Link] = right
def children(self):
return ([Link], [Link])
def nodes(self):
return ([Link], [Link])
def __str (self):
return '%s_%s' % ([Link], [Link])
def huffman_code_tree(node, left=True, binString=''):
if type(node) is str:
return {node: binString}
(l, r) = [Link]()
d = dict()
[Link](huffman_code_tree(l, True, binString + '0'))
[Link](huffman_code_tree(r, False, binString + '1'))
return d
freq = {}
for c in string:
if c in freq:
freq[c] += 1
else:
freq[c] = 1
freq = sorted([Link](), key=lambda x: x[1], reverse=True)
nodes = freq
31
while len(nodes) > 1:
(key1, c1) = nodes[-1]
(key2, c2) = nodes[-2]
nodes = nodes[:-2]
node = NodeTree(key1, key2)
[Link]((node, c1 + c2))
nodes = sorted(nodes, key=lambda x: x[1], reverse=True)
huffmanCode = huffman_code_tree(nodes[0][0])
print(' Char | Huffman code ')
print(' --------------------- ')
for (char, frequency) in freq:
print(' %-4r |%12s' % (char, huffmanCode[char]))
OUTPUT
Char | Huffman code
----------------------
'C' | 0
'A' | 11
'D' | 101
'B' | 100
RESULT:
32
EXP NO: 7 ITERATIVE IMPROVEMENT - SIMPLEX ALGORITHM
Date:
AIM:
ALGORITHM :
33
Coding :
### Import the neccessary libraries
import numpy as np
import scipy as sp
# Get matrices
c = [-8, -12, -22]
A = [[17, 27, 34], [12, 21, 15]]
b = [91800, 42000]
# define the upper bound and the lower bound
R = (0, None)
T = (0, None)
M = (0, None)
# Implementing the Simplex Algorithm
from [Link] import linprog
# Solve the problem by Simplex method in Optimization
res = linprog(c, A_ub=A, b_ub=b, bounds=(R, T, M), method='simplex', options={"disp": True}) #
linear
programming problem
print(res)
34
OUTPUT:
Optimization terminated successfully.
Current function value: -59400.000000
Iterations: 3
con: array([], dtype=float64)
fun: -59400.0
message: 'Optimization terminated successfully.'
nit: 3
slack: array([ 0., 1500.])
status: 0
success: True
x: array([ 0., 0., 2700.])
RESULT:
35
EXP NO: 8 BACKTRACKING
Date:
EX-8.1 N-QUEEN PROBLEM
AIM:
ALGORITHM:
36
CODING:
N = int(input("Enter the number of queens : "))
board = [[0]*N for _ in range(N)]
def attack(i, j):
for k in range(0,N):
if board[i][k]==1 or board[k][j]==1:
return True
for k in range(0,N):
for l in range(0,N):
if (k+l==i+j) or (k-l==i-j):
if board[k][l]==1:
return True
return False def N_queens(n):
if n==0:
return True
for i in range(0,N):
for j in range(0,N):
if (not(attack(i,j))) and (board[i][j]!=1):
board[i][j] = 1
if N_queens(n-1)==True:
return True
board[i][j] = 0
return False
N_queens(N)
for i in board:
print (i)
37
OUTPUT:
Enter the number of queens : 4
[0, 1, 0, 0]
[0, 0, 0, 1]
[1, 0, 0, 0]
[0, 0, 1, 0]
RESULT:
38
EX-8.2 SUBSET SUM PROBLEM
Date:
AIM:
ALGORITHM:
39
CODING:
def isSubsetSum(set, n, sum) :
if (sum == 0) :
return True
if (n == 0 and sum != 0) :
return False
if (set[n - 1] > sum) :
return isSubsetSum(set, n - 1, sum);
return isSubsetSum(set, n-1, sum) or isSubsetSum(set, n-1, sum-set[n-1])
set = [3, 34, 4, 12, 5, 2]
sum = 9
n = len(set)
if (isSubsetSum(set, n, sum) == True) :
print("Found a subset with given sum")
else :
print("No subset with given sum")
OUTPUT:
Found a subset with given sum
40
# A RECURSIVE SOLUTION FOR SUBSET SUM PROBLEM
# Returns true if there is a subset of set[ ] with sun equal to given sum
def sum_of_subset(s,k,rem):
x[k]=1
if s+my_list[k]==target_sum:
list1=[]
for i in range (0,k+1):
if x[i]==1:
[Link](my_list[i])
print( list1 )
elif s+my_list[k]+my_list[k+1]<=target_sum :
sum_of_subset(s+my_list[k],k+1,rem-my_list[k])
if s+rem-my_list[k]>=target_sum and s+my_list[k+1]<=target_sum :
x[k]=0
sum_of_subset(s,k+1,rem-my_list[k])
my_list=[]
n=int(input("Enter number of elements"))
total=0
for i in range (0,n):
ele=int(input())
my_list.append(ele)
total=total+ele
my_list.sort()
target_sum=int(input("Enter required Sum"))
x=[0]*(n+1)
sum_of_subset(0,0,total)
OUTPUT:
Enter number of elements5
10
15
15
20
30
Enter required Sum30
[10, 20]
[15, 15]
[30]
RESULT:
41
EXP NO: 9 BRANCH AND BOUND -- TRAVELLING SALESMAN PROBLEM
Date:
AIM:
ALGORITHM
42
CODING:
from sys import maxsize
from itertools import permutations
V=4
def travellingSalesmanProblem(graph, s):
vertex = []
for i in range(V):
if i != s:
[Link](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(travellingSalesmanProblem(graph, s))
OUTPUT
80
RESULT:
43