Ex.

No: 1
Implementation of simple ADTs as Python classes
Date:

AIM:

ALGORITHM:
1. Start
2. Create a class named student with data members rollno, name, course and member
function named display
3. Instantiate the class student with object s1 and s2
4. During instantiation pass the arguments for the data members through the constructor
5. Call display function to print the attributes for both objects s1 and s2
6. Stop

PROGRAM:
class student:
def init (self,rollno,name,course):
self.rollno = rollno
self.name = name
self.course = course
def display(self):

print("my Roll Number is "+str(self.rollno))

print("my Name is "+str(self.name))
print("my Course is "+str(self.course))
s1 = student(101,"John","AI&DS")
s1.display()
s2 = student(102,"Raj","CSBS")
s2.display()

RESULT:
 Ex. No: 2 (a) Implementation of Recursive algorithm for finding
Factorial of a number
Date:

AIM:

ALGORITHM:
1. Start
2. Pass the number as an argument to a recursive factorial function.
3. Define the base condition as the number to be lesser than or equal to 1 and return 1 if it
is.
4. Otherwise call the function recursively with the number minus 1 multiplied by the
number itself.
5. Then return the result and print the factorial of the number.
6. Stop

PROGRAM:
# Factorial of a number using recursion
def recur_factorial(n):
if n == 1:
return n
else:
return n*recur_factorial(n-1)
num = 7
# check if the number is negative
if num < 0:
print("Sorry, 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))

RESULT:
 Ex. No: 2 (b) Implementation of Recursive algorithm for generating
Fibonacci series
Date:

AIM:

ALGORITHM:
1. Firstly get the length of the Fibonacci series as input from the user and keep the variable.
2. Then send the length as parameter to a recursive method named recursive fibonacci ().
3. Then the function will check whether the length is lesser than or equal to 1.
4. Its length is less or equal to 1 then returns immediately.
5. If it is greater and not equal then it will make two adjoining recursive calls with the
argument as the (length-1) and (length-2) to the recursive fibonacci () function.
6. Then we call recursive function inside for loop which iterates length of the Fibonacci
series and print result.

PROGRAM:
# Recursive function
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 valid
if 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))

RESULT:
 Ex. No: 3
Implementation of List ADT using python Arrays
Date:

AIM:

ALGORITHM:
1. Start
2. Import the necessary package for implementation.
3. Define the array and specify the values.
4. Using the functions in the Array package that is insert; for inserting the values, remove
for deleting the specified index value, reverse function to reverse the array, and other
such functions in array package
5. Display the output of each functions.
6. Stop

PROGRAM:
# Importing Array module
import array
# Array creation
arr=array.array('i',[1,2,3])
print(arr)
# Appended a new item 4 at the end of the array
arr.append(4)
print(arr)
# inserted new element 5 at 2nd index position
arr.insert(2,5)
print(arr)
# removed the element at the end of the array
arr.pop()
print(arr)
# removed the item mentioned ar argument
arr.remove(2)
print(arr)
# Return the index position of the value mentioned as argument
print(arr.index(3))
# 5 is at index position 1
print(arr.index(5))
# used to reverse my array
arr.reverse()
print(arr)
RESULT:
 Ex. No: 4 (a)
Implementation of Singly Linked list
Date:

AIM:

ALGORITHM:
1. Start
2. Creation: Get the number of elements, and create the nodes having structures DATA,
LINK and store the element in Data field, link them together to form a linked list.
3. Insertion: Get the number to be inserted and create a new node store the value in DATA
field. And insert the node in the required position.
4. Deletion: Get the number to be deleted. Search the list from the beginning and locate
the node then delete the node.
5. Display: Display all the nodes in the list.
6. Stop

PROGRAM:
# Class created for node creation
class Node:
def init (self,data):
self.data = data
self.next = None
#Linked List Class to perform LL operations
class LL:
def init (self):
self.head = None

# Function to display the linked list

def display(self):
temp = self.head
if self.head is None: # if head is none it means list is empty
print ("List is Empty")
while temp:
print(temp.data,"--->",end=" ")
temp = temp.next
# Function to Insert node at the beginning of the LL
def insert_begining(self,data):
nb = Node(data)
nb.next = self.head
self.head = nb

# Function to Insert node at the end of the LL

def insert_end(self,data):
ne = Node(data)
temp = self.head
while temp.next:
temp = temp.next
temp.next = ne # make temp's next postion as new node

# Function to Insert node at a specific position in the middle of the LL

def insert_position(self,pos,data):
np = Node(data) # create new node
temp = self.head
for i in range(pos-1): #loop till the specified position-1; i value starts from 0
temp = temp.next
np.data = data
np.next = temp.next
temp.next = np

# Function to Delete node at the beginning of the LL

def delete_beginning(self):
temp = self.head
self.head = temp.next
temp.next = None

# Function to delete node at the end of the LL

def delete_end(self):
prev = self.head
temp = self.head.next
while temp.next is not None:
temp = temp.next
prev = prev.next
prev.next = None
 # Function to delete node at a specified position in the LL
def delete_position(self,pos):
prev = self.head
temp = self.head.next
for i in range (pos-1):
temp = temp.next
prev = prev.next
prev.next = temp.next

#Object created for LL class

obj = LL()
# node 1 created with data 10 created
n1 = Node(10)
obj.head = n1
# node 2 created with data 20 created
n2 = Node(20)
n1.next = n2
# node 3 with data 30 created
n3 = Node(30)
n2.next = n3

# display the linked list created

print("DISPLAY THE CREATED LIST..... ")
obj.display()

# Insertion of data 5 at the beginning of the list

obj.insert_begining(5)
print("AFTER INSERTING 5 AT THE BEGINNING ... ")
obj.display()

# Insert 40 at the end of the list

obj.insert_end(40)
print("INSERTING 40 AT THE END OF THE LIST")
obj.display()
# Insert data 25 at the 3rd position in the list
obj.insert_position(3,25)
print("INSERTING 25 AT THE MIDDLE OF THE LIST")
obj.display()

#function call for deletion at the beginning

obj.delete_beginning()
print("AFTER DELETING THE FIRST NODE 5 FROM THE LIST...")
obj.display()

# function call for deletion at the end of the LL

obj.delete_end()
print("AFTER DELETING THE LAST NODE 40 FROM THE LIST...")
obj.display()

# Function call for deletion at the location 1, where the index position of this LL is started
from 0
obj.delete_position(1)
print("AFTER DELETING MIDDLE NODE 25 FROM THE LIST...")
obj.display()

RESULT:
 Ex. No: 4 (b)
AIM: Implementation of Circularly Linked List
Date:

AIM:

ALGORITHM:
1. Define a Node class which represents a node in the list. It has two properties data and
next which will point to the next node.
2. Define another class for creating the circular linked list, and it has two nodes: head and
tail. It has two methods: add() and display() .
3. add() will add the node to the list:
i. It first checks whether the head is null, then it will insert the node as the
head.
ii. Both head and tail will point to the newly added node.
iii. If the head is not null, the new node will be the new tail, and the new tail
will point to the head as it is a circular linked list.
4. delete() will delete the mode from the list:
i. specify the position to be deleted if in case of middle element
ii. beginning: move the head pointer to the next element and change the next
address of tail to current head
iii. end: move tail to the before element and change next of tail to the head
5. display() will show all the nodes present in the list.
i. Define a new node 'n' that will point to the head.
ii. Print n.data till n will points to head
iii. n will point to the next node in the list in each iteration.

PROGRAM:
class Node:
def init (self, val):
self.value = val
self.next = None
class CSLL:
def init (self):
self.head = None
def add(self, val):
if self.empty() is True:
self.head = Node(val)
self.head.next = self.head
 print("Head value created")
return
opt = int(input(
"Enter 1 to add a Node at the beginning\nEnter 2 to add a Node at the end\nEnter 3 to
add a Node in the "
"middle::"))
if opt == 1:
a = Node(val)
a.next = self.head
n = self.head
while n.next is not self.head:
n = n.next
n.next = a
self.head = a
elif opt == 2:
i = self.head
while i.next is not self.head:
i = i.next
i.next = Node(val)
i.next.next = self.head
elif opt == 3:
pos = int(input("Enter the position ::"))
i=1
n = self.head
f = n.next
flag = 0
while f is not self.head:
if i == pos:
flag = 1
break
f = f.next
n = n.next
i=i+
1 if flag ==
1:
n.next = Node(val)
n.next.next = f
else:
print("Position not found")
def delete(self):
if self.empty() is True:
print("Linked List empty")
return
elif self.head.next is self.head:
self.head = None
return
 opt = int(input("Enter 1 to delete the beginning element\nEnter 2 to delete the last
element\nEnter 3 to "
"delete elements in between ::"))
if opt == 1:
n = self.head
while n.next is not self.head:
n = n.next
n.next = self.head.next
self.head = self.head.next
elif opt == 2:
n = self.head
while n.next.next is not self.head:
n = n.next
n.next = self.head
else:
op = int(input("Enter 1 to delete by position\nEnter 2 to delete by value ::"))
if op == 1:
pos = int(input("Enter the position ::"))
i=1
n = self.head
f = self.head.next
flag = 0
while f.next is not self.head:
if i == pos:
flag = 1
break
i= i+1
n = n.next
f = f.next
if flag == 1:
n.next = f.next
else:
print("Position not found")
return
else:
val = int(input("Enter the value you want to delete ::"))
n = self.head
f = self.head.next
flag = 0
while f.next is not self.head:
if f.value == val:
flag = 1
break
 f = f.next
n = n.next
if flag == 1: n.next = f.next
else:
print("Value not found")
return
def clear(self):
self.head = None
print("Linked List cleared")
def empty(self):
if self.head is None:
return True
else:
return False
def display(self):
if self.empty() is True:
print("Linked List empty")
return
print("THE LINKED LIST")
print(self.head.value, " <== HEAD")
n = self.head.next
while n is not self.head:
print(n.value)
n = n.next
print("Linked List ends")
obj = CSLL()
while True:
option = int(input("Enter 1 to add an element\nEnter 2 to delete an element\nEnter 3 to
clear the Linked "
"List\nEnter 4 to display the Linked List\nEnter 5 to exit ::"))
if option == 1:
value = int(input("Enter the value you want to add ::"))
obj.add(value)
continue
elif option == 2:
obj.delete()
continue
elif option == 3: obj.clear()
continue
elif option == 4:
obj.display()
continue
 elif option == 5:
print("Goodbye")
break
elif option == 6:
print(obj.empty())
else:
print("Wrong option")

RESULT:
 Ex. No: 4 (c)
Implementation of Doubly Linked List
Date:

AIM:

ALGORITHM:
1. Define a Node class which represents a node in the list. It will have three properties:
data, previous which will point to the previous node and next which will point to the
next node.
2. Define another class for creating a doubly linked list, and it has two nodes: head and
tail. Initially, head and tail will point to null.
3. Insertion occurs in three cases at the beginning, end and middle of the list
i. For insertion in the beginning, create a new node, make the next pointer
of the new node to point to the head and make the new node as present
head
ii. For insertion at the end, create a new node, make the previous pointer of
the new node to point to the tail and make new node as the tail
iii. For insertion at a specified position, traverse a pointer till the specified
position – 1 location and update the pointers.
4. Deletion as well occurs in three cases at the beginning, end and middle of the list

i. For deletion at the beginning, assign a new pointer to head named temp,
and move head to point to the next node, then make temp’s next pointer
as none
ii. For deletion at the end of the list, assign new variable temp to access the
last node that is tail , move tail to the previous node and then make
temp’s previous pointer as none
iii. For deletion at the middle of the list, move two pointers for traversing
till the position-1 and position+1 respectively and then update the
pointers.
5. display() will show all the nodes present in the list.
i. Define a new node 'temp' that will point to the head.
ii. Print temp.data till current points to null.
iii. Temp will point to the next node in the list in each iteration.

PROGRAM:
class Node:
def init (self,data):
self.data = data
self.prev = None
self.next = None
class DLL:
def init (self):
self.head = None
# Function to display the Doubly Linked list
def display(self):
if self.head is None:
print("Empty Doubly Linked List")
else:
temp = self.head
while temp:
print(temp.data,"--->",end=" ")
temp = temp.next
def insert_beginning(self,data):
n = Node (data) # create new node n
temp = self.head # Assign head to temp variable
temp.prev = n # set temp's previous field to new node n
n.next = temp # set new node's next to temp
self.head = n # Assign head to n
def insert_end(self,data):
n = Node(data) # create new node n
temp = self.head # Assign head to temp
while temp.next is not None: # loop till temp.next is not None
temp = temp.next # set temp to temp.next
temp.next = n # Assign temp's next to new node n
n.prev = temp # Assign temp to n's previous field
def insert_position(self,pos,data):
n = Node(data) # create node n
temp = self.head # Assign head to temp
for i in range(1,pos-1): # loop from 1 to the specified position-1
temp = temp.next # set temp.next as temp
n.prev = temp # Assign temp as n's previous field
n.next = temp.next # set temp's next as new node n's next
temp.next.prev = n # Assign new node n as previous of temp.next
temp.next = n # set n as temp's next field
def delete_beginning(self):
temp = self.head
self.head = temp.next
temp.next = None
self.head.prev = None
def delete_end(self):
temp = self.head.next
before = self.head
while temp.next is not None:
temp = temp.next
before = before.next
before.next = None
temp.prev = None
 def delete_position(self,pos):
temp = self.head.next
before = self.head
for i in range(1,pos-1):
temp = temp.next
before = before.next
before.next = temp.next
temp.next.prev = before
temp.next = None
temp.prev = None
obj = DLL() # create object for DLL class
n1 = Node(10) # create new node n1 with data 10
obj.head = n1 # set n1 as head
n2 = Node(20) # create new node n2 with data 20
n2.prev = n1 # set n2's previous field to n1
n1.next = n2 # set n1's next field to n2
n3 = Node(30) # create new node n3 with data 30
n3.prev = n2 # set n3's previous field as n2
n2.next = n3 # set n2's next field as n3
n4 = Node(40) # create new node n4 with data 40
n4.prev = n3 # set n4's previous field as n3
n3.next = n4 # set n3's next field as n4
print("Created doubly linked list...")
obj.display()
obj.insert_beginning(5)
print("After inserting 5 at the beginning of doubly linked list...")
obj.display()
obj.insert_end(50)
print("After inserting 50 at the end of doubly linked list...")
obj.display()
obj.insert_position(4,25)
print("After inserting 25 as 4th item of doubly linked list...")
obj.display()
obj.delete_beginning()
print("Deletion at the beginning...")
obj.display()
obj.delete_end()
print("Deletion at the end of doubly linked list...")
obj.display()
obj.delete_position(3)
print("Deleting the 3rd item from doubly linked list...") obj.display()
RESULT:
 Ex. No: 5 (a)
Implementation of Stack ADT using Array
Date:

AIM:

ALGORITHM:
1. Start
2. Initialize top = -1
3. Push operation increases top by one and writes pushed element to storage[top]
4. Pop operation checks that top is not equal to -1 and decreases top variable by 1
5. Display operation checks that top is not equal to -1 and returns storage[top]
6. Stop

PROGRAM:
class StackUsingArray:
def init (self):
self.stack = []
#Method to append the element in the stack at top position.
def push(self, element):
self.stack.append(element)
#Method to Pop last element from the top of the stack
def pop(self):
if(not self.isEmpty()):
lastElement = self.stack[-1] #Save the last element to return
del(self.stack[-1]) #Remove the last element
return lastElement
else:
return("Stack Already Empty")
#Method to check if stack is empty or not
def isEmpty(self):
return self.stack == []
def printStack(self):
print(self.stack)
#Main code
if name == " main ":
s = StackUsingArray()
print("*"*5+" Stack Using Array"+5*"*")
while(True):
el = int(input("1 for Push\n2 for Pop\n3 to check if it is Empty\n4 to print Stack\n5 to exit\n"))
 if(el == 1):
item = input("Enter Element to push in stack\n")
s.push(item)
if(el == 2):
print(s.pop())
if(el == 3):
print(s.isEmpty())
if(el == 4):
s.printStack()
if(el == 5):
break

RESULT:
 Ex. No: 5 (b)
Implementation of Stack ADT using Linked list
Date:

AIM:

ALGORITHM:
1. Start
2. Push operation inserts an element at the front.
3. Pop operation deletes an element at the front of the list
4. Display operation displays all the elements in the list.
5. Stop

PROGRAM:
class Node:
# Class to create nodes of linked list
# Constructor initializes node automatically
def init (self,data):
self.data = data
self.next = None
class Stack:
# head is default NULL
def init (self):
self.head = None
# Checks if stack is empty
def isempty(self):
if self.head == None:
return True
else:
return False
# Method to add data to the stack
# adds to the start of the stack
def push(self,data):
if self.head == None:
self.head=Node(data)
else:
newnode = Node(data)
newnode.next = self.head
self.head = newnode
# Remove element that is the current head (start of the stack)
def pop(self):
if self.isempty(): return None
 else:
# Removes the head node and makes
#the preceding one the new head
poppednode = self.head
self.head = self.head.next
poppednode.next = None
return poppednode.data
# Returns the head node data
def top(self):
if self.isempty():
return None
else:
return self.head.data
# Prints out the stack
def display(self):
iternode = self.head
if self.isempty():
print("Stack Underflow")
else:
while(iternode != None):
print(iternode.data,"->",end = " ")
iternode = iternode.next
return
# Driver code
MyStack = Stack()
MyStack.push(10)
MyStack.push(20)
MyStack.push(30)
MyStack.push(40)
# Display stack elements
MyStack.display()
# Print top element of stack
print("\nTop element is ",MyStack.top())
# Delete top elements of stack
MyStack.pop()
MyStack.pop()
# Display stack elements
MyStack.display()
# Print top element of stack
print("\nTop element is ", MyStack.top())

RESULT:
 Ex. No: 5 (c)
Implementation of Queue ADT using Array
Date:

AIM:

ALGORITHM:
1. Start
2. Initialize front=0; rear=-1.
3. Enqueue operation moves a rear by one position and inserts a element at the rear.
4. Dequeue operation deletes a element at the front of the list and moves the front by one
Position.
5. Display operation displays all the element in the list.
6. Stop
PROGRAM:
# Implement Queue using List(Functions)
q=[]
def Enqueue():
if len(q)==size: # check wether the stack is full or not
print("Queue is Full!!!!")
else:
element=input("Enter the element:")
q.append(element)
print(element,"is added to the Queue!")
def dequeue():
if not q:# or if len(stack)==0
print("Queue is Empty!!!")
else:
e=q.pop(0)
print("element removed!!:",e)
def display():
print(q)
size=int(input("Enter the size of Queue:"))
while True:
print("Select the Operation:1.Add 2.Delete 3. Display 4. Quit")
choice = int(input())
if choice==1:
Enqueue()
elif choice==2:
dequeue()
elif choice==3:
display()
elif choice==4:
break
 else:
print("Invalid Option!!!")

RESULT:
 Ex. No: 5 (d)
Implementation of Queue ADT using Linked list
Date:

AIM:

PROCEDURE:
1. Start
2. Enqueue operation inserts an element at the rear of the list.
3. Dequeue operation deletes an element at the front of the list.
4. Display operation display all the element in the list.
5. Stop

PROGRAM:
class Node:
def init (self,data):
self.data = data
self.next = None
class Queue:
def init (self):
self.head = None
def display(self):
temp = self.head
print('Queue is:[', end='')
while temp:
print(temp.data, end=", ")
temp = temp.next
print(']')
def enqueue(self, data):
if self.head is None:
self.head = Node(data)
else:
temp = self.head
while temp.next is not None:
temp = temp.next
temp.next = Node(data)
self.display()
def dequeue(self):
if self.head is None:
print('Queue is Empty')
self.display()
return None
 else:
data=self.head.data
self.head=self.head.next
self.display()
return data
def main():
Q = Queue()
print('1.enqueue\n2.dequeue\n3.exit')
while 1:
choice = input('Enter your option:')
if choice is '1':
d = int(input('Enter data:'))
Q.enqueue(d)
elif choice is '2':
print('Deleted element is:',Q.dequeue())
else:
break
if name == ' main ':
main()

RESULT:
 Ex. No: 6 (a)
Implement an application of Linked List using Python
Date:

AIM:

ALGORITHM:
1. Loop around all values of linked list and follow step 2& 3.
2. if the value of a node’s exponent. is greater copy this node to result node and head
towards the next node.
3. if the values of both node’s exponent is same add the coefficients and then copy the
added value with node to the result.
4. Print the resultant node.

PROGRAM:
# Add two polynomials using linked list
class Node :
def init (self, data, power) :
self.data = data
self.power = power
self.next = None
# Update node value
def updateRecord(self, data, power) :
self.data = data
self.power = power
class AddPolynomial :
def init (self) :
self.head = None
# Display given polynomial nodes
def display(self) :
if (self.head == None) :
print("Empty Polynomial ")
print(" ", end = "")
temp = self.head
while (temp != None)
: if (temp !=
self.head) :
print("+", temp.data, end = "")
else :
print(temp.data, end = "")
if (temp.power != 0) :
print("x^", temp.power, end = " ",sep = "")
 # Visit to next node
temp = temp.next
print(end = "\n")
# Add node with given data and power
def addNode(self, data, power) :
if (self.head == None) :
# Add first node
self.head = Node(data, power)
else :
node = None
temp = self.head
location = None
# Find the valid new node location
while (temp != None and temp.power >= power) :
location = temp
temp = temp.next
if (location != None and location.power == power) :
# When polynomial power already exists
# Then add current add to previous data
location.data = location.data + data
else :
node = Node(data, power)
if (location == None) :
# When add node in begining
node.next = self.head
self.head
= node else :
# When adding node in intermediate
# location or end location
node.next = location.next
location.next = node
# Add two polynomial
def addTwoPolynomials(self, other) :
# Define some useful variable
result = None
tail = None
node = None
# Get first node of polynomial
first = self.head
second = other.head
# Execute loop until when polynomial are exist
# And add two polynomial.
# Process takes O(n) time.
while (first != None or second != None) :
 # Create node with default value
node = Node(0, 0)
if (result == None) :
# When first resultant node
result = node
if (first != None and second != None) :
if (first.power == second.power) :
# When the polynomial node power are same
node.updateRecord(first.data + second.data, first.power)
first = first.next
second = second.next
elif (first.power > second.power) :
# When first polynomial power are larger
node.updateRecord(first.data,
first.power) first = first.next
else :
# When second polynomial power are larger
node.updateRecord(second.data, second.power)
second = second.next
elif (first != None) :
# When first polynomial are not empty
# Update the current node information
node.updateRecord(first.data, first.power)
first = first.next
else :
# When second polynomial are not empty
node.updateRecord(second.data, second.power)
second = second.next
if (tail == None) :
tail = node
else :
# Add new node at end of resultant polynomial
tail.next = node
tail = node
# return first node return result
def main() :
poly1 = AddPolynomial()
poly2 = AddPolynomial()
result = AddPolynomial()
# Add node in polynomial poly1
poly1.addNode(9, 3)
poly1.addNode(4, 2)
poly1.addNode(3, 0)
poly1.addNode(7, 1)
 poly1.addNode(3, 4)
# Add node in polynomial poly2
poly2.addNode(7, 3)
poly2.addNode(4, 0)
poly2.addNode(6, 1)
poly2.addNode(1, 2)
# Display Polynomial nodes
print("\n Polynomial A")
poly1.display()
print(" Polynomial B")
poly2.display()
result.head = poly1.addTwoPolynomials(poly2)
# Display calculated result
print(" Result")
result.display()
if name == " main ": main()

RESULT:
 Ex. No: 6 (b)
Implement an application of Stack ADT using Python
Date:

AIM:

ALGORITHM:

1. Scan the Infix Expression from left to right.

2. If the scanned character is an operand, append it with final Infix to Postfix string.
3. Else,
i. If the precedence order of the scanned(incoming) operator is greater than the
precedence order of the operator in the stack (or the stack is empty or the
stack contains a ‘(‘ or ‘[‘ or ‘{‘), push it on stack.
ii. Else, Pop all the operators from the stack which are greater than or equal to
in precedence than that of the scanned operator. After doing that Push the
scanned operator to the stack. (If you encounter parenthesis while popping
then stop there and push the scanned operator in the stack).
4. If the scanned character is an ‘(‘ or ‘[‘ or ‘{‘, push it to the stack.
5. If the scanned character is an ‘)’or ‘]’ or ‘}’, pop the stack and and output it until a ‘(‘
or ‘[‘ or ‘{‘ respectively is encountered, and discard both the parenthesis.
6. Repeat steps 2-6 until infix expression is scanned.
7. Print the output
8. Pop and output from the stack until it is not empty.

PROGRAM:
Operators = set(['+', '-', '*', '/', '(', ')', '^']) # collection of Operators
Priority = {'+':1, '-':1, '*':2, '/':2, '^':3} # dictionary having priorities of Operators
def infixToPostfix(expression):
stack = [] # initialization of empty stack
output = ‘’
for character in expression:
if character not in Operators: # if an operand append in postfix expression
output+= character
elif character=='(': # else Operators push onto stack
stack.append('(')
elif character==')':
while stack and stack[-1]!= '(':
output+=stack.pop()
stack.pop()
else:
while stack and stack[-1]!='(' and Priority[character]<=Priority[stack[-1]]:
output+=stack.pop()
stack.append(character)
 while stack:
output+=stack.pop()
return output
expression = input('Enter infix expression ')
print('infix notation: ',expression)
print('postfix notation: ',infixToPostfix(expression))

RESULT:
 Ex. No: 6 (c)
Implement an application of Queue ADT using Python
Date:

AIM:

ALGORITHM:
1. Use multiprocessing.queue to use a queue for multiprocessing
2. Call multiprocessing.Queue() to create a Queue to share between multiple
processes.
3. Call multiprocessing.Process(target=function, args=[queue]) to create a process to
execute function with arguments to the queue created in the previous step.
4. Set Process.daemon to True to run the process in the background.
5. Call Process.start() to start the process.
6. Call Process.join() to block execution until the Process has finished executing.

PROGRAM:
import multiprocessing
def consumer(queue):
while True:
msg = queue.get()
if (msg == 'DONE'):
break
def producer(count, queue):
for i in range(count):
queue.put(i)
queue.put('DONE')
queue = multiprocessing.Queue()
consumer_process = multiprocessing.Process(target=consumer, args=[queue])
consumer_process.daemon = True
consumer_process.start()
count = 10**4
producer(count, queue) #Send data to the queue
consumer_process.join()
print("Sent {0} numbers to Queue...".format(count))

RESULT:
 Ex. No: 7 (a)
Implementation of Bubble sort using Python
Date:

AIM:

ALGORITHM:
1. Get the total number of elements. Get the total number of items in the given array
2. Determine the number of outer passes (n – 1) to be done. Its length is array minus one
3. Perform inner passes (n – 1) times for outer pass 1. Get the first element value and
compare it with the second value. If the second value is less than the first value, then
swap the positions
4. Repeat step 3 passes until you reach the outer pass (n – 1). Get the next element in the
list then repeat the process that was performed in step 3 until all the values have been
placed in their correct ascending order.
5. Return the result when all passes have been done. Return the results of the sorted array

PROGRAM:
def bubbleSort(arr):
n = len(arr)
# Traverse through all array elements
for i in range(n-1):
# range(n) also work but outer loop will
# repeat one time more than needed.
# Last i elements are already in place
for j in range(0, n-i-1):
# traverse the array from 0 to n-i-1
# Swap if the element found is greater
# than the next element
if arr[j] > arr[j + 1] :
arr[j], arr[j + 1] = arr[j + 1], arr[j]
# Driver code to test above
arr = [64, 134, 25, 12, 56, 10, 90]
bubbleSort(arr)
print ("Sorted array is:")
for i in range(len(arr)):
print ("% d" % arr[i],end=" ")

RESULT:
 Ex. No: 7 (b)
Implementation of Selection sort using Python
Date:

AIM:

ALGORITHM:
1. Get the value of n which is the total size of the array
2. Partition the list into sorted and unsorted sections. The sorted section is initially empty
while the unsorted section contains the entire list
3. Pick the minimum value from the unpartitioned section and placed it into the sorted
section.
4. Repeat the process (n – 1) times until all of the elements in the list have been sorted.
5. Return the sorted list and print it.

PROGRAM:
def selectionSort( itemsList ):
n = len( itemsList )
for i in range( n - 1 ):
minValueIndex = i
for j in range( i + 1, n ):
if itemsList[j] < itemsList[minValueIndex] :
minValueIndex = j
if minValueIndex != i :
temp = itemsList[i]
itemsList[i] = itemsList[minValueIndex]
itemsList[minValueIndex] = temp
return itemsList
el = [29,6,37,45,5]
print("Unsorted list... ")
print(el)
print("Sorted list")
print(selectionSort(el))

RESULT:
 Ex. No: 7 (c)
Implementation of Insertion sort using Python
Date:

AIM:

ALGORITHM:
1. Create a function insetion_sort()
2. Declare a list.
3. Mark the first element as sorted
4. Initialize for loop
5. Iterate each element and extract the locations.
6. Move sorted element right by 1
7. break the loop and insert the key here
8. Print the sorted Array

PROGRAM:
def insertion_sort(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= j- 1
# Place key at after the element just smaller than it.
arr[j + 1] = key
arr = [9, 8, 6, 7, 1]
print("Unsorted Array:", arr)
insertion_sort(arr)
print('Sorted Array: ', arr)

RESULT:
 Ex. No: 7 (d)
Implementation of Merge sort using Python
Date:

AIM:

ALGORITHM:
1. Store the length of the list
2. List with length less than is already sorted
3. Identify the list midpoint and partition the list into a left_partition and a
right_partition
4. To ensure all partitions are broken down into their individual components, the
merge_sort function is called and a partitioned portion of the list is passed as a
parameter
5. The merge_sort function returns a list composed of a sorted left and right partition.
6. Takes in two lists and returns a sorted list made up of the content within the two lists
7. Initialize an empty list output that will be populated with sorted elements. Initialize
two variables i and j which are used pointers when iterating through the lists.
8. Executes the while loop if both pointers i and j are less than the length of the left and
right lists
9. Compare the elements at every position of both lists during each iteration
10. Move pointer to the right
11. The remnant elements are picked from the current pointer value to the end of the
respective list

PROGRAM:
def merge_sort(list):
list_length = len(list)
if list_length == 1:
return list
mid_point = list_length // 2
left_partition = merge_sort(list[:mid_point])
right_partition = merge_sort(list[mid_point:])
return merge(left_partition, right_partition)
def merge(left, right):
output = []
i= j=0
while i < len(left) and j < len(right):
if left[i] < right[j]:
 output.append(left[i])
i += 1
else:
output.append(right[j])
j += 1
output.extend(left[i:])
output.extend(right[j:])
return output
def run_merge_sort():
unsorted_list = [4, 7, 2, 61, 1, 1, 61, 44, 10, 33, 15, 7, 23]
print("Unsorted list...",unsorted_list)
sorted_list = merge_sort(unsorted_list)
print("Sorted list...",sorted_list)
run_merge_sort()

RESULT:
 Ex. No: 7 (e)
Implementation of Quick sort using Python
Date:

AIM:

ALGORITHM:
1. Create a function partition()
2. Pass three parameters arr, low, high
3. Select rightmost element as pivot
4. declare pointer for greater element
5. traverse through all elements and compare them with pivot
6. If the smaller element is found swap them with pivot
7. Return the index position
8. Create a function QuickSort()
9. Pass three parameters arr, low, high
10. Find the pivot element
11. Do Recursive call on the left pivot and right pivot
12. The array is now sorted
13. Print the sorted array

PROGRAM:
def partition(arr, low, high):
i = (low-1) # index of smaller element
pivot = arr[high] # pivot
for j in range(low, high):
# If current element is smaller than or
# equal to pivot
if arr[j] <= pivot:
# increment index of smaller element
i = i+1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return (i+1)
# The main function that implements QuickSort
# arr[] --> Array to be sorted,
# low --> Starting index,
# high --> Ending index
# Function to do Quick sort
def quickSort(arr, low, high):
if len(arr) == 1:
return arr
if low < high:
# pi is partitioning index, arr[p] is now
# at right place
pi = partition(arr, low, high)
# Separately sort elements before
# partition and after partition
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
# Driver code to test above
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
print("Input arrat: ",arr)
quickSort(arr, 0, n-1)
print("Sorted array is:")
for i in range(n):
print("%d" % arr[i])

RESULT:
 Ex. No: 7 (f)
Implementation of Linear Search using Python
Date:

AIM:

ALGORITHM:
1. Create a function linear_search()
2. Declare three parameters array, length of the array, and number to be found.
3. Initialize for loop
4. Iterate each element and compare the key value.
5. If the element is present return index
6. Else return not present

PROGRAM:
def linear_search(arr, a, b):
# Going through array
for i in range(0, a):
if (arr[i] == b):
return i
return -1
arr = [9, 7, 5, 3, 1]

print("The array given is ", arr)

b=5
print("Element to be found is ", b)
a = len(arr)
index = linear_search(arr, a, b)
if(index == -1):
print("Element is not in the list")
else:
print("Index of the element is: ", index)

RESULT:
 Ex. No: 7 (g)
Implementation of Binary search using Python
Date:

AIM:

ALGORITHM:
1. Create a function binary_search() which accepts 4 parameters(array, low, high, a).
2. Declare two variables to store the highest and the lowest values in the list.
3. Then Follow step 4 until the lowest and highest meet each other:
4. mid = (low + high)/2 if (a == arr[mid]) return mid else if (a > arr[mid])
a is on the right side low = mid + 1 else
a is on the left side high = mid - 1
5. Intialize the array and the element to be found
6. Print the resulting position if the element is found else print Not found.

PROGRAM:
def binary_search(arr, a, low, high):
# Repeat until low and high meet each other
while low <= high:
mid = low + (high - low)//2
if arr[mid] == a:
return mid
elif array[mid] < a:
low = mid + 1
else:
high = mid - 1
return -1
arr = [1, 2, 3, 4, 5, 6, 7]
a=4
#printing the array
print("The given array is", arr)
#printing element to be found
print("Element to be found is ", a)
index = binary_search(arr, a, 0, len(arr)-1)
if index != -1:
print("The Index of the element is " + str(index))
else:
print("Element Not found")

RESULT:
 Ex. No: 8 (a)
Implementation of graph traversal using Breadth First
Date: Search

AIM:

ALGORITHM:

1. Initialize an empty set visited to keep track of visited vertices.

2. Initialize a queue and add the starting vertex to it.
3. While the queue is not empty:
➢ Dequeue a vertex from the front of the queue.
➢ If the vertex has not been visited, mark it as visited and append it to the bfs_order list.
➢ Enqueue all unvisited adjacent vertices of the current vertex.
4. Return the bfs_order list, which contains the BFS traversal of the graph.

PROGRAM:
def bfs(graph, start):
visited = set()
queue = deque([start])
bfs_order = []

while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
bfs_order.append(vertex)
queue.extend(graph[vertex] - visited)

return bfs_order

# Example usage:
graph = {
'A': {'B', 'C'},
'B': {'A', 'D', 'E'},
'C': {'A', 'F'},
'D': {'B'},
'E': {'B', 'F'},
'F': {'C', 'E'}
}
print("BFS:", bfs(graph, 'A'))

RESULT:
 Ex. No: 8 (b)
Implementation of graph traversal using Depth First
Date: Search

AIM:

ALGORITHM:

1. Initialize a set visited to keep track of visited vertices (optional, passed as a parameter).
2. Mark the current vertex as visited and add it to the dfs_order list.
3. Recursively visit each unvisited adjacent vertex.
4. Return the dfs_order list, which contains the DFS traversal of the graph.

PROGRAM:

def dfs(graph, start, visited=None):

if visited is None:
visited = set()
visited.add(start)
dfs_order = [start]

for next_vertex in graph[start] - visited:

dfs_order.extend(dfs(graph, next_vertex, visited))

return dfs_order

# Example usage:
graph = {
'A': {'B', 'C'},
'B': {'A', 'D', 'E'},
'C': {'A', 'F'},
'D': {'B'},
'E': {'B', 'F'},
'F': {'C', 'E'}
}

print("DFS:", dfs(graph, 'A'))

RESULT:
 Ex. No: 8 (c)
Finding the shortest paths to other vertices using Dijkstra’s
Date: algorithm

AIM:

ALGORITHM:

1. Initialize a dictionary distances with all vertices set to infinity except the starting vertex,
which is set to 0.
2. Create a priority queue and add the starting vertex with a distance of 0.
3. While the priority queue is not empty:

➢ Dequeue the vertex with the smallest distance.

➢ For each adjacent vertex, calculate the new distance.
➢ If the new distance is smaller than the currently known distance, update it and push the
adjacent vertex into the priority queue.

4. Return the distances dictionary, which contains the shortest paths from the start vertex to all
other vertices.

PROGRAM:
def dijkstra(graph, start):
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
priority_queue = [(0, start)]

while priority_queue:
current_distance, current_vertex = heapq.heappop(priority_queue)

if current_distance > distances[current_vertex]:

continue

for neighbor, weight in graph[current_vertex].items():

distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))

return distances
# Example usage:
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}

print("Dijkstra's Shortest
Paths:", dijkstra(graph, 'A')

RESULT:
 Ex. No: 8 (d)
Finding the minimum cost spanning tree of a given
Date: undirected graph using Prim’s algorithm

AIM:

ALGORITHM:

1. Initialize an empty list mst for the MST edges and a set visited for visited vertices.
2. Initialize a priority queue and add the starting vertex with a weight of 0.
3. While the priority queue is not empty:

➢ Extract the edge with the minimum weight.

➢ If the vertex at the end of the edge is not visited, add it to the MST and mark it as
visited.
➢ Push all adjacent edges to the priority queue.

4. Return the MST edges and the total cost of the MST.

PROGRAM:
def prim(graph, start):
mst = []
visited = set()
edges = [(0, start, None)]
total_cost = 0

while edges:
weight, vertex, parent = heapq.heappop(edges)
if vertex not in visited:
visited.add(vertex)
if parent is not None:
mst.append((parent, vertex, weight))
total_cost += weight

for next_vertex, next_weight in graph[vertex].items():

if next_vertex not in visited:
heapq.heappush(edges, (next_weight, next_vertex, vertex))

return mst, total_cost

# Example usage:
graph = {
'A': {'B': 1, 'C': 3},
'B': {'A': 1, 'C': 1, 'D': 6},
'C': {'A': 3, 'B': 1, 'D': 2},
'D': {'B': 6, 'C': 2}
}

mst, cost = prim(graph, 'A')

print("Prim's MST:", mst)
print("Total cost:", cost)

RESULT:
 Ex. No: 8 (e)
Finding the minimum cost spanning tree of a given
Date: undirected graph using Kruskal’s algorithm

AIM:

ALGORITHM:

1. Initialize a disjoint-set data structure for each vertex.

2. Create a list of all edges and sort them by weight.
3. Initialize an empty list mst for the MST edges and a variable total_cost for the total weight.
4. For each edge in the sorted list:

➢ If the edge does not form a cycle (i.e., its vertices belong to different sets in the
disjoint-set), add it to the MST and union the sets.

5. Return the MST edges and the total cost of the MST.

PROGRAM:
def init (self, vertices):
self.parent = {vertex: vertex for vertex in vertices}
self.rank = {vertex: 0 for vertex in vertices}

def find(self, vertex):

if self.parent[vertex] != vertex:
self.parent[vertex] = self.find(self.parent[vertex])
return self.parent[vertex]

def union(self, vertex1, vertex2):

root1 = self.find(vertex1)
root2 = self.find(vertex2)

if root1 != root2:
if self.rank[root1] > self.rank[root2]:
self.parent[root2] = root1
elif self.rank[root1] < self.rank[root2]:
self.parent[root1] = root2
else:
self.parent[root2] = root1
self.rank[root1] += 1
def kruskal(graph):
edges = []
for vertex in graph:
for neighbor, weight in graph[vertex].items():
edges.append((weight, vertex, neighbor))
edges.sort()

disjoint_set = DisjointSet(graph.keys())
mst = []
total_cost = 0

for weight, vertex1, vertex2 in edges:

if disjoint_set.find(vertex1) != disjoint_set.find(vertex2):
disjoint_set.union(vertex1, vertex2)
mst.append((vertex1, vertex2, weight))
total_cost += weight

return mst, total_cost

# Example usage:
graph = {
'A': {'B': 1, 'C': 3},
'B': {'A': 1, 'C': 1, 'D': 6},
'C': {'A': 3, 'B': 1, 'D': 2},
'D': {'B': 6, 'C': 2}
}

mst, cost = kruskal(graph)

print("Kruskal's MST:", mst)
print("Total cost:", cost)

RESULT:
 Ex. No: 9
Implementation of N Queens problem using Backtracking
Date:

AIM:

ALGORITHM:

1. Initialize an N×N board filled with 0s (representing empty cells).

2. Define a function is_safe to check if placing a queen on a given cell is safe.
3. Define a recursive function solve_nqueens to attempt to place queens column by column:

➢ If all queens are placed, return true.

➢ For each row in the current column, check if placing a queen there is safe.
➢ If safe, place the queen and recursively attempt to place the next queen.
➢ If placing the next queen fails, backtrack by removing the queen and trying the next
row.

4. If a solution is found, print the board. Otherwise, indicate that no solution exists.

PROGRAM:

def is_safe(board, row, col, n):

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), range(col, -1, -1)):

if board[i][j] == 1:
return False

return True

def solve_nqueens(board, col, n):

if col >= n:
return True

for i in range(n):
if is_safe(board, i, col, n):
board[i][col] = 1
if solve_nqueens(board, col + 1, n):
return True
board[i][col] = 0
return False

def print_board(board):
for row in board:
print(" ".join('Q' if x == 1 else '.' for x in row))

def n_queens(n):
board = [[0] * n for _ in range(n)]
if solve_nqueens(board, 0, n):
print_board(board)
else:
print("No solution exists")

# Example usage:
n_queens(4)

RESULT:
 Ex. No: 10
Implementation of randomized algorithms for finding the
Date: kth smallest number

AIM:

ALGORITHM:

1. Define a function randomized_partition to randomly choose a pivot element, partition the

array around it, and return the pivot's index.
2. Define a recursive function randomized_select:

➢ If the array has one element, return it.

➢ Partition the array using randomized_partition.
➢ If the pivot index matches k, return the pivot element.
➢ If k is less than the number of elements to the left of the pivot, recursively search the
left part of the array.
➢ Otherwise, search the right part of the array.

3. Call the randomized_select function with the entire array, starting and ending indices, and k
to get the k-th smallest element.

PROGRAM:

def randomized_partition(arr, low, high):

pivot_index = random.randint(low, high)
arr[pivot_index], arr[high] = arr[high], arr[pivot_index]
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1

def randomized_select(arr, low, high, k):

if low == high:
return arr[low]

pivot_index = randomized_partition(arr, low, high)

num_elements = pivot_index - low + 1
if num_elements == k:
return arr[pivot_index]
elif k < num_elements:
return randomized_select(arr, low, pivot_index - 1, k)
else:
return randomized_select(arr, pivot_index + 1, high, k - num_elements)

def find_kth_smallest(arr, k):

if k < 1 or k > len(arr):
raise ValueError("k is out of bounds.")
return randomized_select(arr, 0, len(arr) - 1, k)

# Example usage:
arr = [7, 10, 4, 3, 20, 15]
k=3
print(f"The {k}-th smallest element is {find_kth_smallest(arr, k)}")

RESULT: