1.

IMPLEMENT SIMPLE ADTS AS PYTHON CLASSES

PROGRAM:

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:

STACK:

Initial stack

['a', 'b', 'c']

Elements poped from stack:

Stack after elements are poped:

[]

QUEUE:

Initial queue

['a', 'b', 'c']

Elements dequeued from queue

Queue after removing elements

[]

LIST:

Initial List:

[1, 2, 3, 4]

List after performing Extend Operation:

[1, 2, 3, 4, 8, 'Geeks', 'Always']

 2. RECURSIVE 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:

Fibonacci sequence:

13

21

34
 3. LIST ADT USING PYTHON ARRAYS

PROGRAM:

class node:

def __init__(self, data):

self.data = data

self.next = None

def add(data):

nn = node(0)

nn.data = data

nn.next = None

return nn

def printarray(a, n):

i=0

while i < n:

print(a[i], end=" ")

i =i+1

print()

def findlength(head):

cur = head

count = 0

while(cur!=None):

count=count+1

cur = cur.next

return count
 def convertarr(head):

len = node.findlength(head)

arr = []

index=0

cur = head

while(cur!=None):

arr.append(cur.data)

cur = cur.next

node.printarray(arr, len)

head= node(0)

head = node.add(6)

head.next = node.add(4)

head.next.next = node.add(3)

head.next.next.next = node.add(4)

node.convertarr(head)
OUTPUT:

[6 4 3 4]
 4. LINKED LIST IMPLEMENTATIONS OF LIST

PROGRAM:

my_list = []

print("Initial blank List:")

print(my_list)

my_list.append(1)

my_list.append(2)

my_list.append(4)

print("List after Addition of Three elements:")

print(my_list)

my_list.extend([1, 2, 3])

print("List after Addition of elements from 1-3:")

print(my_list)

my_list = [1, 2, 3, 4]

print("Initial List:")

print(my_list)

my_list.insert(0, 'Geeks')

my_list.insert(4, 12)

print("List after performing Insert Operation:")

print(my_list)

my_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

print("Initial List:")
print(my_list)

my_list.remove(5)

my_list.remove(6)

print("List after Removal of two elements:")

print(my_list)

my_list = my_list[4:]

print("List after Removing a range of elements:")

print(my_list)
OUTPUT:

Initial blank List:

[]

List after Addition of Three elements:

[1, 2, 4]

List after Addition of elements from 1-3:

[1, 2, 4, 1, 2, 3]

Initial List:

[1, 2, 3, 4]

List after performing Insert Operation:

['Geeks', 1, 2, 3, 12, 4]

Initial List:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

List after Removal of two elements:

[1, 2, 3, 4, 7, 8, 9, 10, 11, 12]

List after Removing a range of elements:

[7, 8, 9, 10, 11, 12]

 5. IMPLEMENTATION OF STACK AND QUEUE ADTS

PROGRAM:

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

STACK:

Initial stack

['a', 'b', 'c']

Elements poped from stack:

Stack after elements are poped:

[]

QUEUE:

Initial queue

['a', 'b', 'c']

Elements dequeued from queue

Queue after removing elements

[]
 6. A) APPLICATION OF LIST

PROGRAM:

def add(A, B, m, n):

size = max(m, n)

sum = [0 for i in range(size)]

for i in range(m):

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

print()

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("Second polynomial is")

printPoly(B, n)

sum = add(A, B, m, n)

size = max(m, n)

print("Sum polynomial is")

printPoly(sum, size)
OUTPUT:

First polynomial is

5 + 0x^ 1 + 10x^ 2 + 6x^ 3

Second polynomial is

1 + 2x^ 1 + 4x^ 2

Sum polynomial is

6 + 2x^ 1 + 14x^ 2 + 6x^ 3

 6. B) APPLICATION OF STACK

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:

abcd^e-fgh*+^*+i-
 6. C) APPLICATION OF QUEUE

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(processes[i]) + "\t\t" + str(bt[i]) + "\t\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]

findavgTime(processes, n, burst_time)
OUTPUT:

Processes Burst time Waiting time Turn around time

1 10 0 10

2 5 10 15

3 8 15 23

Average waiting time = 8.333333333333334

Average turn around time = 16.0

 7. A) LINEAR SEARCH

PROGRAM:

list_of_elements = [4, 3, 8, 9, 2, 7]

x = int(input("Enter number to search: "))

found = False

for i in range(len(list_of_elements)):

if list_of_elements[i] == x:

found = True

print(f"{x} found at {i}th position")

break

if not found:

print(f"{x} is not in the list")

OUTPUT:

Enter number to search: 4

4 found at 0th position

 7. B) BINARY SEARCH

PROGRAM:

def binary_search(item_list, item):

item_list.sort()

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:

False

True
 7. C) SELECTION SORT

PROGRAM:

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:

[13, 20, 31, 45, 49, 53, 62, 71, 77]

 7. D) INSERTION SORT

PROGRAM:

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:

[15, 22, 39, 41, 67, 73, 85, 86, 90]

 8. IMPLEMENTATION OF HASH TABLES

PROGRAM:

hashTable = [[] for _ in range(10)]

def checkPrime(n):

if n <= 1:

return False

for i in range(2, int(n**0.5) + 1):

if n % i == 0:

return False

return True

def getPrime(n):

if n % 2 == 0:

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)

for pair in hashTable[index]:

if pair[0] == key:
 pair[1] = data

return

hashTable[index].append([key, data])

def removeData(key):

index = hashFunction(key)

for i, pair in enumerate(hashTable[index]):

if pair[0] == key:

del hashTable[index][i]

return

insertData(123, "apple")

insertData(432, "mango")

insertData(213, "banana")

insertData(654, "guava")

print("Hash table after insertion:", hashTable)

removeData(123)

print("Hash table after deletion:", hashTable)

OUTPUT:

Hash table after insertion: [[], [], [[123, 'apple']], [[432, 'mango']], [[213, 'banana']], [[654, 'guava']], [], [], [], []]

Hash table after deletion: [[], [], [], [[432, 'mango']], [[213, 'banana']], [[654, 'guava']], [], [], [], []]
 9. A) TREE REPRESENTATION

PROGRAM:

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

 if self.right:

self.right.PrintTree()

root = Node(12)

root.insert(6)

root.insert(14)

root.insert(3)

root.PrintTree()
OUTPUT:

12

14
 9. B) TREE TRAVERSAL ALGORITHMS

PROGRAM:

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

printInorder(root.right)

def printPostorder(root):

if root:

printPostorder(root.left)

printPostorder(root.right)

print(root.val, end=" ")

def printPreorder(root):

if root:

print(root.val, end=" ")

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("Preorder 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:

Preorder traversal of binary tree is:

12453

Inorder traversal of binary tree is:

42513

Postorder traversal of binary tree is:

45231
 10. IMPLEMENTATION OF BINARY SEARCH TREES

PROGRAM:

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:

return str(self.data) + " is found"

def PrintTree(self):

if self.left:

self.left.PrintTree()

print(self.data, end=' ')

if self.right:

self.right.PrintTree()

root = Node(12)

root.insert(6)

root.insert(14)

root.insert(3)

print(root.findval(7))

print("Tree traversal:")

root.PrintTree()
OUTPUT:

7 Not Found

Tree traversal:

3 6 12 14
 11. IMPLEMENTATION OF HEAPS

PROGRAM:

import heapq

H = [21, 1, 45, 78, 3, 5]

heapq.heapify(H)

print("Heapified list:", H)

heapq.heappush(H, 8)

print("After pushing 8:", H)

heapq.heappop(H)

print("After popping the smallest element:", H)

OUTPUT:

Heapified list: [1, 3, 5, 78, 21, 45]

After pushing 8: [1, 3, 5, 78, 21, 45, 8]

After popping the smallest element: [3, 8, 5, 78, 21, 45]

 12. A) GRAPH REPRESENTATION

PROGRAM:

class Graph:

def __init__(self, gdict=None):

if gdict is None:

gdict = {}

self.gdict = gdict

def getVertices(self):

return list(self.gdict.keys())

def edges(self):

return self.find_edges()

def find_edges(self):

edge_list = []

for vertex in self.gdict:

for next_vertex in self.gdict[vertex]:

if {vertex, next_vertex} not in edge_list:

edge_list.append({vertex, next_vertex})

return edge_list

graph_elements = {

"a": ["b", "c"],

"b": ["a", "d"],

"c": ["a", "d"],

"d": ["e"],

"e": ["d"]
}

g = Graph(graph_elements)

print("Vertices of graph:", g.getVertices())

print("Edges of graph:", g.edges())

OUTPUT:

Vertices of graph: ['a', 'b', 'c', 'd', 'e']

Edges of graph: [{'b', 'a'}, {'c', 'a'}, {'b', 'd'}, {'c', 'd'}, {'e', 'd'}]
 12. B) GRAPH TRAVERSAL ALGIRITHMS

PROGRAM:

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)

DFS:

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)

if curr == dest:

print("FOUND:", curr)
 print(path)

break

for neigh in graph[curr]:

if neigh not in visited:

visited.append(neigh)

stack.append(neigh)

if dest not in path:

print("Not found")

print(path)
OUTPUT:

BFS:

Following is Breadth First Traversal:

0123

DFS:

FOUND: J

['A', 'D', 'F', 'G', 'I', 'J']

 13. IMPLEMENTATION OF SINGLE SOURCE
SHORTEST PATH ALGORITHM

PROGRAM:

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

u, v, w = graph[j]

if dis[u] != maxsize and dis[u] + w < dis[v]:

dis[v] = dis[u] + w

for i in range(E):

u, v, w = graph[i]

if dis[u] != maxsize and dis[u] + w < dis[v]:

print("Graph contains negative weight cycle")

return

print("Vertex Distance from Source")

for i in range(V):

print(f"{i}\t\t{dis[i]}")

if __name__ == "__main__":

V=5
E=8

graph = [

[0, 1, -1], [0, 2, 4],

[1, 2, 3], [1, 3, 2],

[1, 4, 2], [3, 2, 5],

[3, 1, 1], [4, 3, -3]

BellmanFord(graph, V, E, 0)
OUTPUT:

Vertex Distance from Source

0 0

1 -1

2 2

3 -2

4 1
 14. IMPLEMENTATION OF MINIMUM SPANNING
TREE ALGORITHMS

PROGRAM:

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

if parent[i] == i:

return 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

# Sort all edges based on weight

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 += 1

x = self.find(parent, u)

y = self.find(parent, v)

if x != y:

e += 1

result.append([u, v, w])

self.apply_union(parent, rank, x, y)

for u, v, weight in result:

print(f"{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:

1 - 2: 2

2 - 5: 2

2 - 3: 3

3 - 4: 3

0 - 1: 4