1

INDEX

PAGE FACULTY
S.No. DATE NAME OF THE EXPERIMENT
No. SIGN

Implement recursive and non-recursive algorithms

1
in Python

2 Divide And Conquer - Strassen’s Matrix Multiplication

3 Decrease and Conquer - Topological Sorting

4 Transform And Conquer - Heap Sort

5.a Coin Change Problem

5.b Dynamic Programming – Warshall Algorithm

5.c Dynamic Programming – Floyd ’S Algorithm

5.d Implementation of Knapsack Problem

6.a Implementation of Dijkstra’s Algorithm

6.b Huffman Tree and Codes

7 Iterative improvement - Simplex Method

8.a Backtracking-N Queens Problem

8.b Backtracking - Subset Sum Problem

9.a Branch and Bound - Assignment Problem

9.b Branch and Bound-Traveling Salesman Problem

2
 Ex.No:1 Implement recursive and non-recursive
Date:
algorithms in Python
AIM:
Implement recursive and non-recursive algorithms and study the order of growth from log2n to n!

ALGORITHM:
Step 1: Start
Step 2: get the input values
Step 3: Perform the recursive and non recursive algorithms and study the order of growth.
Step 4: End

PROGRAM:
a).Recursive
def fact(n):
if n == 0:
return 0
elif n == 1:
return 1
else
:
return n*fact(n-1)
n=7

result = fact(n)
print(“factorial of 7 is =”,result)
b).Non-recursive
a=3
b=5
c = a+b
print(“The sum of a and b is :”,c)

3
OUTPUT:
a).factorial of 7 is = 5040
b).The sum of a and b is :8

RESULT:
Thus the program to solve recursive and non-recursive algorithms and study the order of growth was
executed and output was observed successfully.

4
 Ex.No:2
Date:
Divide And Conquer -Strassen’s
Matrix Multiplication
AIM:
To implement Strassen’s Matrix Multiplication by using Divide and Conquero write a
Python program for various sorting algorithms.

ALGORITHM:

Step1: Initializing the matrix A and B.

Step2: .If the Length of the Matrix is lesser than or Equal to 2 then we use Brute Force
Method.
Step3; If the Length of the Matrix is greater than 2 then we need to divide the Matrix into the
Length 2 and Perform the Multiplication.

Step 4: The final Results will be Combined to Produce Final Multiplied Matrix.

PROGRAM:

import numpy as np

def brute (A,B):

n,m,p= A.shape[0], A.shape[1], B.shape[1]

C=np.array([[0]*p for i in range(n)])
for i in range(n):

for j in range(p):

for k in range(m):

C[i][j]+=A[i][k]*B[k][j]

return C

def split(matrix):

n=len(matrix)

