DEPARTMENT OF ARTIFICIAL

INTELLIGENCE & DATA SCIENCE

AD3351 – DESIGN AND ANALYSIS OF

ALGORITHM LABORATORY

[Link]…………………………………..…
NAME……………………………………….
 SRIRANGAPOOPATHICOLLEGEOFENGINEERING
Alampoondi-604151,Gingee-TK

BONAFIDECERTIFICATE
NAME :

YEAR/SEM :

BRANCH :

SUBJECTCODE :

SUBJECTNAME :

REGISTERNO. :

Certified that this is a bonafide record of work done by the above student in the

_____________________________________________________________________________

LABORATORY d u r i n g t h e Academic year ____________________

Signature of Staff in charge Head of the Department

Submitted for the Practical Examination HeldOn

Internal Examiner External Examiner

 TABLE OF CONTENTS

STAFF
[Link] DATE TITLE OF THE EXPERIMENT MARKS
SIGN
 TABLE OF CONTENTS

STAFF
[Link] DATE TITLE OF THE EXPERIMENT MARKS
SIGN
 [Link](a) IMPLEMENT RECURSIVE ALGORITHM.

Date:

AIM:

To Implement a python program for recursive algorithm.

PROCEDURE:

(FACTORIAL)

STEP1:start

STEP2:Read number n

STEP3:Call factorial(n)

STEP4:Print factorial(n)

STEP5:StopFactorial(n)

STEP1:Ifn==1 return1

STEP2:Else

Fact=n=factorial(n-1)

STEP3:ReturnFact
 PROGRAM/SOURCECODE:

def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n - 1)

n = int(input('Enter a number:'))
result = factorial(n)
print("Factorial of", n, ":", result)

OUTPUT:
Enter a number : 6
Factorial of 5 is 720

RESULT:
Thus, the program to implement the concept of Recursive algorithm using Python has been executed
successfully.
 [Link](b) IMPLEMENTNON-RECURSIVE
Date: ALGORITHM.

AIM:
To Implement a python program for Non-Recursive algorithm.

PROCEDURE:

(BINARYSEARCH)

STEP1:set beg=lower_bound,end=upper_bound,pos=-1
STEP2:repeat steps3and4whilebeg <=end
STEP3:setmid = (beg+end)/2
STEP4:ifa[mid]=valset pos
= mid
printposgo to
step 6
else if a[mid] > val
setend=mid-1else set
beg = mid + 1
STEP5: if pos = -1
print"value isnotpresent inthe array"
STEP6:exit.
PROGRAM/SOURCECODE:

def binary_search(arr, x):

low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
low = mid + 1
else:
high = mid - 1
return -1

arr = [2, 3, 4, 10, 40]

x = 10
result = binary_search(arr, x)
if result != -1:
print(f"Element {x} is present at index {result+1}")
else:
print(f"Element {x} is not present in the array")

OUTPUT:

Element 10 is present at index 4

RESULT:
Thus, the program to implement the concept of Non- Recursive algorithm using Python has been
executed successfully.
 [Link] DIVIDE AND CONQUER
STRASSEN’S MATRIX MULTIPLICATION
Date:

AIM:

To implement Strassen’s Matrix Multiplication using Divide and Conquer.

PROCEDURE:

STEP1:Divide a matrix of order of 2*2 recursively till we get the matrix of 2*2.

STEP2:Use the previous set of formulas to carry out 2*2 matrix multiplication.

STEP3:In this eight multiplication and four additions, subtraction are performed.

STEP4: Combine the result of two matrixes to find the final product or final matrix.

-
PROGRAM/SOURCECODE:

import numpy as np

def split(matrix):
"""
Splits a given matrix into quarters. Input: nxn matrix
Output: tuple containing 4 n/2 x n/2 matrices corresponding to a, b, c, d
"""
row, col = [Link]
row2, col2 = row//2, col//2
return matrix[:row2, :col2], matrix[:row2, col2:], matrix[row2:, :col2], matrix[row2:,
col2:]

def strassen(x, y):

"""
Computes matrix product by divide and conquer approach, recursively. Input: nxn
matrices x and y
Output: nxn matrix, product of x and y
"""
if len(x) == 1:
return x * y # This line was missing proper indentation

a, b, c, d = split(x)
e, f, g, h = split(y)

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)

c11 = p5 + p4 - p2 + p6
c12 = p1 + p2
 c21 = p3 + p4
c22 = p1 + p5 - p3 - p7

c = [Link](([Link]((c11, c12)),
[Link]((c21, c22)))) # Fixed incomplete line
return c # Fixed indentation

A = [Link]([[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]])

B = [Link]([[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]])

C = strassen(A, B)
print(C)

OUTPUT:

[[90 100110 120]

[202 228 254 280]

[314 356 398 440]

[426 484 542 600]]

RESULT:
Thus, the python program to implement Strassen’s Matrix Multiplication using Divide and Conquer has
been executed successfully.
 [Link] DECREASE AND CONQUER
Date: TOPOLOGICAL SORTING

AIM:

To implement Topological sorting using Decrease and Conquer.

PROCEDURE:

STEP1: Start
STEP2: Find a vertex that has indegree = 0 (no incoming edges)
STEP3: Remove all the edges from that vertex that go outward (make it's outdegree = 0, remove outgoing
edges)
STEP4: Add that vertex to the array representing topological sorting of the graph
STEP5: Repeat till there are no more vertices left.
STEP6: Stop.
PROGRAM/SOURCECODE:

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](v)

def topologicalSort(self):
visited = [False] * self.V
stack = []
for i in range(self.V):
if visited[i] == False:
[Link](i, visited, stack)

print("Following is a Topological Sort of the given graph:")

print(stack[::-1])

if _name_ == '_main_':
g = Graph(6)
[Link](5, 2)
[Link](5, 0)
[Link](4, 0)
[Link](4, 1)
[Link](2, 3)
 [Link](3, 1)

[Link]()

OUTPUT:

FollowingisaTopologicalSortofthegiven

graph:[5, 4, 2, 3, 1, 0]

RESULT:

Thus, the python program to implement Topological Sorting using Decrease and Conquer has been
executed successfully
 [Link] TRANSFORM AND CONQUER
HEAP SORT
Date:

AIM:

To implement Heap Sort using Transform and Conquer.

PROCEDURE:

STEP1: Build a max heap from the input data.

STEP2: At this point, the maximum element is stored at the root of the [Link] it with the last item

of the heap followed by reducing the size of the heap by 1. Finally, heapify the root of the tree.

STEP3: Repeat step 2 while the size of the heap is greater than 1.
PROGRAM/SOURCECODE:

def heapify(arr, N, i):

largest = i
l=2*i+1
r=2*i+2

if l < N and arr[largest] < 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] # swap

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)

if __name__ == "__main__":
arr = [28, 11, 17, 13, 18, 29, 25]
heapSort(arr)
print("Sorted array in ascending order is:")
for i in arr:
print(i, end=" ")

OUTPUT:
Therefore, the sorted array is[11,13,17,18,25,28,29].
RESULT:
Thus,the program to implement character recognition using multilayer perceptron has been executed
successfully.
 [Link](a) DYNAMIC PROGRAMMING
COIN CHANGING PROBLEM.
Date:

AIM:

To implement Coin Changing Problem using Dynamic programming.

PROCEDURE:

STEP1: Start.

STEP2: Get input amount as a amt.

STEP3: if amount =0,then return 0.

STEP4: if minimum of coins array > amount, then return -1.

STEP5: Define one array called dp, of size amount + 1, and fill this with -1.

STEP6: for i in range coins array. if i > length of dp – 1, then skip the next part, go for the next

iteration. dp[i] := 1.

STEP7: Return dp[amount].

STEP8: Stop.
PROGRAM/SOURCECODE:

class Solution(object):
def coinChange(self, coins, amount):
if amount == 0:
return 0

if min(coins) > amount:

return -1

dp = [float('inf')] * (amount + 1)
dp[0] = 0 # Base case

for j in range(1, amount + 1):

for coin in coins:
if j - coin >= 0:
dp[j] = min(dp[j], dp[j - coin] + 1)

return dp[amount] if dp[amount] != float('inf') else -1

ob1 = Solution()
amt = int(input("Enter the amount: "))
print([Link]([1, 2, 5], amt))

OUTPUT:
Enter the amount : 123

RESULT:
Thus, the python program to implement the Coin Changing Problem using Dynamic
Programming has been executed successfully.
 [Link](b)
WARSHALL’S AND FLOYD’S ALGORITHMS.

Date:

AIM:

To implement the Warshall’s and Flyod’s algorithms using Dynamic Programming.

PROCEDURE:

STEP1: Start

STEP2: Get input ‘n’ where n=no of vertices

STEP3: Assign A=matrix of dimension n*n

STEP4: fork=1 ton

STEP5: for i= 1ton

STEP6: forj= 1ton

STEP7: Ak[i, j] =min(Ak-1[i,j],Ak-1[i,k]+Ak-1[k,j])

STEP8: ReturnA

STEP9: Stop
PROGRAM/SOURCECODE:

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):
print("Shortest distances between every pair of vertices:")
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)
OUTPUT:
0375
2064
3105
5320

RESULT:

Thus, the python program to Warshall’s and Floyd’s algorithms using Dynamic
Programming has been executed successfully.
 [Link](c)
KNAPSACK PROBLEM
Date:

AIM:

To Write a program to Knapsack Problem using Dynamic Programming.

PROCEDURE:

STEP1: Start

STEP2: Calculate the ratio (value/weight) for each item.

STEP3:Sort all the items in decreasing order of the ratio.

STEP4: Initializeres =0,curr_cap= given_cap.

STEP5: Do the following for every item “i” in the sorted order

STEP6: If the weight of the current item is less than or equal to the remaining capacity then add the value of

that item into the result

STEP7: Else add the current item as much as we can and break out of the loop.

STEP8: Return res.

STEP9: Stop
PROGRAM/SOURCECODE:

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:
Thus, by using Dynamic Programming, the Knapsack Problem has been demonstrated.
 [Link](a) GREEDY TECHNIQUE
Date: DIJKSTRA’S ALGORITHM

AIM:

To implement Dijkstras Algorithm using Greedy Technique.

PROCEDURE:

STEP1: Start

STEP2: Create a set sptSet that keeps track of vertices included in the shortest-path tree.

STEP3: Assign a distance value to all vertices in the input graph. Initialize all distancevalues as infinite.
Assign the distance value as 0 for the source vertex so that it is picked first.

STEP4: While sptSet doesn’t include all vertices, pick a vertex u which is not therein sptSet and
has a minimum distance.

STEP5: Include u to sptSet.

STEP6: Then update distance value of all adjacent vertices of u.

STEP7: To update the distance values, iterate through all adjacent vertices.

STEP8: For every adjacent vertex v, if sum of the distance value of u (from source) andweight of edge u-v,
is less than the distance value of v, then update the distance value of v.

STEP9: Stop
PROGRAM/SOURCECODE:

import sys

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", dist[node])

def minDistance(self, dist, sptSet):

min_val = [Link]
min_index = -1

for u in range(self.V):
if dist[u] < min_val and not sptSet[u]:
min_val = dist[u]
min_index = u
return min_index

def dijkstra(self, src):

dist = [[Link]] * self.V
dist[src] = 0
sptSet = [False] * self.V

for _ in range(self.V):
x = [Link](dist, sptSet)
sptSet[x] = True

for y in range(self.V):
if [Link][x][y] > 0 and not sptSet[y] and dist[y] > dist[x] +
[Link][x][y]:
dist[y] = dist[x] + [Link][x][y]

[Link](dist)
 if __name__ == "__main__":
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 DistancefromSource
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14

RESULT:
Thus, the python program to implement Dijkstras algorithm using Greedy Technique has been executed
successfully.
 [Link](b)
Date: HUFFMAN TREES AND CODES

AIM:

To implement Huffman Trees and Codes using Greedy technique

PROCEDURE:

STEP1: Start

STEP2: Input is an array of unique characters along with their frequency of occurrences

STEP3: Create a leaf node for each unique character and build a min heap of all leaf nodes(Min Heap is

used as a priority queue. The value of frequency field is used tocompare two nodes in min heap.

Initially, the least frequent character is at root)

STEP4: Extract two nodes with the minimum frequency from the min heap

STEP6: Createanewinternalnodewithafrequencyequaltothesumofthetwonodesfrequencies.

Make the first extracted node as its left child and the other extractednode as its right child. Add

this node to the min heap.

STEP7: Repeat steps 2 and 3 until the heap contains only one node. The remaining nodeis the root

node and the tree is complete.

STEP8: Stop.
PROGRAM/SOURCECODE:

import heapq

class Node:
def __init__(self, freq, symbol, left=None, right=None):
[Link] = freq
[Link] = symbol
[Link] = left
[Link] = right
[Link] = ''

def __lt__(self, nxt):

return [Link] < [Link]

def printNodes(self, val=''):

newVal = val + str([Link])

if [Link]:
[Link](newVal)
if [Link]:
[Link](newVal)

if not [Link] and not [Link]:

print(f"{[Link]} -> {newVal}")

chars = ['a', 'b', 'c', 'd', 'e', 'f']

freq = [5, 9, 12, 13, 16, 45]

nodes = []

for x in range(len(chars)):
[Link](nodes, Node(freq[x], chars[x]))

while len(nodes) > 1:

left = [Link](nodes)
right = [Link](nodes)
 [Link] = '0'
[Link] = '1'

newNode = Node([Link] + [Link], [Link] + [Link], left, right)

[Link](nodes, newNode)

print("Huffman Codes are:")

nodes[0].printNodes()

OUTPUT:

f->0
c->100
d->101
a->1100
b->1101
e->111

RESULT:
Thus, the python program to implement Huffman Trees and Codes using Greedy technique has been
executed successfully
 [Link]
ITERATIVE IMPROVEMENT-SIMPLE X METHOD

Date:

AIM:

To implement a python program for Simplex Method using Iterative Improvement..

PROCEDURE:

STEP 1: Start
STEP 2: The initial table for simplex method is created with the linear constraints given.
STEP 3: The slack variables are added to bring the linear constrains into an equation.
STEP 4: With the equation formed the corresponding values are filed in the table.
STEP 5: The key value, Entering variable and leaving variable are chosen based on the
most negative value found in the difference and the least value found in the Ratio value.
STEP 6: The intersection of row and column chosen according to the previous method is
taken as the key along with its corresponding variables as entering and leaving.
STEP 7: The entire row of the key value is divided by a number such that the key becomes
1
STEP 8: The corresponding column of the key value is made to 0 by subtracting from the
key value row multiple by some constant if necessary and filled in a new table .
STEP 9: All the necessary calculation are done as needed and the new key values and
variables are found.
STEP 10: Step 5 to Step 9 is repeated until the difference from the values are non-negative
numbers.
STEP 11: The final solutions are found from the solution table when the table is done
recursive calculations.
STEP 12: Stop
PROGRAM/SOURCECODE:

import numpy as np
from fractions import Fraction

print("\n*** Simplex Algorithm ***\n")

A = [Link]([[1, 1, 0, 1],
[2, 1, 1, 0]])

b = [Link]([8, 10])

c = [Link]([1, 1, 0, 0])

