INDEX

EXP DATE NAME OF THE EXPERIMENT PAGE SIGNATURE

NO. NO.

Implement recursive and non-recursive algorithms

1 and studythe order of growth from log2n to n!..

2 Divide and Conquer - Strassen’s Matrix Multiplication

Decrease and Conquer - Topological Sorting

3

4 Transform and Conquer - Heap Sort

5 Dynamic programming - Coin change Problem,

Warshall’s andFloyd‘s algorithms, Knapsack Problem

6 Greedy Technique – Dijkstra’s algorithm, Huffman Trees

and codes

7 Iterative improvement - Simplex Method

8 Backtracking – N-Queen problem, Subset Sum Problem

9 Branch and Bound - Assignment problem, Traveling

SalesmanProblem

1
 Ex.No:1(a) RECURSIVE ALGORITHM -
FIBONACCI SERIES
Date:

AIM:
To write the algorithm and python program to display the Fibonacci series usingrecursive
algorithm

ALGORITHM:

Step-1: Start the program

Step-2: Get the number of series as n from user.

Step-3: Check if n is less than or equal to 1, if yes, then return the value of n to the main.

Step-4: Otherwise , call the function “recursive_fibonacci(n-1)+recursive_fibonacci(n-2)”

recursively until the base condition becomes true.

Step-5: Stop the program .

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 validif

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

2
Output

Fibonacci series:
0
1
1
2
3
5
8
13
21
34

RESULT: Thus the Fibonacci series was displayed successfully using recursion algorithm and
output was verified.

3
 Ex.No:1 b
BINARY SEARCH USING ITERATION METHOD
Date:

AIM:

To write an algorithm and python program to implement the binary search methodusing
non-recursive(Iteration) method.

ALGORITHM:

Step-1: Start the program.

Step-2: Read the value of array and search element.

Step-3: Assign the value of lo=0 and hi=len(v)-1.

Step-4: Assign the while loop if (hi-lo) >1.

Step-5: Assume the value of mid and check if v[mid] < search element, then assign lo=mid=1.

Step-6: Otherwise assign hi = mid : and the loop runs until the condition fails.

Step-7: Return the value of mid to main program after the execution of while loop.

Step-8: Stop the program

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,

4
 To_Find)To_Find = 10
binarySearch(v, To_Find)

OUTPUT:

Found At Index 4Not

Found

RESULT:
Thus the implementation of binary search using iterative method was executed
successfully and output was verified.

5
 Ex.No: 2 FINDING MINIMUM AND MAXIMUM ELEMENT IN ARRAY USING
Date: DIVIDEAND CONQUER

AIM:

To write the algorithm and python program for finding the maximum and minimum
element in array using Divide and Conquer method.

ALGORITHM:

Step-1: Start the program.

Step-2: Divide and conquer approach for Max. Min problem works in three stages.

Step-2.1: If a1 is the only element in the array, a1 is the maximum and minimum.

Step-2.2: If the array contains only two elements a1 and a2, then the single comparison between
two elements can decide the minimum and maximum of them.

Step-2.3: If there are more than two elements, the algorithm divides the array from the middle and
creates two subproblems.

Step-3: Both subproblems are treated as an independent problem and the same recursiveprocess is
applied to them.

Step-4: This division continues until subproblem size becomes one or two.

Step-5: After solving two subproblems, their minimum and maximum numbers are compared to
build the solution of the large problem.

Step-6: This process continues in a bottom-up fashion to build the solution of a parent problem.

Step-7: Stop the program.

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];

6
 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);

OUTPUT

The minimum number in the array is: 1 The

maximum number in the array is: 90

RESULT:
Thus the implementation of divide and conquer method is executed successfully andoutput
was verified.

7
 Ex.No:3
Date: DECREASE AND CONQUER - TOPOLOGICAL SORTING

AIM:
To write the algorithm and python program to implement the Topological sorting using
Decrease and Conquer method.

ALGORITHM:

Step-1: Start the program.

Step-2: Create a stack to store the nodes.

Step-3: Initialize visited array of size N to keep the record of visited nodes.

Step-4: Run a loop from 0 till N

Step-4.1: If the node is not marked True in visited array

Step-4.2: Call the recursive function for topological sort and perform the following steps.

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

Step-4.4: Run a loop on all the nodes which has a directed edge to the current node

Step-4.5: If the node is not marked True in the visited array:

Step-4.6: Recursively call the topological sort function on the node

Step-4.7: Push the current node in the stack.

Step-5: Print all the elements in the stack.

Step-6: Stop the program.

CODING:

from collections import defaultdictclass

Graph:

def __init__(self,vertices):

self.graph = defaultdict(list) #dictionary containing adjacency Listself.V =

vertices #No. of 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.insert(0,v)

def topologicalSort(self): visited =

[False]*self.Vstack =[]

for i in range(self.V):

if visited[i] == False:

self.topologicalSortUtil(i,visited,stack)

print (stack)

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[5, 4,

2, 3, 1, 0]

RESULT:
Thus the implementation of topological sorting using decrease and conquermethod was
executed successfully and output was verified.

9
 Ex.No: 4
Date: TRANSFORM AND CONQUER - HEAP SORT

AIM:

To write algorithm and python program to implement the Heap sorting using Transform
and Conquer algorithm.

ALGORITHM:

Step-1: Start the program

Step-2: Initialize largest as root and assign left=2*i+1 and right = 2*i+2.

Step-3: Build a max heap from the input data.

Step-4: At this point, the maximum element is stored at the root of the heap.

Step-5: Replace it with the last item of the heap followed by reducing the size of the heap by 1.

Step-6: Finally, heapify the root of the tree.

Step-7: Repeat step 4 while the size of the heap is greater than 1.

Step-8: Stop the program .

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)

10
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])

OUTPUT

Sorted array is5

11

12

13

RESULT:

Thus the program had executed successfully and output was verified.

11
 Ex.No: 5a DYNAMIC PROGRAMMING - COIN CHANGING PROBLEM
Date:

AIM:

To write the algorithm and python program to implement the coin changeproblem using
dynamic programming.

ALGORITHM

Step-1: Start the program

Step-2: The size of the dynamic progTable is equal to (number of coins +1)*(Sum +1).

Step-3: The first column value is one because there is only one way to change if the totalamount is 0.
(we do not include any coin).

Step-4: Row: The total number of coins. The fact that the first-row index is 0 indicatesthat no coin
is available. If the value index in the second row is 1, only the first coin is available.

Step-5: If the value index in the third row is 2, it means that the first two coins areavailable to add
to the total amount, and so on

Step-6: Column: Total amount (sum). Because the first-column index is 0, the sumvalue is 0. The
second column index is 1, so the sum of the coins should be 1.

Step-7: The third column value is 2, so a change of 2 is required, and so on.

Step-8: If the coin value is greater than the dynamicprogSum, the coin is ignored, i.e.
dynamicprogTable[i][j]=dynamicprogTable[i-1][j].

Step-9: If the coin value is less than the dynamicprogSum, you can consider it.

Step-10: Stop the program

CODING

INF = 100000

def min(x, y):

if x < y:

return x

return y

def coin_change(d, n, k):

M = [0]*(n+1)

12
 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:
Thus the implementation of coin change problem was executed successfullyand output was
verified.

13
 Ex.No:5b DYNAMIC PROGRAMMING -
Date: WARSHALL’S & FLOYD’S ALGORITHM

AIM:
To write the algorithm and python program to implement the warshall’s and floyd’s algorithm using
dynamic programming.

ALGORITHM:

Step 1: Start the program.

Step-2: Initialize the shortest paths between any 2 vertices with Infinity.

Step 3: Find all pair shortest paths that use 0 intermediate vertices, then find the shortest paths that use
1 intermediate vertex and so on.. until using all N vertices as intermediate nodes.

Step 4: Minimize the shortest paths between any 2 pairs in the previous operation.

Step 5: For any 2 vertices (i,j) , one should actually minimize the distances between this pairusing
the first K nodes, so the shortest path will be: min(dist[i][k]+dist[k][j],dist[i][j]).

Step-6: stop the program.

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

14
 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

0 3 7 5

2 0 6 4

3 1 0 5

5 3 2 0

RESULT:
Thus the implementation of warshall’s and floyd’s algorithm was executed successfully
and output was verified.

15
 Ex.No:5c DYNAMIC PROGRAMMING -
Date: KNAPSACK PROBLEM

AIM:

To write the algorithm and python program to implement the knapsack problem using
dynamic programming

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

Thus the implementation of knapsack problem using dynamicprogramming was

executed successfully and output was verified.

16
Ex.No:6a GREEDY TECHNIQUES
Date: DIJIKSTRA’S ALGORITHM

AIM

To write the algorithm and python program to implement the dijikstra’salgorithm using greedy technique.

ALGORITHM

Step-1: Start the program

Step-2: Mark the source node with a current distance of 0 and the rest with infinity.

Step-3: Set the non-visited node with the smallest current distance as the current node,
lets say C.

Step-4: For each neighbour N of the current node C: add the current distance of C with
the weight of the edge connecting C-N.

Step-5: If it is smaller than the current distance of N, set it as the new current distance
of N.

Step-6: Mark the current node C as visited.

Step-7: Go to step 3 if there are any nodes are unvisited.