return matrix[:n//2, :n//2],matrix[:n//2, n//2:],matrix[n//2:, :n//2],matrix[n//2:, n//2:]

def strassen(A,B):

if len(A)<=2:

5
 return brute(A,B)

a,b,c,d = split(A)

e,f,g,h = split(B)

ae=strassen(a,e)

bg=strassen(b,g)

af=strassen(a,f)

bh=strassen(b,h)

ce=strassen(c,e)

dg=strassen(d,g)

cf=strassen(c,f)

dh=strassen(d,h)

c11 = ae + bg

c12 = af + bh

c21 = ce + dg

c22 = cf + dh

C = np.vstack((np.hstack((c11,c12)), np.hstack((c21,c22))))

return C
A = np.array([[3,5,1,3],[1,2,3,4],[4,5,6,8],[7,8,9,3]])

print("The A Matrix is:",A)

B = np.array([[4,1,2,3],[1,2,1,6],[2,4,6,2],[6,2,5,4]])

print("The B Matrix is:",B)

C=A.dot(B)
print("The value of C is:",C)

OUTPUT:
The A Matrix is: [[3 5 1 3]

[1 2 3 4]
[4 5 6 8]
[7 8 9 3]]

6
The B Matrix is: [[4 1 2 3]
[1 2 1 6]
[2 4 6 2]
[6 2 5 4]]
The value of C is: [[37 23 32 53]
[36 25 42 37]
[81 54 89 86]
[72 65 91 99]]

RESULT:
This the program for Strassen’s Matrix Multiplication was executed and output was verified
successfully.

7
 Ex.No:3 Decrease and Conquer - Topological
Date:
Sorting

AIM:

To write a Python program for Decrease and Conquer - Topological Sorting

ALGORITHM:

Step 1:Start

Step 2:Create stack to store nodes.

Step 3:Initialise visited array of size n to keep the record of visited nodes.

Step 4:Run a loop from 0 to n

Step 5:If the node is not marked True in visited array.

Step 6:Call the recursive function for topological sorting.

Step 7:Mark the current node as True in the visited array.

Step 8:Run a loop on all the nodes which has directed edges to current node.
Step 9:If the node is not marked True in visited array.

Step 10:Again call topological sort.

Step 11:Print all elements in the

stack. Step 12:End.

PROGRAM:

class Graph:
def init (self, vertices):
self.graph = defaultdict(list)
self.V = vertices

def addEdge(self, u, v):

self.graph[u].append(v)

def topologicalSortUtil(self, v, visited, stack):

8
 visited[v] = True
for i in self.graph[v]:
if visited[i] == False:
self.topologicalSortUtil(i, visited, stack)
stack.append(v)

def topologicalSort(self):
visited = [False]*self.V
stack = []

for i in range(self.V):
if visited[i] == False:
self.topologicalSortUtil(i, visited, stack)

print(stack[::-1]) # return list in reverse order

g = Graph(6)
g.addEdge(5, 2)
g.addEdge(5, 0)
g.addEdge(4, 0)
g.addEdge(4, 1)
g.addEdge(2, 3)
g.addEdge(3, 1)

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

g.topologicalSort()

OUTPUT:
Following is a Topological Sort of the given graph
543210

RESULT:
The Python program for Decrease and Conquer - Topological Sorting was successfully
executed.

9
 Ex.No:4
Date:
Transform And Conquer - Heap Sort

AIM:

To implement Heap Sort by using Transform and Conquer Technique.

ALGORITHM:

Step1: Initializing the array named ‘arr’.

Step2: .Creating a tree from the given array and performing Heapify to produce a max heap.

Step3; Compare the nodes from the Leaf node to find maximum value among the nodes.

3.1: If the leaf node have greater value swap it with root node.

Step 4: The Heap will be Heapified and the sorted array will be printed.

PROGRAM:
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] 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):

10
 arr[i], arr[0] = arr[0], arr[i]

heapify(arr, i, 0)

if name == ' main ':

arr = [12, 11, 13, 5, 6, 7]

heapSort(arr)
N = len(arr)

print("Sorted array is")

for i in range(N):
print(arr[I])

OUTPUT:

Sorted array is

5
6

11

12

13

RESULT:

This the program for Heap Sort was executed and output was verified successfully.

11
 Ex.No:5.a
Date: Coin Change Problem
AIM:
To find the solution for coin change problem

ALGORITHM:

Step 1: Start the program.

Step 2: if amount = 0, then return 0

STEP 3:if minimum of coins array > amount, then return –1
Step 4:define one array called dp, of size amount + 1, and fill this with -1
Step 5:for i in range coins array
Step 6:if i > length of dp – 1, then skip the next part, go for the next iteration
Step 7:dp[i] := 1
Step 8:for j in range i + 1 to amount
Step 9:if dp[j – 1] = -1, then skip the next part, go for the next iteration
Step 10:otherwise if dp[j] = -1, then dp[j] := dp[j - i] + 1
Step 11:otherwise dp[j] := minimum of dp[j] and dp[j – i]
Step 12:return dp[amount]

Step13: Stop the Program.

PROGRAM:

class Solution(object):
def coinChange(self, coins, amount):
if amount == 0 :
return 0
if min(coins) > amount:
return -1
dp = [-1 for i in range(0, amount + 1)
for i in coins:
if i > len(dp) - 1:
continue
dp[i] = 1
for j in range(i + 1, amount + 1):
if dp[j - i] == -1:
continue

12
 elif dp[j] == -1:
dp[j] = dp[j - i] + 1
else:
dp[j] = min(dp[j], dp[j - i] + 1)
#print(dp)
return dp[amount]
ob1 = Solution()
print( “NUMBER OF COINS REQUIRED IS:”ob1.coinChange([1,2,5], 11))

OUTPUT:

NUMBER OF COINS REQUIRED IS: 3

RESULT:
Thus, we can find the number of coins required to satisfy the given sum.

13
 Ex.No:5.b
Date:
Dynamic Programming – Warshall
Algorithm
AIM:
To implement Warshall Algorithm by using Dynamic Programming

ALGORITHM:

Step1: Initializing the graph named ‘G’.

Step2: .Now we use the formula distance[i][j] = (distance[i][j]or distance[i][k] and

distance[k][j]) to Identify the Shortest Path

Step3; This formula will be iterated to all values of the Matrix

Step 4: Then print the matrix

PROGRAM:

nV = 4

def 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] = (distance[i][j]or distance[i][k] and distance[k][j])

print_solution(distance)

def print_solution(distance):
for i in range(nV):
for j in range(nV):
print(distance[i][j], end=" ")
print(" ")

print("The Matrix is :")

14
G = [[0,1,0,0],

[0,0,1,0],

[0,0,0,1],

[0,0,0,0]]

warshall(G)

OUTPUT:

The Matrix is :

0 1 1 1

0 0 1 1

0 0 0 1
0 0 0 0

RESULT:

This the program for Warshall Algorithm was executed and output was verified successfully.

15
 Ex.No:5.c
Date:
Dynamic Programming – Floyd ’S
Algorithm
AIM:
To implement Floyd’s Algorithm by using Dynamic Programming.

ALGORITHM:
Step1: Initializing the graph named ‘G’.

Step2: .Now we use the formula distance[i][j] = min(distance[i][j], distance[i][k] +

distance[k][j]) to Identify the Shortest Path

Step3; This formula will be iterated to all values of the Matrix

Step 4: If the Final graph G is not infinity the we print the matrix

PROGRAM:
nV = 4

INF = 999

def floyd(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(" ")

16
print("The Matrix is

:") G = [[0, 3, INF, 5],

[2, 0, INF, 4],

[INF, 1, 0, INF],

[INF, INF, 2, 0]]

floyd(G)

OUTPUT:

The Matrix is :

0 3 7 5

2 0 6 4

3 1 0 5

5 3 2 0

RESULT:

This the program for Floyd’s Algorithm was executed and output was verified successfully.

17
 Ex.No:5.d Implementation of Knapsack Problem
Date:

AIM:
Implement knapsack problem using dynamic programming

ALGORITHM:
Step 1: Start
Step 2: Get the value and weight of the items,and capacity
Step 3: Check whether the capacity is equal to zero or not if ti is equal to zero then return zero
Step 4: Check whether the last item is greater than the capacity weight then don’t include that item for
getting optimal solution

Step 5: The maximum value obtained from ‘N’ items is the max of the following two values.

Maximum value obtained by N-1 items and W weight (excluding nth item)

Value of nth item plus maximum value obtained by N-1 items and W minus the weight
of the Nth item (including Nth item)

If the weight of the ‘Nth’ item is greater than ‘W’, then the Nth item cannot be included
Step 6: return the function
Step 7: End

PROGRAM:
def knapSack(W, wt, val, n):
if n == 0 or W == 0 :
return 0
if (wt[n-1] >
W):
return knapSack(W, wt, val, n-1)
else:
return max(val[n-1] + knapSack(W-wt[n-1], wt, val, n-
1), knapSack(W, wt, val, n-1))
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print (knapSack(W, wt, val, n))

18
OUTPUT:
220

RESULT:
Thus the program to solve Knapsack problem using Dynamic Programming was executed and output
was observed successfully.

19
 Ex.No:6.a Implementation of Dijkstra’s
Date:
Algorithm
AIM:

To implement Dijkstra's algorithm using greedy technique.

ALGORITHM:

Step1: initialise the starting node with zero costs and the rest of the node as infinity cost.
Step2: maintain an array or list to keep track of visited nodes.
Step3; update the node cost with minimum cost. It can be done by comparing the current cost
with the path cost.

Step 4: continue step 3 until all the node is visited.

PROGRAM:

from queue import PriorityQueue

class Graph:

def init (self, num_of_vertices):

self.v = num_of_vertices

self.edges = [[-1 for I in range(num_of_vertices)] for j in range(num_of_vertices)]

self.visited = []

def add_edge(self, u, v, weight):

self.edges[u][v] = weight

self.edges[v][u] = weight
def dijkstra(graph, start_vertex):

D = {v:float(‘inf’) for v in range(graph.v)}

D[start_vertex] = 0

Pq = PriorityQueue()

Pq.put((0, start_vertex))
While not pq.empty():

(dist, current_vertex) = pq.get()

Graph.visited.append(current_vertex)
For neighbor in range(graph.v):

20
 If graph.edges[current_vertex][neighbor] != -1:

Distance = graph.edges[current_vertex][neighbor]

If neighbor not in graph.visited:

Old_cost = D[neighbor]

New_cost = D[current_vertex] + distance

If new_cost < old_cost:

Pq.put((new_cost, neighbor))

D[neighbor] = new_cost

Return D
G = Graph(9)
g.add_edge(0, 1, 4)
g.add_edge(0, 6, 7)

g.add_edge(1, 6, 11)

g.add_edge(1, 7, 20)

g.add_edge(1, 2, 9)

g.add_edge(2, 3, 6)

g.add_edge(2, 4, 2)

g.add_edge(3, 4, 10)

g.add_edge(3,5,5)

g.add_edge(4, 5, 15)
g.add_edge(4, 7, 1)

g.add_edge(4, 8, 5)

g.add_edge(5, 8, 12)

g.add_edge(6, 7, 1)

g.add_edge(7, 8, 3)

D = dijkstra(g, 0)

Print(D)
For vertex in range(len(D)):

Print(“Distance from vertex 0 to vertex”, vertex, "is", D[vertex]

21
OUTPUT:
Distance from vertex 0 to vertex 1 is 4

Distance from vertex 0 to vertex 2 is 11

Distance from vertex 0 to vertex 3 is 17

Distance from vertex 0 to vertex 4 is 9

Distance from vertex 0 to vertex 5 is 22

Distance from vertex 0 to vertex 6 is 7

Distance from vertex 0 to vertex 7 is 8

Distance from vertex 0 to vertex 8 is 11

RESULT:

This the program for Dijkstra’s algorithm was executed and output was verified successfully.

22
 Ex.No:6.b Huffman Tree and Codes
Date:

AIM:
To write a python program on hoffman’s code.

ALGORITHM:

Step 1 : Create a priority queue Q consisting of each unique character.

Step 2 : Sort that is ascending of their frequencies.
For all the unique characters:

Step 3 : Create a newnode.

Step 4 : Extract minimum value from Q and assign it to leftchild of newnode.

Step 5 : Extract minimum value from Q and assign it to rightchild of newnode.

Step 6 : Calculate the sum of these two minimum values and assign it to the value of
newnode.
Step 7 : Insert this newnode into the tree.
Step 8 : Return rootnode

PROGRAM:

# Huffman Coding in python

String = ‘BCAADDDCCACACAC’

# Creating tree nodes

Class NodeTree(object):

def init (self, left=None, right=Nonobj Self.left =

left Self.right = right

def children(self):

Return (self.left, self.right)

def nodes(self):
Return (self.left, self.right)

23
 def str (self):

Return ‘%s_%s’ % (self.left, self.right)

def huffman_code_tree(node, left=True, binString=’’):

If type(node) is str:

return {node: binString}

(l, r) = node.children()
D = dict()

d.update(huffman_code_tree(l, True, binString + ‘0’))

d.update(huffman_code_tree(r, False, binString +

‘1’)) return d

# Calculating frequency

Freq = {}

for c in string:

if c in freq:

Freq[c] += 1
else:
Freq[c] = 1
Freq = sorted(freq.items(), key=lambda x: x[1],

reverse=True) Nodes = freq

While len(nodes) > 1:

(key1, c1) = nodes[-
1]

(key2, c2) = nodes[-2]

Nodes = nodes[:-2]

Node = NodeTree(key1, key2)

Nodes.append((node, c1 +
c2))

Nodes = sorted(nodes, key=lambda x: x[1],

24
reverse=True) huffmanCode =
huffman_code_tree(nodes[0][0])

25
print(‘ Char | Huffman code

‘) print(‘ ‘)
for (char, frequency) in freq:

print(‘ %-4r |%12s’ % (char, huffmanCode[char]))

OUTPUT:

The factorial of 5 is 120

RESULT:
The python program to find factorial of a number using recursive function was successfully
executed.

26
 Ex.No:7 Iterative improvement - Simplex Method
Date:

AIM:
To write a Python program to Iterative improvement using simplex method.

ALGORITHM:

Step 1. Start the program.

Step 2: Standard Form.

Step 3: Determine Slack

Variables. Step 4: Setting up the

Tableau.

Step 5: Check Optimality.

Step 6: Identify Pivot

Variable.

Step 7: Create the New

Tableau. Step 8: Check

Optimality.

Step 9: Identify New Pivot Variable.

Step 10: Stop the program.

PROGRAM:

import numpy as np
from fractions import Fraction # so that numbers are not displayed in decimal.

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

# inputs

# A will contain the coefficients of the

constraints A = np.array([[1, 1, 0, 1], [2, 1, 1, 0]])
# b will contain the amount of resources
b = np.array([8, 10])
# c will contain coefficients of objective function
Z c = np.array([1, 1, 0, 0])

27
# B will contain the basic variables that make identity
matrix cb = np.array(c[3])
B = np.array([[3], [2]])
# cb contains their corresponding coefficients in Z
cb = np.vstack((cb, c[2]))

28
xb = np.transpose([b])
# combine matrices B and cb
table = np.hstack((B, cb))
table = np.hstack((table, xb))
# combine matrices B, cb and xb
# finally combine matrix A to form the complete simplex table
table = np.hstack((table, A))
# change the type of table to float
table = np.array(table, dtype ='float')
# inputs end

# if min problem, make this var 1

MIN = 0

print("Table at itr = 0")

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

print("Simplex Working. ..")

# when optimality reached it will be made 1

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

while reached == 0:

print("Iteration: ", end =' ')

print(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()

# calculate Relative profits-> cj - zj for non-basics

i=0
rel_prof = []
while i<len(A[0]):
rel_prof.append(c[i] - np.sum(table[:, 1]*table[:, 3 + i]))
i=i+1
29
print("rel profit: ", end =" ")
for profit in rel_prof:
print(Fraction(str(profit)).limit_denominator(100), end =", ")
print()
i=0

b_var = table[:, 0]
# checking for alternate solution
while i<len(A[0]):
j=0
present = 0
while j<len(b_var):
if int(b_var[j]) == i:
present = 1
break;
j+= 1
if present == 0:
if rel_prof[i] == 0:
alternate = 1
print("Case of Alternate
found") # print(i, end =" ")
i+= 1
print()
flag =
0

for profit in rel_prof:

if profit>0:
flag = 1
break
# if all relative profits <= 0
if flag == 0:
print("All profits are <= 0, optimality reached")
reached = 1
break

# kth var will enter the basis

k = rel_prof.index(max(rel_prof))
min = 99999
i = 0;
r = -1
# min ratio test (only positive values)
while i<len(table):
if (table[:, 2][i]>0 and table[:, 3 + k][i]>0):
val = table[:, 2][i]/table[:, 3 + k][i]
if val<min:
30
min = val

31
 r=i # leaving variable
i+= 1

# if no min ratio test was performed

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

print("pivot element index:", end =' ')

print(np.array([r, 3 + k]))

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

# perform row operations

# divide the pivot row with the pivot element
table[r, 2:len(table[0])] = table[
r, 2:len(table[0])] / pivot

# do row operation on other rows

i=0
while i<len(table):
if i != r:
table[i, 2:len(table[0])] = table[i,
2:len(table[0])] - table[i][3 + k] *
table[r, 2:len(table[0])]
i += 1

# assign the new basic variable

table[r][0] = k
table[r][1] = c[k]

print()
print()
itr+= 1

print()

print("***************************************************************")
if unbounded == 1:
print("UNBOUNDED LPP")
exit()
32
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()
print("value of Z at optimality: ", end =" ")

basis = []
i=0
sum = 0
while i<len(table):
sum += c[int(table[i][0])]*table[i][2]
temp = "x"+str(int(table[i][0])+1)
basis.append(temp)
i+= 1
# if MIN problem make z negative
if MIN == 1:
print(-Fraction(str(sum)).limit_denominator(100))
else:
print(Fraction(str(sum)).limit_denominator(100))
print("Final Basis: ", end =" ")
print(basis)

print("Simplex Finished...")
print()

33
OUTPUT:

34
RESULT:
Thus the program to solve the simplex method using iterative improvement was executed
and output was observed successfully.

35
 Ex.No:8.a Backtracking-N Queens Problem
Date:

AIM:
To implement N queens problem using backtracking algorithm technique.
ALGORITHM:
Step 1:Start
Step 2: place the queen row-wise , starting from the left most cell.
Step 3: if all queens are placed then return true and print the solution matrix.
Step 4: else try all columns in the current row.
Condition 1: check if the queen is placed safely in this column then mark current cell
(row,column) in the solution matrix as 1 and try to check the rest of the problem recursively by
placing the queen here leads to a solution or not.
Condition 2: if placing the queen ( row, column) can lead to the solution return true and print the
solution for each queen position.
Condition 3 : if placing the queen cannot lead to the solution then unmark this ( row, column) in
the solution matrix as 0, BACKTRACK and go back to condition 1 to try other rows.
Step 5: if all the rows have been tried and nothing worked, return false to trigger backtracking.
Step 6:End

PROGRAM:
def printSolution(board):
for i in range(N):
for j in range(N):
print(board[i][j], end = " ")
print()
def isSafe(board, row, col):
# Check this row on left side
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):

36
 range(col, -1, -1)):
if board[i][j] == 1:
return False
return True
def solveNQUtil(board, col):
if col >= N:
return True
for i in range(N):
if isSafe(board, i, col):
board[i][col] = 1
if solveNQUtil(board, col + 1) ==
True: return True
board[i][col] = 0
return False
def solveNQ(board):
if solveNQUtil(board, 0) == False:
print ("Solution does not
exist") return False
printSolution(board)
return True
z=int(input("Enter the board length : "))
board = [[0 for col in range(z)] for row in range(z)]
N=z
solveNQ(board)

37
OUTPUT:
Enter the board length :
510000
00010
01000
00001
00100
True

RESULT:
Thus the program to solve N queen problem using backtracking technique was executed and output
was observed successfully.

38
 Ex.No:8.b Backtracking - Subset Sum
Date:
Problem

AIM:

To write python program to perform sum of subset.

ALGORITHM:
Step 1 import combinations from
itertools, Step 2: initialize array as at
Step 3: assign target value as 80
Step 4: create a subset using packages
Step 5: if sum of subsettarget
Step 6:print(subset)

PROGRAM:

From tertogl import combinations

Def subsetsur(n. az x)
For I n range(u+1):

For subset in combnations(ar

If sum(subset)x

Print(list(subset))
ôK-[10, 20, 25, 50, 70, 90]

N=lep(art) = 80

Subsetsum(n. E, 3)

Minimum cost : 80

OUTPUT:
[10,70]

[10,20,50]

RESULT:
The python program to find the sum of subset was successfully executed.

39
 Ex.No:9.a Branch and Bound - Assignment
Date:
Problem
AIM:
To write a Python program for implementing Branch and Bound assignment problem.
ALGORITHM:

IMPORT – CP MODULE
IMPORT - ORTOOLS

STEP 1 :

/* findMinCost uses Least() and Add() to maintain thelist of live nodes

Least() finds a live node with least cost, deletesit from the list and returns
it

STEP 2:

Add(x) calculates cost of x and adds it to the listof live

nodes Implements list of live nodes as a min heap */
// Search Space Tree Nodenode
{

int job_number; int

worker_number;node
STEP 3
: parent;
int cost;
}

STEP 4 :

// Input: Cost Matrix of Job Assignment problem

// Output: Optimal cost and Assignment of Jobsalgorithm findMinCost (costMatrix
mat[][])

40
 {
// Initialize list of live nodes(min-Heap)
// with root of search tree i.e. a Dummy nodewhile (true)
{
STEP
5:
// Find a live node with least estimated costE = Least():
// The found node is deleted from the list
// of live nodes
if (E is a leaf node)
{
STEP 6:
printSolution();return;
}

for each child x of E

{
Add(x); // Add x to list of live nodes;
x->parent = E; // Pointer for path to root

PROGRAM:
from ortools.sat.python import cp_model

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

# Model
model = cp_model.CpModel()

41
 # Variables
x = []
for i in range(num_workers):
t = []
for j in range(num_tasks):
t.append(model.NewBoolVar(f'x[{i},{j}]'))
x.append(t)

# Constraints
# Each worker is assigned to at most one task.
for i in range(num_workers):
model.AddAtMostOne(x[i][j] for j in range(num_tasks))

# Each task is assigned to exactly one worker.

for j in range(num_tasks):
model.AddExactlyOne(x[i][j] for i in range(num_workers))

# Objective
objective_terms = []
for i in range(num_workers):
for j in range(num_tasks):
objective_terms.append(costs[i][j] * x[i][j])
model.Minimize(sum(objective_terms))

# Solve
solver = cp_model.CpSolver()
status = solver.Solve(model)

# Print solution.
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
print(f'Total cost = {solver.ObjectiveValue()}')
print()
for i in range(num_workers):
for j in range(num_tasks):
if solver.BooleanValue(x[i][j]):
print(
f'Worker {i} assigned to task {j} Cost = {costs[i][j]}')
else:
print('No solution found.')

if name == ' main ':

main()

OUTPUT:

RESULT:
Thus the program to solve the branch and bound – assignment problem was executed and output was observed
successfully.

42
 Ex.No:9.b Branch and Bound-Traveling Salesman
Date:
Problem
AIM:
To write a Python program to solve branch and bound Travelling Salesman Problem.
ALGORITHM:
Step-1 : start

Step-2 : Input data on the form of

matrix Step-3 : Import math library.

Step-4 : By passing matrix in travelling sales person function which we created.

Step-5 : In that function we will give some other small functions for getting output
easy. Step-6 : And passing through loops we will get some output.

Step-7 : End.
PROGRAM:

Import math
Maxsize = float(‘inf’)
Def copyToFinal(curr_path):
Final_path[:N + 1] =
curr_path[:] Final_path[N] =
curr_path[0]
def firstMin(adj, i):

Min = maxsize

For k in range(N):

If adj[i][k] < min and I != k:

Min = adj[i][k]
Return min
def secondMin(adj, i):

First, second = maxsize,

maxsize For j in range(N):

43
If I == j:

44
 Continue

If adj[i][j] <= first:

Second = first
First = adj[i][j]
Elif(adj[i][j] <= second
and Adj[i][j] != first):
Second = adj[i][j]
return second
Def TSPRec(adj, curr_bound, curr_weight,
Level, curr_path, visited):
Global final_res
If level == N:
If adj[curr_path[level – 1]][curr_path[0]] != 0:
Curr_res = curr_weight + adj[curr_path[level – 1]]\

[curr_path[0]]

If curr_res < final_res:

copyToFinal(curr_path)
final_res = curr_res
return

for I in range(N):

if (adj[curr_path[level-1]][i] != 0 and
visited[i] == False):
temp = curr_bound
curr_weight += adj[curr_path[level – 1]][i]
if level == 1:
curr_bound -= ((firstMin(adj, curr_path[level – 1]) +
firstMin(adj, i)) / 2)

else:

45
 curr_bound -= ((secondMin(adj, curr_path[level – 1]) +
firstMin(adj, i)) / 2)
if curr_bound + curr_weight <
final_res: curr_path[level] = i

visited[i] = True
TSPRec(adj, curr_bound, curr_weight,
Level + 1, curr_path, visited)
Curr_weight -= adj[curr_path[level – 1]]
[i] Curr_bound = temp
Visited = [False] *
len(visited) For j in
range(level):
If curr_path[j] != -1:
Visited[curr_path[j]] = True

def TSP(adj):

Curr_bound = 0
Curr_path = [-1] * (N +
1) Visited = [False] * N

For I in range(N):

Curr_bound += (firstMin(adj, i) +
secondMin(adj, i))
curr_bound = math.ceil(curr_bound /
2) visited[0] = True

curr_path[0] = 0
TSPRec(adj, curr_bound, 0, 1, curr_path, visited)

Adj = [[0, 10, 15, 20],

[10, 0, 35, 25],

[15, 35, 0, 30],

46
 [20, 25, 30, 0]]

N=4

Final_path = [None] * (N +
1) Visited = [False] * N
Final_res = maxsize
TSP(adj)
Print(“Minimum cost :”, final_res)
Print(“Path Taken : “, end = ‘ ‘)
For I in range(N + 1):
Print(final_path[i], end = ‘ ‘)

OUTPUT:

RESULT:

The python program for implementing Branch and Bound travelling sales man problem was
executed and output was observed.

47