B = [Link]([[3], [2]])

cb = [Link]([c[3]])
cb = [Link]((cb, c[2]))

xb = [Link]([b])

table = [Link]((B, cb))

table = [Link]((table, xb))

table = [Link]((table, A))

table = [Link](table, dtype='float')

MIN = 0

print("Table at itr = 0")

print("B\tCB\tXB\ty1\ty2\ty3\ty4")
for row in table:
for el in row:
print(Fraction(str(el)).limit_denominator(100), end="\t")
print()
print()

print("Simplex Working...")

reached = 0
itr = 1
unbounded = 0
alternate = 0

while reached == 0:
print("Iteration:", itr)
print("B\tCB\tXB\ty1\ty2\ty3\ty4")
for row in table:
for el in row:
print(Fraction(str(el)).limit_denominator(100), end="\t")
print()

rel_prof = []
non_basic_indices = [i for i in range(len(c)) if i not in table[:, 0]]
for i in non_basic_indices:
rel_prof.append(c[i] - [Link](table[:, 1] * table[:, 3 + i]))

print("relprofit:", end="")
for profit in rel_prof:
print(Fraction(str(profit)).limit_denominator(100), end=",")
print()

for i, profit in enumerate(rel_prof):

if profit == 0:
alternate = 1
print("Case of alternate found")
break # No need to check further if one alternate is found
print()

flag = 0
for profit in rel_prof:
if profit > 0:
flag = 1
break
if flag == 0:
print("All profits are <= 0, optimality reached")
reached = 1
break

k_index_in_rel_prof = rel_prof.index(max(rel_prof))
k = non_basic_indices[k_index_in_rel_prof] # Get the original index in c

min_val = 99999
r = -1

for i in range(len(table)):
if table[i][2] > 0 and table[i][3 + k] > 0:
val = table[i][2] / table[i][3 + k]
if val < min_val:
min_val = val
r = i # leaving variable

if r == -1:
unbounded = 1
print("Case of Unbounded")
break

print("pivot element index:", [r, 3 + k])

pivot = table[r][3 + k]
print("pivot element:", Fraction(pivot).limit_denominator(100))

table[r, 2:] = table[r, 2:] / pivot

for i in range(len(table)):
if i != r:
table[i, 2:] = table[i, 2:] - table[i][3 + k] * table[r, 2:]

table[r][0] = k
table[r][1] = c[k]
 print()
itr += 1

print("***************************************************")
if unbounded == 1:
print("UNBOUNDED LPP")
exit()

if alternate == 1:
print("ALTERNATE SOLUTION")

print("Optimal table:")
print("B\tCB\tXB\ty1\ty2\ty3\ty4")
for row in table:
for el in row:
print(Fraction(str(el)).limit_denominator(100), end="\t")
print()

print("value of Z at optimality:", end="")

basis = []
summation = 0
for i in range(len(table)):
summation += c[int(table[i][0])] * table[i][2]
temp = "x" + str(int(table[i][0]) + 1)
[Link](temp)

if MIN == 1:
print(-Fraction(str(summation)).limit_denominator(100))
else:
print(Fraction(str(summation)).limit_denominator(100))

print("Final Basis: ", basis)

print("Simplex Finished...")

Output:
Tableatitr=0
B C X Y Y Y Y
B B 1 2 3 4
3 0 8 1 1 0 1
2 0 1 2 1 1 0
0
 SimplexWorki
ng….
Iteration:1
B CB XB Y1 Y2 Y3 Y4
3 0 8 1 1 0 1
2 0 10 2 1 1 0
relprofit:1,1,0,0,

pivotelementindex:[
13] pivot element: 2

Iteration:2
B CB XB Y1 Y2 Y3 Y4
3 0 3 0 1/2 -1/2 1
0 1 5 1 1/2 1/2 0
Relprofit:0,1/2,-1/2,0,

pivotelementindex:[
0,4] pivot element

iteration:3
B CB XB Y1 Y2 Y3 Y4
1 1 6 0 1 -1 2
0 1 2 1 0 1 -1
rel profit: 0, 0, 0,-
1,
CaseofAlternatefo
und

Allprofitare<=0,optimalityreached
*********************************************************************
ALTERNATE SOLUTION
optimaltable:
B C X Y Y Y Y
B B 1 2 3 4
1 1 6 0 1 - 2
1
0 1 2 1 0 1 -
1

ValueofZatoptimalit
y:8 Final
basis:['x2','x1]
Simple finished…

RESULT:
Thus,the python program to implement Simple x Method using Iterative Improvement
has been executed successfully.
 [Link](a) BACKTRACKINGN
Date: -QUEEN PROBLEM

AIM:

To implement N-Queen Problem usimg Backtracking.

PROCEDURE:

STEP1:Start In the leftmost column

STEP2:If all queens are placed return

true
STEP3:Try all rows in the current column.

Do following for every tried row.

a)If the queen can be placed safely in this row then

mark this [row, column] as part of thesolution and
recursively check if placing queen here leads to a
solution.
b) If placing the queen in [row, column] leads toa
solution then return true.
c) If placing queen doesn't lead to a solution then unmark
this [row, column] (Backtrack) and go tostep (a) to try
other rows.
STEP4: If all rows have been tried and nothing worked,return false to
trigger backtracking.
 PROGRAM/SOURCECODE:

def print_solution(board):
for row in board:
print("".join(map(str, row)))
print()

def is_safe(board, row, col, n):

for i in range(col):
if board[row][i] == 1:
return False

for i, j in zip(range(row, -1, -1), range(col, -1, -1)):

if board[i][j] == 1:
return False

for i, j in zip(range(row, n, 1), range(col, -1, -1)):

if board[i][j] == 1:
return False

return True

def solve_n_queens_util(board, col, n):

if col == n:
print_solution(board)
return True

res = False
for i in range(n):
if is_safe(board, i, col, n):
board[i][col] = 1
res = solve_n_queens_util(board, col + 1, n) or res
board[i][col] = 0 # Backtrack
return res

def solve_n_queens(n):
board = [[0] * n for _ in range(n)]

if not solve_n_queens_util(board, 0, n):

print("Solution does not exist")
else:
print("Solutions found!")

solve_n_queens(4)
OUTPUT:
0010
1000
0001
0100

0100
0001
1000
0010

Solutionsfound!

RESULT:
Thus, the python program to implement N-Queen Problem using Backtracking has been executed
successfully.
 [Link](b) BACKTRACKING
Date: SUBSET SUM PROBLEM

AIM:

To implement Subset Sum Problem using backtracking.

PROCEDURE:

STEP 1 : Start with an empty set

STEP 2 : Add the next element from the list to the set

STEP 3 : If the subset is having sum M, then stop with that subset as solution.

STEP 4 : If the subset is not feasible or if we have reached the end of the set, then backtrack through the

subset until we find the most suitable value.

STEP 5 : If the subset is feasible (sum of seubset < M) then go to step 2.

STEP 6 : If we have visited all the elements without finding a suitable subset and if no backtracking is

possible then stop without solution.

PROGRAM/SOURCECODE:

def is_subset_sum(nums, n, target, current_sum, selected):

if current_sum == target:
print("Subset with the target sum found:", selected)
return True

if n == 0 or current_sum > target:

return False

[Link](nums[n - 1])
if is_subset_sum(nums, n - 1, target, current_sum + nums[n - 1], selected):
return True

[Link]()
return is_subset_sum(nums, n - 1, target, current_sum, selected)

def subset_sum(nums, target):

n = len(nums)
selected = []
if not is_subset_sum(nums, n, target, 0, selected):
print("No subset found with the target sum")

nums = [3, 34, 4, 12, 5, 2]

target_sum = 9
subset_sum(nums, target_sum)

OUTPUT:

Subsetwiththe targetsumfound:[2,4,3]

RESULT:

Thus, the python program to implement Subset Sum Problem using Backtracking has been executed
successfully
 [Link](a) BRANCHAND BOUND
Date: ASSIGNMENT PROBLEM

AIM:

To implement Assignment Problem using Branchand Bound technique.

PROCEDURE:

STEP1: Start

STEP2: Get the input data.

STEP3: Create them ip solver with the SCIP backend.

STEP4: Constraints:

a) Each worker is assigned to atmost 1 task.

b) Each task is assigned to exactly one worker.

STEP5: Solve the problem.

STEP6: Print the solution.

PROGRAM/SOURCECODE:

from ortools.linear_solver import pywraplp

def main():
costs = [
[90, 80, 75, 70],
[35, 85, 55, 65],
[125, 95, 90, 95],
[45, 110, 95, 115],
[50, 100, 90, 100],
]
num_workers = len(costs)
num_tasks = len(costs[0])

solver = [Link]('SCIP')

if not solver:
return

x = {}
for i in range(num_workers):
for j in range(num_tasks):
x[i, j] = [Link](0, 1, '')

for i in range(num_workers):
[Link]([Link]([x[i, j] for j in range(num_tasks)]) <= 1)

for j in range(num_tasks):
[Link]([Link]([x[i, j] for i in range(num_workers)]) == 1)

objective_terms = []
for i in range(num_workers):
for j in range(num_tasks):
objective_terms.append(costs[i][j] * x[i, j])
[Link]([Link](objective_terms))

status = [Link]()
 if status == [Link] or status == [Link]:
print(f'Total cost = {[Link]().Value()}\n')
for i in range(num_workers):
for j in range(num_tasks):
if x[i, j].solution_value() > 0.5:
print(f'Worker {i} assigned to task {j}. Cost: {costs[i][j]}')
else:
print('No solution found.')

if __name__ == '__main__':
main()

OUTPUT:

Totalcost=265

Worker 0 assignedtotask 3 Cost= 70

Worker 1 assignedtotask 2 Cost= 55
Worker 2 assignedtotask 1 Cost= 95
Worker 3 assignedtotask 0 Cost= 45

RESULT:
Thus, the python program to implement Assignment Problem using Branch and Bound technique has
been executed successfully.
 [Link](b) BRANCH AND BOUND
Date: TRAVELLING SALESMAN PROBLEM

AIM:
To implement Travelling Salesman Problem using Branch and Bound technique

PROCEDURE:

STEP 1 : Initially, graph is represented by cost matrix C, where Cij = cost of edge, if there is a direct path
from city i to city j Cij = ∞, if there is no direct path from city i to city j.
STEP 2 : Convert cost matrix to reduced matrix by subtracting minimum values from appropriate rows
and columns, such that each row and column contains at least one zero entry.
STEP 3 : Find cost of reduced matrix. Cost is given by summation of subtracted amount from the cost
matrix to convert it in to reduce matrix.
STEP 4 : Prepare state space tree for the reduce matrix
STEP 5 : Find least cost valued node A (i.e. E-node), by computing reduced cost node matrix with every
remaining node.
STEP 6 : If edge is to be included, then do following :
(a) Set all values in row i and all values in column j of A to ∞
(b) Set A[j, 1] = ∞
(c) Reduce A again, except rows and columns having all ∞ entries.
STEP 7 : Compute the cost of newly created reduced matrix as, Cost = L + Cost(i, j) + r Where, L is cost
of original reduced cost matrix and r is A[i, j].
STEP 8 : If all nodes are not visited then go to step 4.
PROGRAM/SOURCECODE:

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] # return to starting point

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:
Minimum cost : 80
Path Taken : 0 1 3 2 0

RESULT:
Thus, the python program to implement Subset Sum Problem using Backtracking has been executed
successfully.