PROGRAM 1: DATA STRUCTURES

SOURCE CODE:
def arrfun():
alen=int(input("Enter the Length of array "))
arr=[0 for i in range(alen)]
for j in range(alen):
arr[j]=int(input("Enter the Array Elements "))
print("The Given array is ",arr)
def listfun():
len=int(input("Enter the Length of the List "))
list1=[]
for j in range(len):
list1.append(eval(input("Enter the Elements ")))
print("The Given List is ",list1)
def tup():
tlen=int(input("Enter the Length of tuple"))
tup1=[]
for i in range(tlen):
tup1.append(eval(input("Enter the Elements ")))
dtuple=tuple(tup1)
print("The Given tuple is ",dtuple)
def dictf():
dlen=int(input("Enter the Length of the dictionary "))
dict1={}
for i in range(dlen):
key=eval(input("Enter the Key "))
value=eval(input("Enter the Value "))
dict1[key]=value
print(dict1)
def setfun():
slen=int(input("Enter the Length of the set "))
set1=[]
for j in range(slen):
set1.append(eval(input("Enter the Set Element ")))
aset=set(set1)
print(aset)
print("Select Your choice of data Structure \n 1.Array\n 2.List\
n 3.Tuple\n 4.Dictionary\n 5.Set ")
choice=int(input("Enter Your Choice "))
if(choice==1):
print("Array Data Structure ")
arrfun()
elif(choice==2):
print("List Data Structure ")
listfun()
elif(choice==3):
print("Tuple Data Structure ")
tup()
elif(choice==4):
print("Dictionary Data Structure ")
dictf()
elif(choice==5):
print("Set Data Structure ")
setfun()
else:
print("Enter Between 1 to 5 ")
OUTPUT:
Select Your choice of data Structure
1.Array
2.List
3.Tuple
4.Dictionary
5.Set
Enter Your Choice 1
Array Data Structure
Enter the Length of array 5
Enter the Array Elements 45
Enter the Array Elements 96
Enter the Array Elements 78
Enter the Array Elements 14
Enter the Array Elements 23
The Given array is [45, 96, 78, 14, 23]
PROGRAM 2: FIBONACCI SERIES (NON RECURSIVE)
SOURCE CODE:
def fib(n):
fv=0
sv=1
sum=0
if n==1:
print(0)
elif n>=2:
print(0)
print(1)
for i in range(n-2):
sum=fv+sv
print(sum)
fv=sv
sv=sum
else:
print("Cant print less than Zero ")
limit=int(input("Enter the limit of Fibonacc series "))
fib(limit)
OUTPUT:
Enter the limit of Fibonacc series 6
0
1
1
2
3
5
PROGRAM 3: FIBONACCI SERIES(RECURSIVE)
SOURCE CODE:
def fib(x):
if(x==0):
return 0
elif(x==1):
return 1
else:
return fib(x-1)+fib(x-2)
x=int(input("Enter the Number of series"))
for i in range(x):
print(fib(i))
OUTPUT:
Enter the Number of series 9
0
1
1
2
3
5
8
13
21
PROGRAM 4: SELECTION SORT IN PYTHON
SOURCE CODE:
def selectionSort(array, size):
for step in range(size-1):
min_idx=step
print('Iteration : ')
print(array)
for i in range(step + 1, size):

if array[i]<array[min_idx]:
min_idx = i
(array[step], array[min_idx]) = (array[min_idx],
array[step])

n=int(input("Enter how many numbers:"))

n1=n
a=[]
while n>0:
a.append(int(input("Enter a number: ")))
n=n-1
print('Given Array: ')
print(a)
selectionSort(a, n1)
print('Sorted array in Ascending Order:')
print(a)
OUTPUT:
Enter how many numbers: 4
Enter a number: 23
Enter a number: 45
Enter a number: 89
Enter a number: 14
Given Array:
[23, 45, 89, 14]
Iteration :
[23, 45, 89, 14]
Iteration :
[14, 45, 89, 23]
Iteration :
[14, 23, 89, 45]
Sorted array in Ascending Order:
[14, 23, 45, 89]
PROGRAM 5: BINARY SEARCH
def binf(arr,a,low,high):
if high >= low:
mid=low+(high-low)//2
if arr[mid]==a:
return mid
elif arr[mid] > a:
return binf(arr,a,low,mid-1)
else:
return binf(arr,a,mid+1,high)
else:
return n-1
n=int(input("Enter how many numbers: "))
n1=n
arr=[]
while n>0:
arr.append(int(input("Enter the Number ")))
n=n-1
print("The given array is: ",arr)
a=int(input("Enter the Number to be searched "))
print("The Element to be found is ",a)
index=binf(arr,a,0,len(arr)-1)
if index !=-1:
print("Elements is present at index "+ str(index))
else:
print(" Not Found ")
OUTPUT:
Enter how many numbers: 5
Enter the Number 78
Enter the Number 32
Enter the Number 1
Enter the Number 6
Enter the Number 4
The given array is: [78, 32, 1, 6, 4]
Enter the Number to be searched 6
The Element to be found is 6
Elements is present at index 3
PROGRAM 6: MERGE SORT
SOURCE CODE:
def merge(arr, l, m, r):
n1 = m - l + 1
n2 = r - m
L = [0] * (n1)
R = [0] * (n2)

for i in range(0, n1):

L[i] = arr[l + i]

for j in range(0, n2):

R[j] = arr[m + 1 + j]

i = 0
j = 0
k = l
while i < n1 and j < n2:
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1

while i < n1:

arr[k] = L[i]
i += 1
k += 1

while j < n2:

arr[k] = R[j]
j += 1
k += 1
def mergeSort(arr, l, r):
if l < r:
m = l+(r-l)//2
mergeSort(arr, l, m)
mergeSort(arr, m+1, r)
merge(arr, l, m, r)

n=int(input("Enter how many numbers: "))

n1=n
arr=[]
while n>0:
arr.append(int(input("Enter the Number ")))
n=n-1
print("Given array is")
print(arr)
mergeSort(arr, 0, n1-1)
print("\n\nSorted array is")
print(arr)
OUTPUT:
Enter how many numbers: 5
Enter the Number :23
Enter the Number :4
Enter the Number :85
Enter the Number :2
Enter the Number :45
Given array is
[23, 4, 85, 2, 45]

Sorted array is
[2, 4, 23, 45, 85]
PROGRAM 7: QUICK SORT
SOURCE CODE:
def part(arr,low,high):
i=(low-1)
pivot=arr[high]
for j in range(low,high):
if arr[j]<=pivot:
i=i+1
arr[i],arr[j]=arr[j],arr[i]
arr[i+1],arr[high]=arr[high],arr[i+1]
return(i+1)
def quicks(arr,low,high):
if low < high:
pi=part(arr,low,high)
quicks(arr,low,pi-1)
quicks(arr,pi*1,high)
n=int(input("Enter how many numbers :"))
arr=[]
while n>0:
arr.append(int(input("Enter a Number : ")))
n=n-1
print("The Given Array is: ")
print(arr)
n=len(arr)
quicks(arr,0,n-1)
print("Sorted Array: ")
print(arr)
OUTPUT:
Enter how many numbers :6
Enter a Number : 12
Enter a Number : 5
Enter a Number : 4
Enter a Number : 21
Enter a Number : 7
Enter a Number : 10
The Given Array is:
[12, 5, 4, 21, 7, 10]
Sorted Array:
[4, 5, 7, 10, 12, 21]
EX :08 INORDER,PREORDER,POSTORDER TREE TRAVERSAL
INORDER SOURCE CODE:
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def inorderTraversal(root):
answer = []
inorderTraversalUtil(root, answer)
return answer

def inorderTraversalUtil(root, answer):

if root is None:
return
inorderTraversalUtil(root.left, answer)
answer.append(root.val)
inorderTraversalUtil(root.right, answer)
return
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(inorderTraversal(root))
OUTPUT:
[4, 2, 5, 1, 3]
PREORDER SOURCE CODE:
class TreeNode:
def __init__(self,val):
self.val = val
self.left = None
self.right = None
def preorderTraversal(root):
answer = []
preorderTraversalUtil(root, answer)
return answer
def preorderTraversalUtil(root, answer):
if root is None:
return
answer.append(root.val)
preorderTraversalUtil(root.left, answer)
preorderTraversalUtil(root.right, answer)

return
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorderTraversal(root))
OUTPUT:
[1, 2, 4, 5, 3]
POSTORDER SOURCE CODE:
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def postorderTraversal(root):
answer = []
postorderTraversalUtil(root, answer)
return answer
def postorderTraversalUtil(root, answer):
if root is None:
return
postorderTraversalUtil(root.left, answer)
postorderTraversalUtil(root.right, answer)
answer.append(root.val)
return
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(postorderTraversal(root))
OUTPUT:
[4, 5, 2, 3, 1]
EX :09 BINARY TREE CREATION
SOURCE CODE:
class Node:
def __init__(self,data):
self.left=None
self.right=None
self.data=data
def insert(self,data):
if self.data:
if data<self.data:
if self.left is None:
self.left=Node(data)
else:
self.left.insert(data)
elif data>self.data:
if self.right is None:
self.right=Node(data)
else:
self.right.insert(data)
else:
self.data=data
def printtree(self):
if self.left:
self.left.printtree()
print(self.data)
if self.right:
self.right.printtree()
root=Node(27)
root.insert(14)
root.insert(35)
root.insert(31)
root.insert(10)
root.insert(19)
root.printtree()
OUTPUT:
10
14
19
27
31
35
EP 10: BINARY TREE TRAVERSAL
SOURCE CODE:
class Node:
def __init__(self,data):
self.left=None
self.right=None
self.data=data
def insert(self,data):
if self.data:
if data<self.data:
if self.left is None:
self.left=Node(data)
else:
self.left.insert(data)
elif data>self.data:
if self.right is None:
self.right=Node(data)
else:
self.right.insert(data)
else:
self.data=data
def printtree(self):
if self.left:
self.left.printtree()
print(self.data)
if self.right:
self.right.printtree()
def inorder(self,root):
res=[]
if root:
res=self.inorder(root.left)
res.append(root.data)
res=res+self.inorder(root.right)
return res
def preorder(self,root):
res=[]
if root:
res.append(root.data)
res=res+self.preorder(root.left)
res=res+self.preorder(root.right)
return res
def postorder(self,root):
res=[]
if root:
res=self.postorder(root.left)
res=res+self.postorder(root.right)
res.append(root.data)
return res
root=Node(27)
root.insert(14)
root.insert(35)
root.insert(31)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print("binary Tree")
root.printtree()
print("InOrder Tree Traversal",root.inorder(root))
print("Preorder tree Traversal",root.preorder(root))
print("Post order tree Traversal",root.postorder(root))
OUTPUT:
binary Tree
10
14
19
27
31
35
42
InOrder Tree Traversal [10, 14, 19, 27, 31, 35, 42]
Preorder tree Traversal [27, 14, 10, 19, 35, 31, 42]
Post order tree Traversal [10, 19, 14, 31, 42, 35, 27]
EX 11: MULTIPLICATION OF LARGE NUMBER:
SOURCE CODE:
print("Kindly enter two large integers of same length")
A = int(input("Enter the first large integer:"))
B = int(input("Enter the second large integer:"))
n = len(str(A))
if len(str(A)) == len(str(B)):
A1 = int(A/pow(10, int(n/2)))
A0 = int(A%pow(10, int(n/2)))
B1 = int(B/pow(10, int(n/2)))
B0 = int(B%pow(10, int(n/2)))
C2 = A1 * B1
C0 = A0 * B0
C1 = (A1 + A0) * (B1 + B0) - (C2 + C0)
c = C2 * pow(10, 2) + C1 * (pow(10, 1)) + C0
if n%2 != 0:
c = C2 * pow(10, 2) + C1 * (pow(10, 1)) + C0
print("Product of two integer is:", c)
else:
print("Given inputs are of different length")
OUTPUT:
Kindly enter two large integers of same length
Enter the first large integer: 100
Enter the second large integer:100
Product of two integer is: 10000
EX 12: PRIM’S ALGORITHM
SOURCE CODE:
INF=9999999
N=5
G=[[0,19,5,0,0],
[19,0,5,9,2],
[5,5,0,1,6],
[0,9,1,0,1],
[0,2,6,1,0]]
selected_node=[0,0,0,0,0]
no_edge=0
selected_node[0]=True
print("Edge:Weight\n")
while(no_edge<N-1):
minimum=INF
a=0
b=0
for m in range(N):
if selected_node[m]:
for n in range(N):
if((not selected_node[n])and G[m][n]):
if minimum>G[m][n]:
minimum=G[m][n]
a=m
b=n
print(str(a)+"-"+str(b)+":"+str(G[a][b]))
selected_node[b]=True
no_edge+=1
OUTPUT:
Edge:Weight

0-2:5
2-3:1
3-4:1
4-1:2
EX 13: KRUSKAL’S ALGORITHM
SOURCE CODE:
class Graph:
def __init__(self,vertex):
self.v = vertex
self.graph = []
def addedge(self,u,v,w):
self.graph.append([u,v,w])
def search(self,parent,i):
if parent[i]==i:
return i
return self.search(parent,parent[i])
def applyunion(self,parent,rank,x,y):
xroot=self.search(parent,x)
yroot=self.search(parent,y)
if rank[xroot] < rank[yroot]:
parent[xroot]=yroot
elif rank[xroot] > rank[yroot]:
parent [yroot]=xroot
else:
parent[yroot]=xroot
rank[xroot]+=1
def kruskal(self):
result=[]
i,e = 0,0
self.graph=sorted(self.graph,key=lambda item:item[2])
parent=[]
rank=[]
for node in range(self.v):
parent.append(node)
rank.append(0)
while e< self.v-1:
u,v,w=self.graph[i]
i=i+1
x=self.search(parent,u)
y=self.search(parent,v)
if x!=y:
e=e+1
result.append([u,v,w])
self.applyunion(parent,rank,x,y)
for u,v,weight in result:
print("Edge: ",u,v,end=" ")
print("-",weight)
g=Graph(5)
g.addedge(0,1,8)
g.addedge(0,2,5)
g.addedge(1,2,9)
g.addedge(1,3,11)
g.addedge(2,3,15)
g.addedge(2,4,10)
g.addedge(3,4,7)
g.kruskal()
OUTPUT:
Edge: 0 2 - 5
Edge: 3 4 - 7
Edge: 0 1 - 8
Edge: 2 4 – 10
EX 14: DIJKSTRA’S ALGORITHM
SOURCE CODE:
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
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)
OUTPUT:
Vertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14
EX 15: BUBBLE SORT
SOURCE CODE:
def bubbleSort(arr):
n = len(arr)
for i in range(n-1):
for j in range(0, n-i-1):

if arr[j] > arr[j + 1] :

arr[j], arr[j + 1] = arr[j + 1], arr[j]
n=int(input("Enter how many numbers"))
n1=n
arr=[]
while n>0:
arr.append(int(input("Enter a number")))
n=n-1
print('Given array')
print(arr)
bubbleSort(arr)
print ("Sorted array is:")
for i in range(len(arr)):
print ("% d" % arr[i],end=" ")
OUTPUT:
Enter how many numbers3
Enter a number3
Enter a number1
Enter a number2
Given array
[3, 1, 2]
Sorted array is:
1 2 3
EX 16: INSERTION SORT
SOURCE CODE:
def insertionSort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >=0 and key < arr[j] :
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
n=int(input("NO OF ELEMENTS"))
n1=n
arr=[]
while n>0:
arr.append(int(input(" ENTER ELEMENT ")))
n=n-1

insertionSort(arr)
print ("SORTED ARRAY : ")
for i in range(len(arr)):
print ("%d" %arr[i])
OUTPUT:
NO OF ELEMENTS 3
ENTER ELEMENT 2
ENTER ELEMENT 4
ENTER ELEMENT 1
SORTED ARRAY :
1
2
4
EX 17: LINEAR SEARCH
SOURCE CODE:
def LinearSearch(array, n, k):
for j in range(0,n):
if (array[j]==k):
return j
return -1
n=int(input("Enter how many numbers : "))
array=[]
while n>0:
array.append(int(input("enter a number :")))
n=n-1
k=int(input("Enter number to be searched : "))
n=len(array)
result = LinearSearch(array,n,k)
if(result == -1):
print("Element not found")
else:
print("Element Found")
OUTPUT:
Enter how many numbers : 4
enter a number :2
enter a number :3
enter a number :4
enter a number :5
Enter number to be searched : 2
Element Found
EX 18: DEPTH FIRST SEARCH
SOURCE CODE:
from collections import defaultdict
class Graph:
def __init__(self):
self.graph=defaultdict(list)
def addEdge(self,u,v):
self.graph[u].append(v)
def DFSUtil(self,v,visited):
visited.add(v)
print(v,end='')
for neighbour in self.graph[v]:
if neighbour not in visited:
self.DFSUtil(neighbour,visited)
def DFS(self,v):
visited=set()
self.DFSUtil(v,visited)
g=Graph()
g.addEdge(0,1)
g.addEdge(0,2)
g.addEdge(1,2)
g.addEdge(2,0)
g.addEdge(2,3)
g.addEdge(3,3)
print("Following is DFS from(starting from vertex2)")
g.DFS(2)
OUTPUT:
Following is DFS from(starting from vertex2)
2013
EX 19: BREADTH FIRST SEARCH
SOURCE CODE:
from collections import defaultdict
class Graph:
def __init__(self):
self.graph=defaultdict(list)
def addEdge(self,u,v):
self.graph[u].append(v)
def BFS(self,s):
visited=[False]*(max(self.graph)+1)
queue=[]
queue.append(s)
visited[s]=True
while queue:
s=queue.pop(0)
print(s,end="")
for i in self.graph[s]:
if visited[i]==False:
queue.append(i)
visited[i]=True
g=Graph()
g.addEdge(0,1)
g.addEdge(0,2)
g.addEdge(1,2)
g.addEdge(2,0)
g.addEdge(2,3)
g.addEdge(3,3)
print("Following is BFS from""(starting from vertex2)")
g.BFS(2)
OUTPUT:
Following is BFS from(starting from vertex2)
2031
EX 20: BINOMIAL COEFFICIENT
SOURCE CODE:
def binomialcoeff(n,k):
if k>n:
return 0
if k==0 or k==n:
return 1
return binomialcoeff(n-1,k-1)+binomialcoeff(n-1,k)
n=5
k=2
print("Value of C(%d,%d)is(%d)"%(n,k,binomialcoeff(n,k)))
OUTPUT:
Value of C(5,2)is(10)
EX 21: FLOYD WARSHALL ALGORITHM
SOURCE CODE:
nV=4
INF=999
def floydwarshall(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]]
floydwarshall(G)
OUTPUT:
0375
2064
3105
5320
EX 22: KNAPSACK PROBLEM
SOURCE CODE:
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
EX 23: 4-QUEEN PROBLEM
SOURCE CODE:
global N
N=4
def printsolution(board):
for i in range(N):
for j in range(N):
print(board[i][j],end="")
print()
def isSafe(board,row,col):
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 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=[[0,0,0,0],
[0,0,0,0],
[0,0,0,0],
[0,0,0,0]]
if solveNQUtil(board,0)==False:
print("Solution does not exist")
return False
printsolution(board)
return True
solveNQ()
OUTPUT:
0010
1000
0001
0100
EX 24: SUM OF SUBSET
SOURCE CODE:
def sumofsubset(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:
list1.append(my_list[i])
print(list1)
elif s+my_list[k]+my_list[k+1]<=target_sum:
sumofsubset(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
sumofsubset(s,k+1,rem-my_list[k])
my_list=[]
n=int(input("Enter number of element:"))
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)
sumofsubset(0,0,total)
OUTPUT:
Enter number of element: 10
1
4
3
1
6
7
5
18
90
55
Enter required sum: 5
[1, 1, 3]
[1, 4]
[1, 4]
[5]