PRACTICAL OBSERVATION
Register Number
Name
Year / Sem
Degree / Branch
Subject Code & Name
INDEX
Ex. Page Staff
Date Name of the Experiment Marks
No No Signature
Ex.No:1 IMPLEMENT SIMPLE ADTS AS PYTHON CLASSES
AIM:
ALGORITHM:
POGRAM :
Stack: stack = []
stack.append('a')
stack.append('b')
stack.append('c')
print('Initial
stack') print(stack)
print('\nElements poped from
stack:') print(stack.pop())
print(stack.pop()) print(stack.pop())
print('\nStack after elements are poped:') print(stack)
Queue: queue = []
queue.append('a')
queue.append('b')
queue.append('c')
print("Initial
queue") print(queue)
print("\nElements dequeued from
queue") print(queue.pop(0))
print(queue.pop(0)) print(queue.pop(0))
print("\nQueue after removing elements") print(queue)
List:
List = [1,2,3,4]
print("Initial List: ")
print(List)
List.extend([8, 'Geeks', 'Always'])
print("\nList after performing Extend Operation: ") print(List)
OUTPUT:
RESULT:
EX.NO:2 IMPLEMENT RECURSIVE ALGORITHMS IN PYTHON
AIM:
ALGORITHM:
PROGRAM:
No = 10 num1, num2 = 0,
1 count = 0 if No <= 0:
print("Invalid Number")
elif No == 1: print("Fibonacci sequence for limit
of ",No,":") print(num1) else:
print("Fibonacci
sequence:") while count <
No: print(num1)
nth = num1 + num2
num1 = num2
num2 = nth count
+= 1
OUTPUT:
RESULT:
EX.NO:3 IMPLEMENT LIST ADT USING PYTHON ARRAYS
AIM:
ALGORITHM:
index=0 cur=head
while(cur!=None): arr.append(cur.data) cur=cur.next
printarray(arr, len) head=node(0) head=add(6)
head.next = add(4) head.next.next = add(3) head.next.next.next = add(4) convertarr(head)
Output:
RESULT:
Ex.NO:4 LINKED LIST IMPLEMENTATIONS OF LIST
AIM:
ALGORITHM:
PROGRAM:
List = [1,2,3,4]
print("Initial List: ")
print(List)
List.extend([8, 'Geeks', 'Always'])
print("\nList after performing Extend
Operation: ") print(List) List = [] print("Blank
List: ") print(List) List = [10, 20, 14]
print("\nList of numbers: ")
print(List)
List = ["Geeks", "For", "Geeks"]
print("\nList Items: ")
print(List[0])
print(List[2])
Adding the
elements: List =
[1,2,3,4]
print("Initial List: ")
print(List)
List.insert(3, 12)
List.insert(0,
'Geeks')
print("\nList after performing Insert Operation: ")
print(List)
List = [1, 2, 3, 4, 5, 6,
7, 8, 9, 10, 11, 12]
print("Intial List: ") print(List)
List.remove(5)
List.remove(6) print("\nList after Removal of
two elements: ") print(List) for i in
range(1, 5):
List.remove(i) print("\nList after Removing a
range of elements: ") print(List)
List = [['Geeks', 'For'] , ['Geeks']] print("\nMulti-
Dimensional List: ")
print(List)
OUTPUT:
RESULT:
EX.NO:5 IMPLEMENTATION OF STACK AND QUEUE ADTS
AIM:
ALGORITHM:
PROGRAM:
stack = []
stack.append('a
')
stack.append('b
')
stack.append('c
') print('Initial
stack')
print(stack)
print('\nElements poped from
stack:') print(stack.pop())
print(stack.pop())
print(stack.pop())
print('\nStack after elements are poped:')
print(stack)
Queue: queue =
[]
queue.append('a')
queue.append('b')
queue.append('c')
print("Initial
queue")
print(queue)
print("\nElements dequeued from
queue") print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))
print("\nQueue after removing elements")
print(queue)
OUTPUT:
RESULT:
EX.NO:6A APPLICATION OF LIST
AIM:
ALGORITHM:
PROGRAM:
def add(A, B, m, n):
size = max(m, n);
sum = [0 for i in range(size)] for
i in range(0, m, 1):
sum[i] = A[i]
for i in range(n):
sum[i] += B[i]
return sum
def printPoly(poly, n):
for i in range(n):
print(poly[i], end = "") if
(i != 0):
print("x^", i, end = "")
if (i != n - 1):
print(" + ", end = "") if
name == ' main ':
A = [5, 0, 10, 6]
B = [1, 2, 4]
m = len(A)
n = len(B)
print("First polynomial is")
printPoly(A, m)
print("\n", end = "")
print("Second polynomial is")
printPoly(B, n)
print("\n", end = "")
sum = add(A, B, m, n)
size = max(m, n)
print("sum polynomial is")
printPoly(sum, size)
C
OUTPUT:
RESULT:
EX.NO:6B APPLICATION OF STACK
AIM:
ALGORITHM:
PROGRAM:
class Conversion:
def init (self,
capacity): self.top = -1
self.capacity = capacity
self.array = [] self.output = [] self.precedence
= {'+':1, '-':1, '*':2, '/':2, '^':3}
def isEmpty(self): return True if self.top
== -1 else False
def peek(self): return
self.array[-1]
def pop(self):
if not self.isEmpty():
self.top -= 1 return
self.array.pop()
else: return
"$"
def push(self, op):
self.top += 1
self.array.append(op)
def isOperand(self, ch):
return ch.isalpha()
def notGreater(self, i):
try:
a = self.precedence[i] b =
self.precedence[self.peek()] return
True if a <= b else False
except KeyError:
return False
def infixToPostfix(self, exp):
for i in exp:
if self.isOperand(i):
self.output.append(i)
elif i == '(':
self.push(i)
elif i == ')':
while( (not self.isEmpty()) and self.peek() !=
'('):
a = self.pop() self.output.append(a)
if (not self.isEmpty() and self.peek() !=
'('): return -1 else:
self.pop()
else:
while(not self.isEmpty() and self.notGreater(i)):
self.output.append(self.pop()) self.push(i)
while not self.isEmpty():
self.output.append(self.pop())
print "".join(self.output)
exp = "a+b*(c^d-e)^(f+g*h)-i"
obj = Conversion(len(exp))
obj.infixToPostfix(exp)
OUTPUT:
RESULT:
Ex.No:6c APPLICATION OF QUEUE
AIM:
ALGORITHM:
PROGRAM:
def findWaitingTime(processes, n,bt, wt):
wt[0] = 0 for i in range(1, n ): wt[i] = bt[i - 1] + wt[i - 1] def
findTurnAroundTime(processes, n,bt, wt, tat): # calculating
turnaround
# time by adding bt[i] + wt[i] for
i in range(n): tat[i] = bt[i] + wt[i]
def findavgTime( processes, n, bt):
wt = [0] * n
tat = [0] * n
total_wt = 0
total_tat = 0 findWaitingTime(processes, n, bt, wt)
findTurnAroundTime(processes, n,bt, wt, tat)
print( "Processes Burst time " +" Waiting time " +" Turn around time")
for i in range(n): total_wt =
total_wt + wt[i] total_tat =
total_tat + tat[i]
print(" " + str(i + 1) + "\t\t" +str(bt[i]) + "\t " str(wt[i])
+ "\t\t " +str(tat[i]))
print( "Average waiting time = "+
str(total_wt / n)) print("Average turn
around time = "+ str(total_tat / n))
if name ==" main ":
processes = [ 1, 2, 3]
n = len(processes)
burst_time = [10, 5, 8]
OUTPUT:
RESULT:
EX.NO:7 IMPLEMENTATION OF SORTING AND SEARCHING
ALGORITHMS
7A. LINEAR SEARCH
AIM:
ALGORITHM:
PROGRAM:
list_of_elements = [4, 3, 8, 9, 2, 7] x=int (input ("Enter no to
search :")) found = False for i in range (len(list_of_elements)):
if (list_of_elements[i] == x):
found = True
print ("%d found at %dth position"%( x,i)) break
if (found == False): print ("%d is not in list"%x)
OUTPUT:
RESULT:
CD3281
Ex.No:7B BINARY SEARCH
AIM:
ALGORITHM:
26
PROGRAM: BINARY SEARCH
def binary_search(item_list,item):
first = 0 last = len(item_list)-1 found = False
while( first<=last and not found):
mid = (first + last)//2 if item_list[mid] == item :
found = True else:
if item < item_list[mid]:
last = mid - 1
else:
first = mid + 1 return found
print(binary_search([1,82,3,5,8], 9))
print(binary_search([1,2,3,5,8], 5))
OUTPUT:
RESULT:
EX.NO:7C SELECTION SORT
AIM:
ALGORITHM:
PROGRAM: SELECTION SORT
def selectionSort(alist): for fillslot in
range(len(alist)-1,0,-1):
positionOfMax=0 for location in
range(1,fillslot+1): if
alist[location]>alist[positionOfMax]:
positionOfMax = location
temp = alist[fillslot]
alist[fillslot] = alist[positionOfMax] alist[positionOfMax] = temp alist
= [45,62,13,71,77,31,49,53,20]
selectionSort (alist) print(alist)
OUTPUT:
RESULT:
EX.NO:7D INSERTION SORT
AIM:
ALGORITHM:
PROGRAM: INSERTION SORT
def insertionSort(alist):
for index in range(1,len(alist)): currentvalue =
alist[index] position = index while position > 0
and alist[position - 1] > currentvalue:
alist[position] = alist[position - 1] position =
position - 1 alist[position] = currentvalue alist
= [15, 22, 39,41 , 67, 73, 85, 86, 90]
insertionSort(alist) print(alist)
OUTPUT:
RESULT:
EX.NO:8 IMPLEMENTATION OF HASH TABLES
AIM:
ALGORITHM:
Coding:
hashTable = [[],] * 10 def
checkPrime(n):
if n == 1 or n == 0: return
0
for i in range(2, n//2):
if n % i == 0:
return 0
return 1
def getPrime(n):
if n % 2 == 0:
n=n+1
while not checkPrime(n): n
+= 2
return n
def hashFunction(key):
capacity =
getPrime(10) return key
% capacity
def insertData(key, data):
index = hashFunction(key)
hashTable[index] = [key, data]
def removeData(key):
index = hashFunction(key) hashTable[index]
=0
insertData(123, "apple")
insertData(432, "mango")
insertData(213,
"banana")
insertData(654, "guava")
print(hashTable)
removeData(123)
print(hashTable)
OUTPUT:
RESULT:
EX.NO:9A TREE REPRESNTATION
AIM:
ALGORITHM:
CODING:
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(12) root.insert(6)
root.insert(14) root.insert(3)
OUTPUT:
RESULT:
EX.NO:9B TREE TRAVERSAL ALGORITHMS
AIM:
ALGORITHM:
Coding:
class Node:
def init (self,key): self.left = None
self.right = None self.val = key
def printInorder(root):
if root:
printInorder(root.left) print(root.val),
printInorder(root.right)
def printPostorder(root):
if root:
printPostorder(root.left)
printPostorder(root.right) print(root.val),
def printPreorder(root):
if root: print(root.val),
printPreorder(root.left)
printPreorder(root.right)
root = Node(1) root.left
= Node(2) root.right
= Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print ("\nPreorder traversal of binary tree is") printPreorder(root)
print ("\nInorder traversal of binary tree is") printInorder(root)
print ("\nPostorder traversal of binary tree is") printPostorder(root)
OUTPUT:
RESULT:
EX.NO:10 IMPLEMENTATION OF BINARY SEARCH TREE
AIM:
ALGORITHM:
Coding:
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 findval(self, lkpval):
if lkpval < self.data:
if self.left is None:
return str(lkpval)+" Not Found"
return self.left.findval(lkpval)
elif lkpval > self.data:
if self.right is None:
return str(lkpval)+" Not Found"
return self.right.findval(lkpval)
else:
print(str(self.data) + ' is found')
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data), if
self.right:
self.right.PrintTree()
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
print(root.findval(7))
OUTPUT:
RESULT:
Ex.NO:11 IMPLEMENTATION OF HEAPS
AIM:
ALGORITHM:
CODING:
import heapq H =
[21,1,45,78,3,5]
heapq.heapify(H)
print(H)
heapq.heappush(H,8)
print(H) heapq.heappop(H)
print(H)
OUTPUT:
RESULT:
EX.NO:12A GRAPH REPRESENTATION
AIM:
ALGORITHM:
Graph Representation Coding:
class graph:
def init (self,gdict=None):
if gdict is None: gdict
= []
self.gdict = gdict
def getVertices(self):
return list(self.gdict.keys())
graph_elements = { "a" : ["b","c"],
"b" : ["a", "d"],
"c" : ["a", "d"],
"d" : ["e"],
"e" : ["d"]
}
g = graph(graph_elements)
print(g.getVertices()) class
graph:
def init (self,gdict=None):
if gdict is None: gdict
= {}
self.gdict = gdict
def edges(self):
return self.findedges()
def findedges(self):
edgename = [] for
vrtx in self.gdict:
for nxtvrtx in self.gdict[vrtx]:
if {nxtvrtx, vrtx} not in edgename:
edgename.append({vrtx, nxtvrtx}) return
edgename
graph_elements = { "a" : ["b","c"],
"b" : ["a", "d"],
"c" : ["a", "d"],
"d" : ["e"],
"e" : ["d"]
}
g = graph(graph_elements)
print(g.edges())
OUTPUT:
RESULT:
EX.NO:12B GRAPH TRAVERSAL ALGORITHMS
AIM:
ALGORITHM:
Coding:
BFS import collections def bfs(graph, root): visited, queue = set(),
collections.deque([root]) visited.add(root) while queue: vertex =
queue.popleft() print(str(vertex) + " ", end="") for neighbour in
graph[vertex]:
if neighbour not in visited: visited.add(neighbour)
queue.append(neighbour)
if name == ' main ':
graph = {0: [1, 2], 1: [2], 2: [3], 3: [1, 2]}
print("Following is Breadth First Traversal: ")
bfs(graph, 0)
OUTPUT:
DFS Coding:
import sys def ret_graph(): return {
'A': {'B':5.5, 'C':2, 'D':6},
'B': {'A':5.5, 'E':3},
'C': {'A':2, 'F':2.5},
'D': {'A':6, 'F':1.5},
'E': {'B':3, 'J':7},
'F': {'C':2.5, 'D':1.5, 'K':1.5, 'G':3.5},
'G': {'F':3.5, 'I':4},
'H': {'J':2},
'I': {'G':4, 'J':4},
'J': {'H':2, 'I':4},
'K': {'F':1.5}
} start =
'A' dest = 'J'
visited = []
stack = [] graph = ret_graph() path = []
stack.append(start)
visited.append(start) while
stack: curr = stack.pop()
path.append(curr) for neigh
in graph[curr]:
if neigh not in visited:
visited.append(neigh)
stack.append(neigh) if
neigh == dest :
print("FOUND:", neigh)
print(path) sys.exit(0)
print("Not found")
print(path)
OUTPUT:
RESULT:
Ex. NO.13
IMPLEMENTATION OF SINGLE SOURCE
SHORTEST PATH ALGORITHM
AIM:
ALGORITHM:
CODING:
from sys import maxsize def
BellmanFord(graph, V, E, src): dis
= [maxsize] * V dis[src] = 0 for i
in range(V - 1): for j in range(E):
if dis[graph[j][0]] + \ graph[j][2] <
dis[graph[j][1]]:
dis[graph[j][1]] = dis[graph[j][0]] + \
graph[j][2]
for i in range(E): x =
graph[i][0] y =
graph[i][1] weight
= graph[i][2]
if dis[x] != maxsize and dis[x] + \ weight <
dis[y]: print("Graph contains negative weight
cycle")
print("Vertex Distance from Source")
OUTPUT:
RESULT:
EX.NO:14 IMPLEMENTATION OF MINIMUM SPANNING TREE
ALGORITHMS
AIM:
ALGORITHM:
Coding:
class Graph:
def init (self,
vertices): self.V =
vertices self.graph = []
def add_edge(self, u, v, w):
self.graph.append([u, v, w])
def find(self, parent, i): return
self.find(parent, parent[i])
def apply_union(self, parent, rank, x,
y): xroot = self.find(parent, x)
yroot = self.find(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_algo(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
+1X=
SELF.FIND(PARENT,
U) Y =
SELF.FIND(PARENT,
V) IF X != Y:
E = E + 1
RESULT.APPEND([U, V, W])
SELF.APPLY_UNION(PARENT, RANK, X, Y)
FOR U, V, WEIGHT IN RESULT:
PRINT("%D - %D: %D" % (U, V,
WEIGHT)) G = GRAPH(6)
G.ADD_EDGE(0, 1, 4)
G.ADD_EDGE(0, 2, 4)
G.ADD_EDGE(1, 2, 2)
G.ADD_EDGE(1, 0, 4)
G.ADD_EDGE(2, 0, 4)
G.ADD_EDGE(2, 1, 2)
G.ADD_EDGE(2, 3, 3)
G.ADD_EDGE(2, 5, 2)
G.ADD_EDGE(2, 4, 4)
G.ADD_EDGE(3, 2, 3)
G.ADD_EDGE(3, 4, 3)
G.ADD_EDGE(4, 2, 4)
G.ADD_EDGE(4, 3, 3)
G.ADD_EDGE(5, 2, 2)
G.ADD_EDGE(5, 4, 3)
G.KRUSKAL_ALGO()
OUTPUT:
RESULT:
EX NO: 15 FACTORIAL OF A NUMBER
DATE:
AIM:
ALGORITHM:
PROGRAM:
def recur_factorial(n):
if n ==1:
return n
else:
return n * recur_factorial
(n-1)
num =5
if num <0:
print(" factorial does not exist for negative numbers")
elif num ==0:
print("The factorial of 0 is 1")
else:
print("The factorial of", num, "is", recur_factorial(num))
OUTPUT:
RESULT:
