EXP NO:1

DATE: IMPLEMENT SIMPLE ADTS AS PYTHON CLASSES

Aim: To Impliment simple adts as python classes.

Algorithm:
1. Start the program
2. Create classes of ADT
3. Access the classes
4. Print the statement
5. Stop the program

Program:

# Python example to show the working of multiple

# inheritance

class Base1(object):
def __init__(self):
self.str1 = "Geek1"
print("Base1")

class Base2(object):
def __init__(self):
self.str2 = "Geek2"
print("Base2")
class Derived(Base1, Base2):
def __init__(self):

# Calling constructors of Base1

# and Base2 classes
Base1.__init__(self)
Base2.__init__(self)
print("Derived")

def printStrs(self):
print(self.str1, self.str2)
ob = Derived()
ob.printStrs()
OUTPUT

Base1
Base2
Derived
b1 b2

=== Code Execution Successful ===

RESULT:

Thus the Implement simple ADTs as Python classes demonstrated successfully.

EXP NO: 02

DATE: Impliment Recursive algorithm in Python

Aim: To Impliment Recursive algorithm using python program

Algorithm:

1. Initialize the algorithm. ...

2. Check to see whether the current value(s) being processed match the base case. ...
3. Redefine the answer in terms of a smaller or simpler sub-problem or sub-problems.
4. Run the algorithm on the sub-problem.
5. Combine the results in the formulation of the answer.

Program:

# Program to print factorial of a number

# recursively.

# Recursive function
def recursive_factorial(n):
if n == 1:
return n
else:
return n * recursive_factorial(n-1)

# user input
num = 6

# check if the input is valid or not

if num < 0:
print("Invalid input ! Please enter a positive number.")
elif num == 0:
print("Factorial of number 0 is 1")
else:
print("Factorial of number", num, "=", recursive_factorial(num))
OUTPUT

Factorial of number 6 = 720

=== Code Execution Successful ===

RESULT:
Thus the Implement recursive algorithms using Python program demonstrated sucessfuly
EXPNO:3

DATE: Impliment List ADT using python Arrays

Aim: To Impliment List ADT using python Arrays.

Algorithm:

1. The data is generally stored in key sequence in a list which has a head structure consisting
of count, pointers and address of compare function needed to compare the data in the list.
2. The data node contains the pointer to a data structure and a self-referential pointer which
points to the next node in the list.
3. The List ADT Functions is given below:
4. get() – Return an element from the list at any given position.
5. insert() – Insert an element at any position of the list.
6. remove() – Remove the first occurrence of any element from a non-empty list.
7. removeAt() – Remove the element at a specified location from a non-empty list.
8. replace() – Replace an element at any position by another element.
9. size() – Return the number of elements in the list.
10. isEmpty() – Return true if the list is empty, otherwise return false.
11. isFull() – Return true if the list is full, otherwise return false.

Program:

i) List of integers
a = [1, 2, 3, 4, 5]

# List of strings
b = ['apple', 'banana', 'cherry']

# Mixed data types

c = [1, 'hello', 3.14, True]
print(a)
print(b)
print(c)

ii) Access first element

a = [10, 20, 30, 40, 50]

# Access first element

print(a[0])
# Access last element
print(a[-1])

iii)Adding Element into the List.

# Initialize an empty list

a = []

# Adding 10 to end of list

a.append(10)
print("After append(10):", a)

# Inserting 5 at index 0
a.insert(0, 5)
print("After insert(0, 5):", a)

# Adding multiple elements [15, 20, 25] at the end

a.extend([15, 20, 25])
print("After extend([15, 20, 25]):", a)

iv)Updating Element to the list

a = [10, 20, 30, 40, 50]

# Change the second element

a[1] = 25

print(a)

v)Removing the Element from list.

a = [10, 20, 30, 40, 50]

# Removes the first occurrence of 30

a.remove(30)
print("After remove(30):", a)

# Removes the element at index 1 (20)

popped_val = a.pop(1)
print("Popped element:", popped_val)
print("After pop(1):", a)

# Deletes the first element (10)

del a[0]
print("After del a[0]:", a)
vi)Iterating Over the List

a = ['apple', 'banana', 'cherry']

# Iterating over the list

for item in a:
print(item)
vii)Nested Lists and Multidimensional Lists

matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]

# Access element at row 2, column 3

print(matrix[1][2])
OUTPUT:
i)List of integers
[1, 2, 3, 4, 5]
['apple', 'banana', 'cherry']
[1, 'hello', 3.14, True]

ii)Accessing element

10
50

iii) Adding element into the List.

After append(10): [10]

After insert(0, 5): [5, 10]

After extend([15, 20, 25]): [5, 10, 15, 20, 25]

iv)Removing Elements from List

After remove(30): [10, 20, 40, 50]

Popped element: 20
After pop(1): [10, 40, 50]
After del a[0]: [40, 50]

v) Updating Elements into List

[10, 25, 30, 40, 50]

vi)Remove data from list

After remove(30): [10, 20, 40, 50]

Popped element: 20
After pop(1): [10, 40, 50]
After del a[0]: [40, 50]

vi)Iterating Over Lists

apple

banana

cherry

vii)Nested Lists and Multidimensional Lists

6
RESULT:
Thus the Implement List ADT using Python arrays demostrated sucessfuly.
Exp:4

Date: Linked List Implimentation of List

Aim: To Linked List Implimentation of List.

Algorithm:
1. Insertion:
2. At the beginning: O(1)
3. At the end: O(n) (since you need to traverse the list)
4. At a specific position: O(n) (since you need to traverse to that position)
5. Deletion:
6. From the beginning: O(1)
7. From the end: O(n) (since you need to traverse the list to find the last node)
8. At a specific position: O(n) (since you need to traverse to that position)
9. Traversal: O(n)
10. Search: O(n)
11. Reversal: O(n)
Program:

# Create a Node class to create a node

class Node:
def __init__(self, data):
self.data = data
self.next = None

# Create a LinkedList class

class LinkedList:
def __init__(self):
self.head = None

# Method to add a node at begin of LL

def insertAtBegin(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
else:
new_node.next = self.head
self.head = new_node

# Method to add a node at any index

# Indexing starts from 0.
def insertAtIndex(self, data, index):
if (index == 0):
self.insertAtBegin(data)

position = 0
current_node = self.head
while (current_node != None and position+1 != index):
position = position+1
current_node = current_node.next

if current_node != None:
new_node = Node(data)
new_node.next = current_node.next
current_node.next = new_node
else:
print("Index not present")

# Method to add a node at the end of LL

def insertAtEnd(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return

current_node = self.head
while(current_node.next):
current_node = current_node.next

current_node.next = new_node

# Update node of a linked list

# at given position
def updateNode(self, val, index):
current_node = self.head
position = 0
if position == index:
current_node.data = val
else:
while(current_node != None and position != index):
position = position+1
current_node = current_node.next

if current_node != None:
current_node.data = val
else:
print("Index not present")

# Method to remove first node of linked list

def remove_first_node(self):
if(self.head == None):
 return

self.head = self.head.next

# Method to remove last node of linked list

def remove_last_node(self):

if self.head is None:
return

current_node = self.head
while(current_node != None and current_node.next.next != None):
current_node = current_node.next

current_node.next = None

# Method to remove at given index

def remove_at_index(self, index):
if self.head == None:
return

current_node = self.head
position = 0
if position == index:
self.remove_first_node()
else:
while(current_node != None and position+1 != index):
position = position+1
current_node = current_node.next

if current_node != None:
current_node.next = current_node.next.next
else:
print("Index not present")

# Method to remove a node from linked list

def remove_node(self, data):
current_node = self.head

if current_node.data == data:
self.remove_first_node()
return

while(current_node != None and current_node.next.data != data):

current_node = current_node.next

if current_node == None:
return
else:
current_node.next = current_node.next.next
 # Print the size of linked list
def sizeOfLL(self):
size = 0
if(self.head):
current_node = self.head
while(current_node):
size = size+1
current_node = current_node.next
return size
else:
return 0

# print method for the linked list

def printLL(self):
current_node = self.head
while(current_node):
print(current_node.data)
current_node = current_node.next

# create a new linked list

llist = LinkedList()

# add nodes to the linked list

llist.insertAtEnd('a')
llist.insertAtEnd('b')
llist.insertAtBegin('c')
llist.insertAtEnd('d')
llist.insertAtIndex('g', 2)

# print the linked list

print("Node Data")
llist.printLL()

# remove a nodes from the linked list

print("\nRemove First Node")
llist.remove_first_node()
print("Remove Last Node")
llist.remove_last_node()
print("Remove Node at Index 1")
llist.remove_at_index(1)
# print the linked list again
print("\nLinked list after removing a node:")
llist.printLL()
print("\nUpdate node Value")
llist.updateNode('z', 0)
llist.printLL()
print("\nSize of linked list :", end=" ")
print(llist.sizeOfLL())
OUTPUT:

Node Data
c
a
g
b
d

Remove First Node

Remove Last Node
Remove Node at Index 1

Linked list after removing a node:

a
b

Update node Value

z
b

Size of linked list : 2

RESULT:
Thus the Implement List ADT using Python arrays demonstrated successfuly.
ExpNo:5

Date: Implementation Stack and Queue ADTs

Aim: To Implementation Stack and Queue ADTs

Algorithm:

Stack:

1. A pointer called TOP is used to keep track of the top element in the stack.
2. When initializing the stack, we set its value to -1 so that we can check if the stack is
empty by comparing TOP == -1.
3. On pushing an element, we increase the value of TOP and place the new element in the
position pointed to by TOP.
4. On popping an element, we return the element pointed to by TOP and reduce its value.
5. Before pushing, we check if the stack is already full
6. Before popping, we check if the stack is already empty
Queue:

Enqueue Operation
1. check if the queue is full
2. for the first element, set the value of FRONT to 0
3. increase the REAR index by 1
4. add the new element in the position pointed to by REAR

Dequeue Operation
1. check if the queue is empty
2. return the value pointed by FRONT
3. increase the FRONT index by 1
4. for the last element, reset the values of FRONT and REAR to -1
Program:

i) Python code to demonstrate Implementing stack using list

stack = ["Amar", "Akbar", "Anthony"]

stack.append("Ram")
stack.append("Iqbal")
print(stack)

# Removes the last item

print(stack.pop())
print(stack)

# Removes the last item

print(stack.pop())

print(stack)

ii) Python code to demonstrate Implementing Queue using list

queue = ["Amar", "Akbar", "Anthony"]

queue.append("Ram")
queue.append("Iqbal")
print(queue)

# Removes the first item

print(queue.pop(0))

print(queue)

# Removes the first item

print(queue.pop(0))

print(queue)
OUTPUT:

i)stack:

['Amar', 'Akbar', 'Anthony', 'Ram', 'Iqbal']

Iqbal
['Amar', 'Akbar', 'Anthony', 'Ram']
Ram
['Amar', 'Akbar', 'Anthony']

ii)Queue:

['Amar', 'Akbar', 'Anthony', 'Ram', 'Iqbal']

Amar
['Akbar', 'Anthony', 'Ram', 'Iqbal']
Akbar
['Anthony', 'Ram', 'Iqbal']
RESULT:
Thus the Linked list implementations of List demonstrated successfuly.
ExpNo:06 Applications of List, Stack and Queue ADTs

Date: i)Adding two polynomials using Linked List

Aim: To impliment Adding two polynomials using Linked List.

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:

# Python program to add two polynomials

class Node:
def __init__(self, c, p):
self.coeff = c
self.pow = p
self.next = None

def add_polynomial(head1, head2):

# if any list is empty, then return

# the other list.
if head1 is None:
return head2
if head2 is None:
return head1

# If head1.pow is greater, then recursively find

# its next node, and return head1.
if head1.pow > head2.pow:
next_ptr = add_polynomial(head1.next, head2)
head1.next = next_ptr
return head1

# If head2.pow is greater, then recursively find its

# next node, and return head2.
elif head1.pow < head2.pow:
 next_ptr = add_polynomial(head1, head2.next)
head2.next = next_ptr
return head2

# else store the sum of head1.coeff and head2.coeff in

# head1.coeff, then find its next node and return head1.
next_ptr = add_polynomial(head1.next, head2.next)
head1.coeff += head2.coeff
head1.next = next_ptr
return head1

def print_list(head):
curr = head

while curr is not None:

print(f"{curr.coeff},{curr.pow}", end=" ")
curr = curr.next

print()

if __name__ == "__main__":

# 1st polynomial: 5x^2+4x^1+2x^0

head1 = Node(5, 2)
head1.next = Node(4, 1)
head1.next.next = Node(2, 0)

# 2nd polynomial: -5x^1-5x^0

head2 = Node(-5, 1)
head2.next = Node(-5, 0)

head = add_polynomial(head1, head2)

print_list(head)
OUTPUT:

5,2 -1,1 -3,0

=== Code Execution Successful ===

RESULT:
Thus the Adding two polynomials using Linked List demonstrated successfuly.
ExpNo:6

Date: ii) Python program to evaluate value of a postfix expression

Aim: To Impliment Python program to evaluate value of a postfix expression.

Algorithm:

1. Create an empty stack called operandStack

2. Scan the string from left to right
3. If the token is an operand, convert it to an integer and push it onto the stack
4. If the token is an operator, pop the stack twice
5. Perform the arithmetic operation on the two operands
6. Push the result back onto the stack
7. When the input expression has been completely processed, pop the operand stack and
return the value

Program:

# Python program to evaluate value of a postfix expression

# Class to convert the expression

class Evaluate:

# Constructor to initialize the class variables

def __init__(self, capacity):
self.top = -1
self.capacity = capacity

# This array is used a stack

self.array = []

# Check if the stack is empty

def isEmpty(self):
return True if self.top == -1 else False

# Return the value of the top of the stack

def peek(self):
return self.array[-1]

# Pop the element from the stack

def pop(self):
if not self.isEmpty():
 self.top -= 1
return self.array.pop()
else:
return "$"

# Push the element to the stack

def push(self, op):
self.top += 1
self.array.append(op)

# The main function that converts given infix expression

# to postfix expression
def evaluatePostfix(self, exp):

# Iterate over the expression for conversion

for i in exp:

# If the scanned character is an operand

# (number here) push it to the stack
if i.isdigit():
self.push(i)

# If the scanned character is an operator,

# pop two elements from stack and apply it.
else:
val1 = self.pop()
val2 = self.pop()
self.push(str(eval(val2 + i + val1)))

return int(self.pop())

# Driver code
if __name__ == '__main__':
exp = "231*+9-"
obj = Evaluate(len(exp))

# Function call
print("postfix evaluation: %d" % (obj.evaluatePostfix(exp)))
OUTPUT:

postfix evaluation: -4

=== Code Execution Successful ===

RESULT:
Thus the Python program to evaluate value of a postfix expression demonstrated
successfuly.
ExpNo:7 Implementation of sorting and searching algorithms

Date: i)Python program for Bubble Sort Algorithm Implementation

Aim: To Impliment python program for bubble sort algorithm.

Algoirthm:

1. An array with values to sort.

2. An inner loop that goes through the array and swaps values if the first value is higher than
the next value. This loop must loop through one less value each time it runs.
3. An outer loop that controls how many times the inner loop must run. For an array with n
values, this outer loop must run n-1 times.
Program:

# Python3 program for Bubble Sort Algorithm Implementation

def bubbleSort(arr):

n = len(arr)

# For loop to traverse through all

# element in an array
for i in range(n):
for j in range(0, n - i - 1):

# Range of the array is from 0 to n-i-1

# Swap the elements if the element found
#is greater than the adjacent element
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]

# Driver code

# Example to test the above code

arr = [ 2, 1, 10, 23 ]

bubbleSort(arr)

print("Sorted array is:")

for i in range(len(arr)):
print("%d" % arr[i])
OUTPUT:

Sorted array is:

1
2
10
23
RESULT:

Thus the python program impliment for bubble sort algorithm demonstrated successfuly.
ExpNo: 7(ii) Implementation of Binary Search in Python

Date:

Aim: To Implementation of Binary Search in Python

Algorithm:

1.Start with the entire sorted list.

2.Compute the middle element of the list.

3.If the middle element is equal to the target value, return its index.

4.If the middle element is less than the target value, search in the right

half of the list.

5.If the middle element is greater than the target value, search in the

left half of the list.

6.Repeat steps 2-5 until the target value is found or the search interval

is empty.

Program:

def binary_search(arr, target, low, high):

"""
Perform binary search recursively to find the target value in the given sorted list.

Parameters:
arr (list): The sorted list to be searched.
target: The value to be searched for.
low (int): The lower index of the search interval.
high (int): The upper index of the search interval.

Returns:
int: The index of the target value if found, otherwise -1.
"""
if low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
 elif arr[mid] < target:
return binary_search(arr, target, mid + 1, high)
else:
return binary_search(arr, target, low, mid - 1)
else:
return -1

# Example usage:
arr = [2, 3, 4, 10, 40]
target = 10
result = binary_search(sorted(arr), target, 0, len(arr) - 1)
if result != -1:
print(f"Binary Search: Element found at index {result}")
else:
print("Binary Search: Element not found")
OUTPUT:

Binary Search: Element found at index 3

=== Code Execution Successful ===

RESULT:
Thus the python Implementation of Binary Search in Python demonstrated successfuly.
EcpNo:8 Implementation of Hash tables

Date:

Aim: To Implementation of Hash tables using python program

Algorithm:

1. Calculate the hash key. i.e. key = data % size

2. Check, if hashTable[key] is empty store the value directly by hashTable[key] = data
3. If the hash index already has some value then check for next index using key =
(key+1) % size
4. Check, if the next index is available hashTable[key] then store the value. Otherwise try
for next index.
5. Do the above process till we find the space.

Program:

class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None

class HashTable:
def __init__(self, capacity):
self.capacity = capacity
self.size = 0
self.table = [None] * capacity

def _hash(self, key):

return hash(key) % self.capacity

def insert(self, key, value):

index = self._hash(key)

if self.table[index] is None:
self.table[index] = Node(key, value)
self.size += 1
else:
current = self.table[index]
while current:
if current.key == key:
 current.value = value
return
current = current.next
new_node = Node(key, value)
new_node.next = self.table[index]
self.table[index] = new_node
self.size += 1

def search(self, key):

index = self._hash(key)

current = self.table[index]
while current:
if current.key == key:
return current.value
current = current.next

raise KeyError(key)

def remove(self, key):

index = self._hash(key)

previous = None
current = self.table[index]

while current:
if current.key == key:
if previous:
previous.next = current.next
else:
self.table[index] = current.next
self.size -= 1
return
previous = current
current = current.next

raise KeyError(key)

def __len__(self):
return self.size

def __contains__(self, key):

try:
self.search(key)
return True
except KeyError:
return False

# Driver code
if __name__ == '__main__':
# Create a hash table with
# a capacity of 5
ht = HashTable(5)
# Add some key-value pairs
# to the hash table
ht.insert("apple", 3)
ht.insert("banana", 2)
ht.insert("cherry", 5)
# Check if the hash table
# contains a key
print("apple" in ht) # True
print("durian" in ht) # False
# Get the value for a key
print(ht.search("banana")) # 2
# Update the value for a key
ht.insert("banana", 4)
print(ht.search("banana")) # 4
ht.remove("apple")
# Check the size of the hash table
print(len(ht)) # 3
OUTPUT:

True
False
2
4
2

=== Code Execution Successful ===

RESULT:

Thus the python program Implemented of Hash tables demonstrated successfuly.

ExpNo:9 Tree representation and traversal algorithms

Date:

Aim: To Impliment the tree representation and traversal.

Algorithm:

Algorithm for Inorder Traversal:

Inorder(tree)

Traverse the left subtree, i.e., call Inorder(left->subtree)

Visit the root.
Traverse the right subtree, i.e., call Inorder(right->subtree)

Algorithm for Preorder Traversal:

Preorder(tree)

Visit the root.

Traverse the left subtree, i.e., call Preorder(left->subtree)
Traverse the right subtree, i.e., call Preorder(right->subtree)

Algorithm for Postorder Traversal:

Algorithm Postorder(tree)

Traverse the left subtree, i.e., call Postorder(left->subtree)

Traverse the right subtree, i.e., call Postorder(right->subtree)
Visit the root

Program:

class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None

# Function to perform inorder traversal

def inorderTraversal(root):

# Base case: if null

if root is None:
 return

# Recur on the left subtree

inorderTraversal(root.left)

# Visit the current node

print(root.data, end=" ")

# Recur on the right subtree

inorderTraversal(root.right)
# Function to perform preorder traversal
def preorderTraversal(root):

# Base case
if root is None:
return

# Visit the current node

print(root.data, end=' ')

# Recur on the left subtree

preorderTraversal(root.left)

# Recur on the right subtree

preorderTraversal(root.right)
# Function to perform postorder traversal
def postorderTraversal(node):
# Base case: if the current node is null, return
if node is None:
return
# Recur on the left subtree
postorderTraversal(node.left)
# Recur on the right subtree
postorderTraversal(node.right)
# Visit the current node
print(node.data, end=' ')

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("inorder traversal",end='')
inorderTraversal(root)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("preordered traversal",end='')
preorderTraversal(root)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("Postorder traversal: ", end='')
postorderTraversal(root)
print()
OUTPUT:

Inorder traversal:

42513

Preordered traversal:

12453

Postorder traversal:

45231

=== Code Execution Successful ===

RESULT:
Thus the python program Implementation of Hash tables demonstrated successfuly.
ExpNo:10 Implementation of Binary Search Trees

Date:

Aim: To Implementation of Binary Search Trees using python program.

Algorithm:

1. The value is checked with the root node, if it is equal to the root node then it returns the
value
2. If the value is less than root node then it recursively calls the search operation in the left
sub tree
3. If the value is greater than root node then it recursively calls the search operation in the
right sub tree
4. In above example BST search for value 'value' begins from the root node.
5. If the value is not equal to the current node's value, the search continues recursively on
the left subtree if the value is less than the current node's value.
6. Once the value matches a node, the search terminates, returning the node containing the
value.

Program:

class Tree:
def __init__(self, val=None):
# Initialize a tree node with a value
self.value = val
if self.value:
# If a value is provided,
#create left and right children as empty trees
self.left = Tree()
self.right = Tree()
else:
# If no value is provided, set left and
#right children to None
self.left = None
self.right = None

def isempty(self):
# Check if the tree node is empty
return self.value == None
def isleaf(self):
# Check if the tree node is a leaf node (both left and right children are None)
if self.left.left == None and self.right.right == None:
return True
else:
return False

def insert(self, data):

if self.isempty():
# If the current node is empty,
#insert the data as its value
self.value = data
# Create empty left and right children
self.left = Tree()
self.right = Tree()
elif self.value == data:
# If the data already exists in the tree, return
return
elif data < self.value:
# If the data is less than the current node's value,
#insert it into the left subtree
self.left.insert(data)
return
elif data > self.value:
# If the data is greater than the current node's value,
#insert it into the right subtree
self.right.insert(data)
return

def find(self, v):

if self.isempty():
# If the tree is empty, the value is not found
print("{} is not found".format(v))
return False
if self.value == v:
# If the value is found at the current node,
#print a message and return True
print("{} is found".format(v))
return True
if v < self.value:
# If the value is less than the current node's value,
#search in the left subtree
return self.left.find(v)
else:
# If the value is greater than the current node's value,
#search in the right subtree
return self.right.find(v)

def inorder(self):
if self.isempty():
 # If the tree is empty, return an empty list
return []
else:
# Return the inorder traversal of the tree (left subtree, root, right subtree)
return self.left.inorder() + [self.value] + self.right.inorder()

# Example usage
t = Tree(20)
t.insert(15)
t.insert(25)
t.insert(8)
t.insert(16)
t.find(8)
print(t.inorder())
OUTPUT:

8 is found
[8, 15, 16, 20, 25]

=== Code Execution Successful ===

RESULT:
Thus the Implementation of Binary Search Trees using python program demonstrated
successfuly.
ExpNo:11 Implementation of Heaps

Date:

Aim: To Implimentation of Heaps using python program.

Algorithm:

1. The algorithm generates (n-1)! permutations of the first n-1 elements, adjoining the last
element to each of these. This will generate all of the permutations that end with the last
element.
2. If n is odd, swap the first and last element and if n is even, then swap the ith element (i is
the counter starting from 0) and the last element and repeat the above algorithm till i is
less than n.
3. In each iteration, the algorithm will produce all the permutations that end with the current
last element.

Program:

# Python code to demonstrate working of

# nlargest() and nsmallest()

# importing "heapq" to implement heap queue

import heapq

# initializing list
li1 = [6, 7, 9, 4, 3, 5, 8, 10, 1]

# using heapify() to convert list into heap

heapq.heapify(li1)

# using nlargest to print 3 largest numbers

# prints 10, 9 and 8
print("The 3 largest numbers in list are : ", end="")
print(heapq.nlargest(3, li1))

# using nsmallest to print 3 smallest numbers

# prints 1, 3 and 4
print("The 3 smallest numbers in list are : ", end="")
print(heapq.nsmallest(3, li1))
OUTPUT:

The 3 largest numbers in list are : [10, 9, 8]

The 3 smallest numbers in list are : [1, 3, 4]

=== Code Execution Successful ===

RESULT:
Thus the Implementation of Binary Search Trees using python program demonstrated
successfuly.
ExpNo:12 Graph representation and Traversal algorithms

Date:

Aim: To Impliment graph representation and traversal algorithm using python program.

Algorithm:

BFS:

1. To build index by search index

2. For GPS navigation
3. Path finding algorithms
4. In Ford-Fulkerson algorithm to find maximum flow in a network
5. Cycle detection in an undirected graph
6. In minimum spanning tree.
DFS:
A standard DFS implementation puts each vertex of the graph into one of two categories:
1. Visited
2. Not Visited
The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.
The DFS algorithm works as follows:
1. Start by putting any one of the graph's vertices on top of a stack.
2. Take the top item of the stack and add it to the visited list.
3. Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to
the top of the stack.
4. Keep repeating steps 2 and 3 until the stack is empty.

Program:

# Python3 Program to print BFS traversal

# from a given source vertex. BFS(int s)
# traverses vertices reachable from s.
from collections import defaultdict

# This class represents a directed graph

# using adjacency list representation
class Graph:

# Constructor
def __init__(self):

# Default dictionary to store graph

self.graph = defaultdict(list)

# Function to add an edge to graph

def addEdge(self, u, v):
self.graph[u].append(v)

# Function to print a BFS of graph

def BFS(self, s):

# Mark all the vertices as not visited

visited = [False] * (max(self.graph) + 1)

# Create a queue for BFS

queue = []

# Mark the source node as

# visited and enqueue it
queue.append(s)
visited[s] = True

while queue:

# Dequeue a vertex from

# queue and print it
s = queue.pop(0)
print(s, end=" ")

# Get all adjacent vertices of the

# dequeued vertex s.
# If an adjacent has not been visited,
# then mark it visited and enqueue it
for i in self.graph[s]:
if not visited[i]:
queue.append(i)
visited[i] = True

# A function used by DFS

def DFSUtil(self, v, visited):

# Mark the current node as visited

 # and print it
visited.add(v)
print(v, end=' ')

# Recur for all the vertices

# adjacent to this vertex
for neighbour in self.graph[v]:
if neighbour not in visited:
self.DFSUtil(neighbour, visited)

# The function to do DFS traversal. It uses

# recursive DFSUtil()
def DFS(self, v):

# Create a set to store visited vertices

visited = set()

# Call the recursive helper function

# to print DFS traversal
self.DFSUtil(v, visited)

# Driver code
if __name__ == '__main__':

# Create a graph given in

# the above diagram
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)

print("Following is Breadth First Traversal"

" (starting from vertex 2)")
g.BFS(2)
print("Following is Depth First Traversal (starting from vertex 2)")

# Function call
g.DFS(2)
OUTPUT:
BFS:

Following is Breadth First Traversal (starting from vertex 2)

2031

DFS:

Following is Depth First Traversal (starting from vertex 2):

2013
RESULT:
Thus the Graph representation and Traversal algorithms using python program
demonstrated successfuly.
ExpNo:13 Implementation of single source shortest path algorithm

Date:

Aim: To Implemention of single source shortest path algorithm using python program.

Algorithm:

1. Mark the source node with a current distance of 0 and the rest with infinity.
2. Set the non-visited node with the smallest current distance as the current node.
3. For each neighbor, N of the current node adds the current distance of the adjacent node
with the weight of the edge connecting 0->1. If it is smaller than the current distance of
Node, set it as the new current distance of N.
4. Mark the current node 1 as visited.
5. Go to step 2 if there are any nodes are unvisited.

Program:

# Python program for Dijkstra's single

# source shortest path algorithm. The program is
# for adjacency matrix representation of the graph

# Library for INT_MAX

import sys

class Graph():

def __init__(self, vertices):

self.V = vertices
self.graph = [[0 for column in range(vertices)]
for row in range(vertices)]

def printSolution(self, dist):

print("Vertex \tDistance from Source")
for node in range(self.V):
print(node, "\t", dist[node])

# A utility function to find the vertex with

# minimum distance value, from the set of vertices
 # not yet included in shortest path tree
def minDistance(self, dist, sptSet):

# Initialize minimum distance for next node

min = sys.maxsize

# Search not nearest vertex not in the

# shortest path tree
for u in range(self.V):
if dist[u] < min and sptSet[u] == False:
min = dist[u]
min_index = u

return min_index

# Function that implements Dijkstra's single source

# shortest path algorithm for a graph represented
# using adjacency matrix representation
def dijkstra(self, src):

dist = [sys.maxsize] * self.V

dist[src] = 0
sptSet = [False] * self.V

for cout in range(self.V):

# Pick the minimum distance vertex from

# the set of vertices not yet processed.
# x is always equal to src in first iteration
x = self.minDistance(dist, sptSet)

# Put the minimum distance vertex in the

# shortest path tree
sptSet[x] = True

# Update dist value of the adjacent vertices

# of the picked vertex only if the current
# distance is greater than new distance and
# the vertex in not in the shortest path tree
for y in range(self.V):
if self.graph[x][y] > 0 and sptSet[y] == False and \
dist[y] > dist[x] + self.graph[x][y]:
dist[y] = dist[x] + self.graph[x][y]

self.printSolution(dist)

# Driver's code
if __name__ == "__main__":
g = Graph(9)
g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],
 [4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]
]

g.dijkstra(0)
OUTPUT:

Vertex Distance from Source

0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14
RESULT:
Thus the Implemention of single source shortest path algorithm using python program
demonstrated successfuly.
ExpNo:14 Implementation of minimum spanning tree algorithms

Date:

Aim: To Implementation of minimum spanning tree algorithms using python program.

Algorithm:

prem’s Algorithm:
We transform the adjacency matrix into adjacency list using list in Python
Then we create a Pair class to store the vertex and its weight .
We sort the list on the basis of lowest weight.
We create priority queue and push the first vertex and its weight in the queue
Then we just traverse through its edges and store the least weight in a variable called.
At last after all the vertex we return the ans.
ii) Below are the steps for finding MST using Kruskal’s algorithm:
1. Sort all the edges in non-decreasing order of their weight.
2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If
the cycle is not formed, include this edge. Else, discard it.
3. Repeat step#2 until there are (V-1) edges in the spanning tree.
Program:
i)
# A Python3 program for
# Prim's Minimum Spanning Tree (MST) algorithm.
# The program is for adjacency matrix
# representation of the graph

# Library for INT_MAX

import sys

class Graph():
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for column in range(vertices)]
for row in range(vertices)]

# A utility function to print

# the constructed MST stored in parent[]
def printMST(self, parent):
print("Edge \tWeight")
for i in range(1, self.V):
print(parent[i], "-", i, "\t", self.graph[i][parent[i]])

# A utility function to find the vertex with

# minimum distance value, from the set of vertices
# not yet included in shortest path tree
def minKey(self, key, mstSet):

# Initialize min value

min = sys.maxsize

for v in range(self.V):
if key[v] < min and mstSet[v] == False:
min = key[v]
min_index = v

return min_index

# Function to construct and print MST for a graph

# represented using adjacency matrix representation
def primMST(self):

# Key values used to pick minimum weight edge in cut

key = [sys.maxsize] * self.V
parent = [None] * self.V # Array to store constructed MST
# Make key 0 so that this vertex is picked as first vertex
key[0] = 0
mstSet = [False] * self.V

parent[0] = -1 # First node is always the root of

for cout in range(self.V):

# Pick the minimum distance vertex from

# the set of vertices not yet processed.
# u is always equal to src in first iteration
u = self.minKey(key, mstSet)

# Put the minimum distance vertex in

# the shortest path tree
mstSet[u] = True

# Update dist value of the adjacent vertices

# of the picked vertex only if the current
# distance is greater than new distance and
# the vertex in not in the shortest path tree
for v in range(self.V):

# graph[u][v] is non zero only for adjacent vertices of m

 # mstSet[v] is false for vertices not yet included in MST
# Update the key only if graph[u][v] is smaller than key[v]
if self.graph[u][v] > 0 and mstSet[v] == False \
and key[v] > self.graph[u][v]:
key[v] = self.graph[u][v]
parent[v] = u

self.printMST(parent)

# Driver's code
if __name__ == '__main__':
g = Graph(5)
g.graph = [[0, 2, 0, 6, 0],
[2, 0, 3, 8, 5],
[0, 3, 0, 0, 7],
[6, 8, 0, 0, 9],
[0, 5, 7, 9, 0]]

g.primMST()

ii)
# Python program for Kruskal's algorithm to find
# Minimum Spanning Tree of a given connected,
# undirected and weighted graph

# Class to represent a graph

class Graph:

def __init__(self, vertices):

self.V = vertices
self.graph = []

# Function to add an edge to graph

def addEdge(self, u, v, w):
self.graph.append([u, v, w])

# A utility function to find set of an element i

# (truly uses path compression technique)
def find(self, parent, i):
if parent[i] != i:

# Reassignment of node's parent

# to root node as
# path compression requires
parent[i] = self.find(parent, parent[i])
return parent[i]

# A function that does union of two sets of x and y

# (uses union by rank)
def union(self, parent, rank, x, y):

# Attach smaller rank tree under root of

# high rank tree (Union by Rank)
if rank[x] < rank[y]:
parent[x] = y
elif rank[x] > rank[y]:
parent[y] = x

# If ranks are same, then make one as root

# and increment its rank by one
else:
parent[y] = x
rank[x] += 1

# The main function to construct MST

# using Kruskal's algorithm
def KruskalMST(self):

# This will store the resultant MST

result = []

# An index variable, used for sorted edges

i=0

# An index variable, used for result[]

e=0

# Sort all the edges in

# non-decreasing order of their
# weight
self.graph = sorted(self.graph,
key=lambda item: item[2])

parent = []
rank = []

# Create V subsets with single elements

for node in range(self.V):
parent.append(node)
rank.append(0)

# Number of edges to be taken is less than to V-1

while e < self.V - 1:

# Pick the smallest edge and increment

# the index for next iteration
u, v, w = self.graph[i]
i=i+1
x = self.find(parent, u)
y = self.find(parent, v)
 # If including this edge doesn't
# cause cycle, then include it in result
# and increment the index of result
# for next edge
if x != y:
e=e+1
result.append([u, v, w])
self.union(parent, rank, x, y)
# Else discard the edge

minimumCost = 0
print("Edges in the constructed MST")
for u, v, weight in result:
minimumCost += weight
print("%d -- %d == %d" % (u, v, weight))
print("Minimum Spanning Tree", minimumCost)

# Driver code
if __name__ == '__main__':
g = Graph(4)
g.addEdge(0, 1, 10)
g.addEdge(0, 2, 6)
g.addEdge(0, 3, 5)
g.addEdge(1, 3, 15)
g.addEdge(2, 3, 4)

# Function call
g.KruskalMST()
OUTPUT:

i)prim’s

Edge Weight
0-1 2
1-2 3
0-3 6
1-4 5

ii)Kruskal's

Following are the edges in the constructed MST

2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
Minimum Cost Spanning Tree: 19
RESULT:
Thus the minimum spanning tree algorithms using python program demonstrated
successfuly.