Step-8: Stop the program

CODING:

class Graph():

def __init__(self, vertices):

self.V = vertices

self.graph = [[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

17
 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 = self.minDistance(dist, sptSet)

sptSet[u] = True

for v in range(self.V):

if (self.graph[u][v] > 0 and

sptSet[v] == False and

dist[v] > dist[u] + self.graph[u][v]): dist[v] = dist[u] + self.graph[u][v]

self.printSolution(dist)

g = Graph(9)

g.graph = [[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]]

g.dijkstra(0)

18
OUTPUT

Vertex Distance from Source

0 0

1 4

2 12

3 19

4 21

5 11

6 9

7 8

8 14

RESULT
Thus the implementation of dijikstra’s algorithm was executed successfullyand output
was verified.

19
 Ex.No:6b HUFFMAN TREES AND CODES
Date:

AIM
To write the algorithm and python program to implement the Huffman trees andcodes using greedy
technique.

ALGORITHM

Step-1 : Start the program

Step-2: Read the value of the string input

Step-3: Calculate the frequency of each character in the string.

Step-4: Sort the characters in increasing order of the frequency. These are stored in a
priority queue Q.

Step-5: Characters sorted according to the frequency

Step-6: Make each unique character as a leaf node.

Step-7: Create an empty node z. Assign the minimum frequency to the left child of z and
assign the second minimum frequency to the right child of z.
Step-8: Set the value of the z as the sum of the above two minimum
frequencies.Getting the sum of the least numbers
Step-9: Remove these two minimum frequencies from Q and add the sum into the list
of frequencies (* denote the internal nodes in the figure above).
Step-10: Insert node z into the tree.
Step-11: Repeat steps 3 to 5 for all the characters.

Step-12: Stop the program

CODING:

string = 'BCAADDDCCACACAC'

class NodeTree(object):

def __init__(self, left=None, right=None):

self.left = left

self.right = right

20
 def children(self):

return (self.left, self.right)

def nodes(self):

return (self.left, self.right)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

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], reverse=True)

huffmanCode = huffman_code_tree(nodes[0][0])

print(' Char | Huffman code ')

print('------------------------- ')

21
for (char, frequency) in freq:

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

OUTPUT

Char | Huffman code

----------------------

'C' | 0

'A' | 11

'D' | 101

'B' | 100

RESULT:
Thus, the implementation of Huffman tress and codes was executed successfully and output was
verified.

22
 Ex.No:7
ITERATIVE IMPROVEMENT - SIMPLEX ALGORITHM
Date:

AIM:

To write an algorithm and python program to implement the simplex algorithm.

ALGORITHM :

Step-1: Start the program

Step-2: Start with the initial basis associated with identity matrix.

Step-3: Calculate the relative profits.

Step-4: For MAX problem check ,If all the relative profits are less than or equal to 0,then the
current basis is the optimal one. STOP.

Step-5: Else continue to 8.

Step-6: For MIN problem check If all the relative profits are greater than or equal to 0,then the
current basis is the optimal one. STOP.

Step-7:Else continue to 8.

Step-8: Find the column corresponding to max relative profit. Say column k has themax

Step-9: Perform a min ratio test to determine which variable will leave the basis.

Step-10: It's evident that the entered variable will not form an identity matrix, sowe will have to
perform row operations to make it identity again.

Step-11: Find the pivot element. The element at index (r, k) will be the pivot elementand row r will
be the pivot row.

Step-12: Divide the rth row by pivot to make it 1. And subtract c*(rth row) from otherrows to make
them 0, where c is the coefficient required to make that row 0.

Step-13: Stop the program

Coding :

import numpy as np

from fractions import Fraction

print("\n ****SiMplex Algorithm

****\n\n")A = np.array([[1, 1, 0, 1], [2, 1, 1, 0]])

b = np.array([8, 10])

c = np.array([1, 1, 0, 0])

23
cb = np.array(c[3])

B = np.array([[3], [2]])

cb = np.vstack((cb, c[2]))

xb = np.transpose([b])

table = np.hstack((B, cb))

table = np.hstack((table, xb))

table = np.hstack((table, A))

table = np.array(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: ", 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()

i=0
rel_prof = []

24
while i<len(A[0]):

rel_prof.append(c[i] - np.sum(table[:, 1]*table[:, 3 +

i]))i = i + 1

print("rel profit: ", end =" ")for profit in rel_prof:

print(Fraction(str(profit)).limit_denominator(100), end =", ")

print()

i=0

b_var = table[:, 0]

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

i+= 1

print()

flag = 0

for profit in rel_prof:

if profit>0:

flag = 1break

if flag == 0:

print("All profits are <= 0, optimality

reached")reached = 1

break

k = rel_prof.index(max(rel_prof))min = 99999

25
 i = 0;

r = -1

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:

min = valr = i

i+= 1

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)) table[r, 2:len(table[0])] =

table[r, 2:len(table[0])] / pivot

i=0

while i<len(table):

if i != r:

print() i += 1

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

print()itr+= 1 table[i, 2:len(table[0])] = table[i,

2:len(table[0])] - table[i][3 + k] *table[r, 2:len(table[0])]

print("**************************************************

*************") if unbounded == 1:

print("UNBOUNDED LPP")

exit()

if alternate == 1:

26
 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+= 1if 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()

OUTPUT:

****Simplex Algorithm ****

Table at itr = 0

B CB XB y1 y2 y3 y4
3 0 8 1 1 0 1

27
2 0 10 2 1 1 0

Simplex Working....

Iteration: 1

B CB XB y1 y2 y3 y4

3 0 8 1 1 0 1

2 0 10 2 1 1 0

rel profit: 1, 1, 0, 0,

pivot element index: [1 3]

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

rel profit: 0, 1/2, -1/2, 0,

pivot element index: [0 4]

pivot element: 1/2

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,

Case of Alternate found

All profits are <= 0, optimality reached

**************************************************************

* ALTERNATE Solution

28
optimal table:

B CB XB y1 y2 y3 y4

1 1 6 0 1 -1 2

0 1 2 1 0 1 -1

value of Z at optimality: 8

Final Basis: ['x2', 'x1']

Simplex Finished...

RESULT:

Thus, the implementation of simplex method using iterative improvements was

executed successfully and output was verified.

29
 Ex.No:8a BACKTRACKING -
Date: N-QUEEN PROBLEM

AIM:
To write the algorithm and python program to implement the n-queen problem using
backtracking algorithm.

ALGORITHM:

Step-1: Start the program

Step-2: Start in the leftmost column

Step-3: If all queens are place then return true
Step-4: Try all rows in the current column. Do following for every tried row.
Step-4.1:If the queen can be placed safely in this row then mark this [row, column] as part of the
solution and recursively check if placing queen here leads to a solution.
Step-4.2:If placing the queen in [row, column] leads to a solution then return true.
Step-4.3: If placing queen doesn't lead to a solution then unmark this [row, column]
(Backtrack) and go to step (4.1) to try other rows.
Step-5: If all rows have been tried and nothing worked,return false to trigger backtracking.
Step-6: Stop the program.

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:

30
 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)

OUTPUT:

Enter the number of queens : 4[0, 1, 0, 0]

[0, 0, 0, 1]

[1, 0, 0, 0]

[0, 0, 1, 0]

RESULT:

Thus the implementation of n-queen problem was executed successfully and output was
verified.

31
 Ex.No:8b SUBSET SUM PROBLEM
Date:

AIM:
To write the algorithm and python program to implement the subset sum problem.

ALGORITHM:

Step-1: Start the program

Step-2: Start with an empty set.

Step-3: Include the next element from list to set.

Step-4: If the numbers in the set sum up to given target_sum, It is a solution set.

Step-5: If the set doesnot sum upto the target_sum or if we have reached the end ofmy_list, then
backtrack the set until we find a solution set.

Step-6: If we get a feasible solution, go to step 2.

Step-7: If we have traversed all the elements and if no backtracking is possible, thenstop without
solution.

Step-8: Stop the program

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 :

32
 print("No subset with given sum")

OUTPUT:

Found a subset with given sum

RESULT:
Thus, the implementation of subset sum problem using backtracking algorithm was
executed successfully and output was verified.

33
 BRANCH AND BOUND -
Ex.No:9
TRAVELLING SALESMAN PROBLEM
Date:

AIM:

To write the algorithm and python program to implement the travelling salesman problem
using branch and bound algorithm.

ALGORITHM

Step-1: Start the program

Step-2: Read the values of graph from the user

Consider city 1 as the starting and ending point. Since the route is cyclic, we canconsider any
point as a starting point.

Step-3: Generate all (n-1)! permutations of cities.

Step-4: Calculate the cost of every permutation and keep track of the minimum costpermutation.

Step-5: Return the permutation with minimum cost.

Step-6: Stop the program

CODING:

from sys import maxsize

from itertools import permutationsV

=4

def travellingSalesmanProblem(graph, s):

vertex = []

for i in range(V):

if i != s:

vertex.append(i) min_path = maxsize

next_permutation=permutations(vertex)for i in next_permutation:

current_pathweight = 0k = s

for j in i:

current_pathweight += graph[k][j]

34
 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:

Thus, the implementation of salesman problem using branch and bound was executed
successfully and output was verified.

35