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
[Link] IMPLEMENT SIMPLE ADTS AS PYTHON CLASSES
AIM:
ALGORITHM:
POGRAM :
Stack: stack = []
[Link]('a')
[Link]('b')
[Link]('c')
print('Initial
stack') print(stack)
print('\nElements poped from
stack:') print([Link]())
print([Link]()) print([Link]())
print('\nStack after elements are poped:') print(stack)
Queue: queue = []
[Link]('a')
[Link]('b')
[Link]('c')
print("Initial
queue") print(queue)
print("\nElements dequeued from
queue") print([Link](0))
print([Link](0)) print([Link](0))
print("\nQueue after removing elements") print(queue)
List:
List = [1,2,3,4]
print("Initial List: ")
print(List)
[Link]([8, 'Geeks', 'Always'])
print("\nList after performing Extend Operation: ") print(List)
OUTPUT:
RESULT:
[Link] 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:
[Link] IMPLEMENT LIST ADT USING PYTHON ARRAYS
AIM:
ALGORITHM:
index=0 cur=head
while(cur!=None): [Link]([Link]) cur=[Link]
printarray(arr, len) head=node(0) head=add(6)
[Link] = add(4) [Link] = add(3) [Link] = add(4) convertarr(head)
Output:
RESULT:
[Link] LINKED LIST IMPLEMENTATIONS OF LIST
AIM:
ALGORITHM:
PROGRAM:
List = [1,2,3,4]
print("Initial List: ")
print(List)
[Link]([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)
[Link](3, 12)
[Link](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)
[Link](5)
[Link](6) print("\nList after Removal of
two elements: ") print(List) for i in
range(1, 5):
[Link](i) print("\nList after Removing a
range of elements: ") print(List)
List = [['Geeks', 'For'] , ['Geeks']] print("\nMulti-
Dimensional List: ")
print(List)
OUTPUT:
RESULT:
[Link] IMPLEMENTATION OF STACK AND QUEUE ADTS
AIM:
ALGORITHM:
PROGRAM:
stack = []
[Link]('a
')
[Link]('b
')
[Link]('c
') print('Initial
stack')
print(stack)
print('\nElements poped from
stack:') print([Link]())
print([Link]())
print([Link]())
print('\nStack after elements are poped:')
print(stack)
Queue: queue =
[]
[Link]('a')
[Link]('b')
[Link]('c')
print("Initial
queue")
print(queue)
print("\nElements dequeued from
queue") print([Link](0))
print([Link](0))
print([Link](0))
print("\nQueue after removing elements")
print(queue)
OUTPUT:
RESULT:
[Link]: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:
[Link]:6B APPLICATION OF STACK
AIM:
ALGORITHM:
PROGRAM:
class Conversion:
def init (self,
capacity): [Link] = -1
[Link] = capacity
[Link] = [] [Link] = [] [Link]
= {'+':1, '-':1, '*':2, '/':2, '^':3}
def isEmpty(self): return True if [Link]
== -1 else False
def peek(self): return
[Link][-1]
def pop(self):
if not [Link]():
[Link] -= 1 return
[Link]()
else: return
"$"
def push(self, op):
[Link] += 1
[Link](op)
def isOperand(self, ch):
return [Link]()
def notGreater(self, i):
try:
a = [Link][i] b =
[Link][[Link]()] return
True if a <= b else False
except KeyError:
return False
def infixToPostfix(self, exp):
for i in exp:
if [Link](i):
[Link](i)
elif i == '(':
[Link](i)
elif i == ')':
while( (not [Link]()) and [Link]() !=
'('):
a = [Link]() [Link](a)
if (not [Link]() and [Link]() !=
'('): return -1 else:
[Link]()
else:
while(not [Link]() and [Link](i)):
[Link]([Link]()) [Link](i)
while not [Link]():
[Link]([Link]())
print "".join([Link])
exp = "a+b*(c^d-e)^(f+g*h)-i"
obj = Conversion(len(exp))
[Link](exp)
OUTPUT:
RESULT:
[Link]: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:
[Link] 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
[Link]: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:
[Link]: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:
[Link]: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:
[Link] 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:
[Link]:9A TREE REPRESNTATION
AIM:
ALGORITHM:
CODING:
class Node:
def init (self, data): [Link] =
None [Link] = None
[Link] = data
def insert(self, data): if [Link]:
if data < [Link]:
if [Link] is None:
[Link] = Node(data)
else: [Link](data)
elif data > [Link]:
if [Link] is None:
[Link] = Node(data)
else:
[Link](data)
else:
[Link] = data
def PrintTree(self):
if [Link]:
[Link]()
print( [Link]), if [Link]:
[Link]()
root = Node(12) [Link](6)
[Link](14) [Link](3)
OUTPUT:
RESULT:
[Link]:9B TREE TRAVERSAL ALGORITHMS
AIM:
ALGORITHM:
Coding:
class Node:
def init (self,key): [Link] = None
[Link] = None [Link] = key
def printInorder(root):
if root:
printInorder([Link]) print([Link]),
printInorder([Link])
def printPostorder(root):
if root:
printPostorder([Link])
printPostorder([Link]) print([Link]),
def printPreorder(root):
if root: print([Link]),
printPreorder([Link])
printPreorder([Link])
root = Node(1) [Link]
= Node(2) [Link]
= Node(3)
[Link] = Node(4)
[Link] = 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:
[Link] IMPLEMENTATION OF BINARY SEARCH TREE
AIM:
ALGORITHM:
Coding:
class Node:
def init (self,
data): [Link] =
None [Link] =
None [Link] =
data
def insert(self, data): if
[Link]:
if data < [Link]: if
[Link] is None:
[Link] = Node(data)
else:
[Link](data)
elif data > [Link]: if
[Link] is None:
[Link] =
Node(data) else:
[Link](data) else:
[Link] = data
def findval(self, lkpval):
if lkpval < [Link]:
if [Link] is None:
return str(lkpval)+" Not Found"
return [Link](lkpval)
elif lkpval > [Link]:
if [Link] is None:
return str(lkpval)+" Not Found"
return [Link](lkpval)
else:
print(str([Link]) + ' is found')
def PrintTree(self):
if [Link]:
[Link]()
print( [Link]), if
[Link]:
[Link]()
root = Node(12)
[Link](6)
[Link](14)
[Link](3)
print([Link](7))
OUTPUT:
RESULT:
[Link] IMPLEMENTATION OF HEAPS
AIM:
ALGORITHM:
CODING:
import heapq H =
[21,1,45,78,3,5]
[Link](H)
print(H)
[Link](H,8)
print(H) [Link](H)
print(H)
OUTPUT:
RESULT:
[Link]:12A GRAPH REPRESENTATION
AIM:
ALGORITHM:
Graph Representation Coding:
class graph:
def init (self,gdict=None):
if gdict is None: gdict
= []
[Link] = gdict
def getVertices(self):
return list([Link]())
graph_elements = { "a" : ["b","c"],
"b" : ["a", "d"],
"c" : ["a", "d"],
"d" : ["e"],
"e" : ["d"]
}
g = graph(graph_elements)
print([Link]()) class
graph:
def init (self,gdict=None):
if gdict is None: gdict
= {}
[Link] = gdict
def edges(self):
return [Link]()
def findedges(self):
edgename = [] for
vrtx in [Link]:
for nxtvrtx in [Link][vrtx]:
if {nxtvrtx, vrtx} not in edgename:
[Link]({vrtx, nxtvrtx}) return
edgename
graph_elements = { "a" : ["b","c"],
"b" : ["a", "d"],
"c" : ["a", "d"],
"d" : ["e"],
"e" : ["d"]
}
g = graph(graph_elements)
print([Link]())
OUTPUT:
RESULT:
[Link]:12B GRAPH TRAVERSAL ALGORITHMS
AIM:
ALGORITHM:
Coding:
BFS import collections def bfs(graph, root): visited, queue = set(),
[Link]([root]) [Link](root) while queue: vertex =
[Link]() print(str(vertex) + " ", end="") for neighbour in
graph[vertex]:
if neighbour not in visited: [Link](neighbour)
[Link](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 = []
[Link](start)
[Link](start) while
stack: curr = [Link]()
[Link](curr) for neigh
in graph[curr]:
if neigh not in visited:
[Link](neigh)
[Link](neigh) if
neigh == dest :
print("FOUND:", neigh)
print(path) [Link](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:
[Link] IMPLEMENTATION OF MINIMUM SPANNING TREE
ALGORITHMS
AIM:
ALGORITHM:
Coding:
class Graph:
def init (self,
vertices): self.V =
vertices [Link] = []
def add_edge(self, u, v, w):
[Link]([u, v, w])
def find(self, parent, i): return
[Link](parent, parent[i])
def apply_union(self, parent, rank, x,
y): xroot = [Link](parent, x)
yroot = [Link](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
[Link] = sorted([Link], key=lambda item: item[2])
parent = [] rank = [] for node in range(self.V):
[Link](node) [Link](0)
WHILE E < SELF.V - 1:
U, V, W =
[Link][I] I = I
+1X=
[Link](PARENT,
U) Y =
[Link](PARENT,
V) IF X != Y:
E = E + 1
[Link]([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: