Department of Computer Science and Engineering (Cyber Security)

LAB MANUAL

COURSE CODE CD3291

COURSE NAME DATA STRUCTURES AND ALGORITHMS LABORATORY

REGULATION 2021 R

YEAR/SEM II/III

Prepared by,

[Link],AP/CyS

1
 Department of Computer Science and Engineering (Cyber Security)
Vision
To develop skilled cyber security professionals equipped to secure digital landscapes, address emerging
cyber challenges, and contribute to society with strong technical expertise, entrepreneurial skills, and ethical
values.
Mission
• Foster self-discipline and critical thinking in students through robust teaching and learning.
• Empower students to become proficient cyber security professionals and responsible citizens.
• Strengthen industry partnerships by establishing specialized centres for advanced skill development and
practical exposure.
• Deliver knowledge for secure and innovative solutions, contributing to sustainable and ethical technology
advancement.
Programme Educational Objectives
Graduates of Computer Science and Engineering Programme will:
PEO Program Outcome(s)
Graduates can apply their technical competence in computer science to solve real
PEO.1
world problems, with technical and people leadership.
Graduates Conduct cutting edge research and develop solutions on problems of social
PEO.2
relevance.
Graduates will Work in a business environment, exhibiting team skills, work ethics,
PEO.3
adaptability and lifelong learning.

Programme Specific Outcomes

At the end of the Programme graduate will be able to

PSO Description
Exhibit design and programming skills to build and automate business solutions using
PSO.1 cutting edge technologies.

Strong theoretical foundation leading to excellence and excitement towards research, to

PSO.2 Provide elegant solutions to complex problems.

Ability to work effectively with various engineering fields as a team to design, build, and
PSO.3 develop system applications.
 CD3291 – DATA STRUCTURES AND ALGORITHMS LABORATORY LTPC
2023

COURSE OBJECTIVES:
● To implement ADTs in Python
● To design and implement linear data structures – lists, stacks, and queues
● To implement sorting, searching and hashing algorithm
● To solve problems using tree and graph structures

LIST OF EXPERIMENTS:

1. Implement simple ADTs as Python classes

2. Implement recursive algorithms in Python
3. Implement List ADT using Python arrays
4. Linked list implementations of List
5. Implementation of Stack and Queue ADTs
6. Applications of List, Stack and Queue ADTs
7. Implementation of sorting and searching algorithms
8. Implementation of Hash tables
9. Tree representation and traversal algorithms
10. Implementation of Binary Search Trees
11. Implementation of Heaps
12. Graph representation and Traversal algorithms
13. Implementation of single source shortest path algorithm

14. Implementation of minimum spanning tree

TOTAL: 60 PERIODS
OUTCOMES:

Upon completion of the course, the students will be able to

CO1: Design and implement various mobile applications using emulators.
CO2: Implement ADTs as Python classes
CO3:Design, implement, and analyse linear data structures, such as lists, queues, and stacks, according to
the needs of different applications
CO4: Design, implement, and analyse efficient tree structures to meet requirements such as searching,
indexing, and sorting
CO5: Model problems as graph problems and implement efficient graph algorithms to
solve theme.
 CONTENTS

[Link]. Date Name of the Experiment Page Marks Sign

No.
1 SIMPLE ADTS AS PYTHON CLASSES
2 RECURSIVE ALGORITHMS IN PYTHON

A. FACTORIAL

B. TOWERS OF HANOI

C. FIBONACCI SERIES

3 LIST ADT USING PYTHON ARRAYS

4 LINKED LIST IMPLEMENTATIONS OF

LIST

5 STACK AND QUEUE ADTS

A. IMPLEMENTATION OF STACK
B. IMPLEMENTATION OF QUEUE
6 APPLICATIONS OF LIST, STACK AND
QUEUE ADTS

A. APPLICATIONS OF LIST ADT

B. APPLICATIONS OF STACK ADT

C. APPLICATIONS OF QUEUE ADT

7 SORTING AND SEARCHING ALGORITHMS

A. SORTING ALGORITHM (INSERTION SORT)

B. SEARCHING ALGORITHM (LINEAR SEARCH)

8 HASH TABLE
9 TREE REPRESENTATION AND
TRAVERSAL ALGORITHM

10 BINARY SEARCH TREE

11 HEAP IMPLEMENTATION
12 GRAPH REPRESENTATION AND
TRAVERSAL ALGORITHM

13 SINGLE SOURCE SHORTEST PATH

ALGORITHM

14 MINIMUM SPANNING TREE

IMPLEMENTATION
EX:NO:1 SIMPLE ADTS AS PYTHON CLASSES
DATE
AIM:
To write a Python program that appends, deletes and displays elements of a list using classes.
ALGORITHM:
1. Create a class and using a constructor initialize values of that class.
2. Create methods for adding, removing and displaying elements of the list and return
the respective values.
3. Create an object for the class.
4. Using the object, call the respective function depending on the choice taken from the user.
5. Print the final list.
6. Exit
PROGRAM:
class check():
def _init (self):
self.n=[]
def add(self,a):
return [Link](a)
def remove(self,b):
[Link](b)
def dis(self):
return (self.n)
obj=check() choice=1
while choice!=0:
print("0. Exit")
print("1. Add")
print("2. Delete")
print("3. Display")
choice=int(input("Enter choice: "))
if choice==1:
n=int(input("Enter number to append: "))
[Link](n)
print("List: ",[Link]())
elif choice==2:
n=int(input("Enter number to remove: "))
[Link](n)
print("List: ",[Link]())
elif choice==3:
print("List: ",[Link]())
elif choice==0:
print("Exiting!") else:
print("Invalid choice!!")
print()
OUTPUT:
Case 1:
0. Exit
1. Add
2. Delete
3. Display
Enter
choice:
1
Enter number to append:
23 List: [23]
0. Exit
1. Add
2. Delete
3. Display
Enter choice:
1
Enter number to append: 45 List:
[23, 45]
0. Exit
1. Add
2. Delete
3. Display
Enter
choice:
1
Enter number to append: 56 List:
[23, 45, 56]
0. Exit
1. Add
2. Delete
3. Display
Enter choice: 2
Enter number to remove: 45 List:
[23, 56]
0. Exit
1. Add
2. Delete
3. Display
4. Enter choice:
0 Exiting!
Case 2:
0. Exit
1. Add
2. Delete
3. Display
Enter choice:1
Enter number to append: 10 List:
[10]
0. Exit
1. Add
[Link]
[Link]
Enter choice: 1
Enter number to append:7
List: [10, 7]
0. Exit
1. Add
2. Delete
3. Display
Enter choice: 0
Exiting!

RESULT:
Thus, the Python program that appends, deletes and displays elements of a list using classes has been
implemented successfully.
 EX:NO:2A RECURSIVE ALGORITHMS IN PYTHON DATE:
AIM:
To write a python program takes a number and determines the factorial of the number using
recursion.
ALGORITHM:
1. Take a number from the user and store it in a variable.
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. Exit.
PROGRAM:
def factorial(n): if (n <= 1):
return 1
else:
return(n*factorial(n-1))
n = int (input ("Enter number:")) print("Factorial:")
print(factorial(n))
OUTPUT:
Case 1:
Enter number:5 Factorial:
120
Case 2:
Enter number:9 Factorial:
362880

RESULT:
Thus, the Python program that takes a number and determines the factorial of the number using
recursion has been implemented successfully.
[Link]:2C IMPLEMENT RECURSIVE ALGORITHMS IN
PYTHON DATE:

Aim: To Implement a recursive algorithms in Python using Towers of Hanoi

Algorithm:
1) Only one disk can be moved at a time.
2) Each move consists of taking the upper disk from one of the stacks and placing it on top
of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3) No disk may be placed on top of a smaller disk.
Program:
def TowerOfHanoi(n , source, destination, auxiliary):
if n==1:
print ("Move disk 1 from source",source,"to destination",destination)
return
TowerOfHanoi(n-1, source, auxiliary, destination)
print ("Move disk",n,"from source",source,"to
destination",destination) TowerOfHanoi(n-1, auxiliary, destination,
source)
n=4
TowerOfHanoi(n,'A','B','C')
# A, C, B are the name of rods

Output:
Move disk 1 from source A to destination
C Move disk 2 from source A to
destination B Move disk 1 from source C to
destination B Move disk 3 from source A
to destination C Move disk 1 from source B
to destination A Move disk 2 from source
B to destination C Move disk 1 from source
A to destination C Move disk 4 from
source A to destination B Move disk 1
from source C to destination B Move disk 2
from source C to destination A Move disk
1 from source B to destination A Move
disk 3 from source C to destination B Move
disk 1 from source A to destination C
Move disk 2 from source A to destination
B Move disk 1 from source C to destination
B

RESULT:
Thus, the Python program determines the towers of hanoi using recursion has been implemented
successfully.
 [Link]:2C IMPLEMENT RECURSIVE ALGORITHMS IN PYTHON
DATE:

Aim: To Implement a recursive algorithms in Python using Fibonacci Series

Algorithm:
Step 1: Define a recursive function called Fibonacci that takes an integer n as an input.
Step 2: Set up a base case: If n is less than or equal to 1, return n
Step 3: In the recursive case, call the Fibonacci function with n-1 as the argument and add the
result by n. Step 4: Return the result obtained from the recursive call.
Step 5: To find the Fibonacci series of a specific number, invoke the Fibonacci function with the desired
number
Program:
def fibonacci(n):

if n<=1:
return n
return fibonacci(n-1) + fibonacci(n-2)
n=int(input("Enter the number to generate Fibonacci
Series:")) print(“Fibonacci Series: ")
for i in range(n):
print(fibonacci(i))
Output:

Enter the number to generate Fibonacci Series: 5

Fibonacci Series:
0
1
1
2
3

RESULT:
Thus, the Python program that takes a number and determines the Fibonacci series using recursion
has been implemented successfully.
EX:NO:3 LIST ADT USING PYTHON
ARRAYS DATE:
AIM
To write a Python program for creation and insertion to implement list using an array.
ALGORITHM
1: Start.
2: Declare the necessary functions for implementation. Step 3: Get the input from the user and
store it an array.
3: In Insertion, half of the elements to be shifted upwards and in deletion half of the elements to be
shifted downwards.
4: Display the output using an
array.
5: Stop.
PROGRAM:
import array
arr = [Link]('i', [1, 2, 3])
print ("The new created array is : ",end=" ")
for i in range (0, 3):
print (arr[i], end="
") print("\r")
[Link](4);
print("The appended array is : ",
end="") for i in range (0, 4):
print (arr[i], end="
") [Link](2, 5)
print("\r")
print ("The array after insertion is : ", end="")
for i in range (0, 5):
print (arr[i], end=" ")

OUTPUT:
The new created array is: 1 2 3

The appended array is: 1 2 3 4

The array after insertion is: 1 2 5 3 4

RESULT:
Thus, the Python program for creation and insertion to implement list using an array has been
executed successfully.
 EX:NO:4 LINKED LIST IMPLEMENTATIONS OF LIST

DATE:
Aim:
To Implement the Linked list implementations of List using python
Algorithm:
1. Create a list[ ] with MAX size as your wish.
2. Write function for all the basic operations of list - create(), insert(), deletion(),
display(). 3. Using append() to extend the elements, removal() to delete the elements
4. Close the program.
Coding:
List = [1,2,3,4]
print("Initial List: ")
print(List)
[Link]([8, 'Geeks', 'Always'])
print("\nList after performing Extend Operation: ")
print(List)
List = []
print("Blank List: ")
print(List)
List = [10, 20, 14]
print("\nList of numbers: ")
print(List)
List = ["Geeks", "For", "Geeks"]
print("\n List Items: ")
print(List[0])
print(List[2])
Adding the elements:
List = [1,2,3,4]
print("Initial List: ")
print(List)
[Link](3, 12)
[Link](0, 'Geeks')
print("\nList after performing Insert Operation: ")
print(List)
List = [1, 2, 3, 4, 5, 6,7,8,9,10,11,12]
print("Intial List: ")
print(List)
[Link](5)
[Link](6)
print("\nList after Removal of two elements: ")
print(List)
for i in range(1, 5):
[Link](i)
print("\nList after Removing a range of elements: ")
print(List)
List = [['Geeks', 'For'] , ['Geeks']]
print("\nMulti-Dimensional List: ")
print(List)

Output:
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]
>>>
===================== RESTART: Z:/New folder/queue [Link]
=====================
Initial List:
[1, 2, 3, 4]
List after performing Insert
Operation: ['Geeks', 1, 2, 3, 12, 4]
>>>
===================== RESTART: Z:/New folder/queue [Link]
=====================
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]

Result:
Thus the list was created,inserted,removed and extend the element was executed successfully.
EX:NO:5 STACK AND QUEUE
ADTS DATE:
A. IMPLEMENTATION OF STACK:

AIM:
To write a python program creates a stack and allows the user to perform push and pop operations on it.

ALGORITHM:
1. Create a class Node with instance variables data and next.
2. Create a class Stack with instance variable head.
3. The variable head points to the first element in the linked list.
4. Define methods push and pop inside the class Stack.
5. The method push adds a node at the front of the linked list.
6. The method pop returns the data of the node at the front of the linked list and removes
the node. It returns None if there are no nodes.
7. Create an instance of Stack and present a menu to the user to perform operations on the stack.

PROGRAM:
class Node:
def init (self, data):
[Link] = data [Link] =
None class Stack:
def init (self): [Link] = None
def push(self, data):
if [Link] is None: [Link] = Node(data)
else:
new_node = Node(data) new_node.next = [Link] [Link] = new_node
def pop(self):
if [Link] is
None: return
None
else:
popped = [Link]
[Link] =
[Link] return
popped
a_stack =
Stack() while
True:
print('push
<value>')
print('pop')
print('quit')
do = input('What would you like to do? ').split()
operation = do[0].strip().lower()
if operation == 'push':a_stack.push(int(do[1])) elif operation == 'pop':
popped = a_stack.pop() if popped is None:
print('Stack is empty.') else:
print('Popped value: ', int(popped)) elif operation == 'quit':
break
 OUTPUT:
Case 1:
push
<value>
pop
quit
what would you like to do? push
15 push <value>
po
pqui
t
What would you like to do?
push 3 push <value>
p

u
i
t
What would you like to do?
pop Popped value: 3
push
<value>
pop
quit
What would you like to do?
pop Popped value: 15
push
<value>
pop
quit
What would you like to do?
pop Stack is empty.
push
<value>
pop
quit
What would you like to do? quit

RESULT:
Thus the python program to creates a stack and allows the user to perform push and pop
operations on it has been executes successfully.
.
B. IMPLEMENTATION OF QUEUE:

AIM:
To write a python program creates a queue and allows the user to perform enqueue and dequeue
operations on it.

ALGORITHM:
1. Create a class Node with instance variables data and next.
2. Create a class Queue with instance variables head and last.
3. The variable head points to the first element in the linked list while last points to the last element.
4. Define methods enqueue and dequeue inside the class Queue.
5. The method enqueue adds a node at the end of the linked list.
6. The method dequeue returns the data of the node at the front of the linked list and removes
the node. It returns None if there are no nodes.
7. Create an instance of Queue and present a menu to the user to perform operations on the queue.

PROGRAM:
class Node:
def init (self, data): [Link] = data [Link] = None
class Queue:
def init (self): [Link] = None [Link] = None
def enqueue(self, data): if [Link] is None:
[Link] = Node(data) [Link] = [Link]
else:
[Link] = Node(data) [Link] = [Link]
def dequeue(self):
if [Link] is None: return None
else:
to_return = [Link] [Link] = [Link] return to_return
a_queue = Queue() while True:
print('enqueue <value>') print('dequeue')
print('quit')do = input('What would you
like to do? ').split()
operation =
do[0].strip().lower() if
operation == 'enqueue':
a_queue.enqueue(int(do[1]))
elif operation == 'dequeue':
dequeued =
a_queue.dequeue() if
dequeued is None:
print('Queue is
empty.') else:
print('Dequeued element: ', int(dequeued))
elif operation == 'quit':
break

OUTPUT:
Case 1:
enqueue
<value>
dequeue
quit
What would you like to do? enqueue
3 enqueue <value>
dequ
eue
quit
What would you like to do? enqueue
4 enqueue <value>
dequ
eue
quit
What would you like to do?
dequeue Dequeued element: 3
enqueue
<value>
dequeue
quit
What would you like to do?
dequeue Dequeued element: 4
enqueue
<value>
dequeue
quit
What would you like to do?
dequeue Queue is empty.
enqueue
<value>
dequeue
quit
What would you like to do? quit

Case 2:
enqueue
<value>
dequeue
quit
What would you like to do?
dequeue Queue is [Link]
<value> dequeue
quit
What would you like to do? enqueue
5 enqueue <value>
dequ
eue
quit
What would you like to do?
dequeue Dequeued element: 5
enqueue
<value>
dequeue
quit
What would you like to do? quit

RESULT:
Thus, the python program to creates a queue and allows the user to perform enqueue
and dequeue operations on it has been executes successfully.
 EX:NO:6 APPLICATIONS OF LIST, STACK AND QUEUE ADTS
DATE:
A. APPLICATIONS OF LIST
ADT AIM:
To write a Python program for implementation of polynomial ADT.
ALGORITHM:
1: Start the program
2: Get the coefficients and powers for the two polynomials to be added. 3:
Add the coefficients of the respective powers.
4: Display the added polynomial. Step5: Terminate the program.
PROGRAM:
def add(A, B, m, n):
size = max(m, n);
sum = [0 for i in range(size)] for i in range(0, m, 1):
sum[i] = A[i]
for i in range(n): sum[i] += B[i]
return sum
def printPoly(poly, n): for i in range(n):
print(poly[i], end = "") if (i != 0):
print("x^", i, end = "") if (i != n - 1):
print(" + ", end = "") if name == ' main ':
# The following array represents # polynomial 5 + 10x^2 + 6x^3 A = [5, 0, 10, 6]
# The following array represents # polynomial 1 + 2x + 4x^2
B = [1, 2, 4]
m = len(A) n = len(B)
print("First polynomial is") printPoly(A, m)print("\n", end = "")
print("Second polynomial is") printPoly(B, n)
print("\n", end = "")
sum = add(A, B, m, n) size = max(m, n)
print("sum polynomial is") printPoly(sum, size)

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

RESULT:
Thus, the Python program for implementation of polynomial ADT has been executed successfully.
 B. APPLICATIONS OF STACK ADT

C. AIM:

To write a Python program to Check if Expression is Correctly Parenthesized

ALGORITHM:
1. Create a class Stack with instance variable items initialized to an empty list.
2. Define methods push, pop and is_empty inside the class Stack.
3. The method push appends data to items.
4. The method pop pops the first element in items.
5. The method is_empty returns True only if items is empty.
6. Prompt the user for an expression.
7. Iterate through the characters of the expression and push to the stack if an open parenthesis
is encountered and pop if a close parenthesis is encountered.
8. Determine whether the expression has balanced parentheses.
PROGRAM:
class Stack:
def init (self): [Link] = []
def is_empty(self): return [Link] == []
def push(self, data): [Link](data)
def pop(self):
return [Link]()
s = Stack()
exp = input('Please enter the expression: ')
for c in exp: if c == '(':
[Link](1)
elif c == ')':
if s.is_empty(): is_balanced = False break
[Link]()
else:
if s.is_empty(): is_balanced = True
else:
is_balanced = False
if is_balanced:
print('Expression is correctly parenthesized.')else:
print('Expression is not correctly parenthesized.')

OUTPUT:
Case 1:
Please enter the expression: (3 + 4 * (1 + (2))/(7 * (8 + 9)))
Expression is correctly parenthesized.

Case 2:
Please enter the expression: (a + b))(3)
Expression is not correctly parenthesized.

Case 3:
Please enter the expression: (4 + (3 * 2)
Expression is not correctly parenthesized

RESULT:
Thus, the Python program for implementation of whether Expression is Correctly Parenthesized has
been executed successfully.
 C APPLICATION OF QUEUE ADT
Aim:
To implement the application of queue using FCFS CPU Scheduling
Algorithm:
1. Input the number of processes required to be scheduled using FCFS, burst time for each process and
its arrival time.
2. Calculate the Finish Time, Turn Around Time and Waiting Time for each process which in turn help to
calculate Average Waiting Time and Average Turn Around Time required by CPU to schedule given set
of process using FCFS.
a. for i = 0, Finish Time T 0 = Arrival Time T 0 + Burst Time T 0
b. for i >= 1, Finish Time T i = Burst Time T i + Finish Time T i - 1
c. for i = 0, Turn Around Time T 0 = Finish Time T 0 - Arrival Time T 0
d. for i >= 1, Turn Around Time T i = Finish Time T i - Arrival Time T i
e. for i = 0, Waiting Time T 0 = Turn Around Time T 0 - Burst Time T 0
f. for i >= 1, Waiting Time T i = Turn Around Time T i - Burst Time T i - 1
3. Process with less arrival time comes first and gets scheduled first by the CPU.
4. Calculate the Average Waiting Time and Average Turn Around Time.
5. Stop the program
Coding:
def findWaitingTime(processes, n, bt, wt):
wt[0] = 0
for i in range(1, n ):
wt[i] = bt[i - 1] + wt[i - 1]
def findTurnAroundTime(processes, n,bt, wt, tat): # calculating turnaround
# time by adding bt[i] + wt[i]
for i in range(n): tat[i] = bt[i] + wt[i]
def findavgTime( processes, n, bt): wt = [0] * n
tat = [0] * n total_wt = 0
total_tat = 0 findWaitingTime(processes, n, bt, wt)
findTurnAroundTime(processes, n,bt, wt, tat)
print( "Processes Burst time " +" Waiting time " +" Turn around time")
for i in range(n):
total_wt = total_wt + wt[i] total_tat =
total_tat + tat[i]
print(" " + str(i + 1) + "\t\t" +str(bt[i]) + "\t "str(wt[i]) + "\t\t " +str(tat[i]))
print( "Average waiting time = "+ str(total_wt / n))
print("Average turn around time = "+ str(total_tat /
n)) if name ==" main ":
processes = [ 1, 2, 3] n = len(processes)
burst_time = [10, 5, 8] 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.33333

Average turn around time = 16

Result:
Thus the FCFS CPU Scheduling was Executed Successfully
EX:NO:7 SORTING AND SEARCHING
ALGORITHMS DATE:

A. SORTING ALGORITHM (INSERTION SORT):

AIM:

To Perform Insertion Sorting in Python Programming.

ALGORITHM:

Step 1: Start
Step 2: Define list of elements(alist)
Step 3: Take first element find its appropriate position and insert them
Step 4: Repeat till every element is sorted
Step 5: Print the list of
elements Step 6: Stop

PROGRAM:

def insertionSort(lst):
for index in range(1, len(lst)):
currentvalue = lst[index] position = index
while position > 0 and lst[position - 1] > currentvalue:
lst[position] = lst[position - 1] position = position - 1
lst[position] = currentvalue
lst = [54, 26, 93, 17, 77, 31, 44, 55, 20]
insertionSort(lst) print(lst)

OUTPUT:

17,20,26,31,44,54,55,77,93

RESULT:

Thus, the python program to perform Insertion Sort is created and executed successfully.
B. SEARCHING ALGORITHM (LINEAR

SEARCH) AIM:

To Perform a Linear Search in Python Programming

ALGORITHM:

Step 1: Start
Step 2: Define a list of elements list_of_elements[]
Step 3: Get the element to be checked from the user(x)
Step 4: Compare the elements with each element in the list
Step 5: If found print found and print index number
Step 6: Else print element not found Step
6: Stop

PROGRAM:

list_of_elements = [4, 2, 8, 9, 3, 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("%d found at %dth position"%(x,i))
break
if(found == False):
print("%d is not in list"%x)

OUTPUT:

Enter element to search:4

4 is found at 0th position

RESULT:

Thus, the python program to perform Linear Search is created and executed successfully.
EX:NO:8 HASH TABLE
DATE:
AIM:
To write a python program to implement the concept of hashing using separate chaining.
ALGORITHM:
1: Start
2: Create Table size
3: Create hash function
4: To insert a node into the hash table, we need to find the hash index for the given key. And it
could be calculated using the hash function.
5: Display hash
entry.
6: Stop
PROGRAM:
def display_hash(hashTable):
for i in range(len(hashTable)):
print(i, end = " ") for j in
hashTable[i]: print("-->", end = " ")
print(j, end = " ")
print()
HashTable = [[] for _ in range(10)] def Hashing(keyvalue):
return keyvalue % len(HashTable)
def insert(Hashtable, keyvalue, value):
hash_key = Hashing(keyvalue)
Hashtable[hash_key].append(value)
insert(HashTable, 10, 'Allahabad')
insert(HashTable, 25, 'Mumbai')
insert(HashTable, 20, 'Mathura')
insert(HashTable, 9, 'Delhi')
insert(HashTable, 21, 'Punjab')
insert(HashTable, 21, 'Noida')
display_hash (HashTable)

OUTPUT:
0 --> Allahabad -->
Mathura 1 --> Punjab -->
Noida
2
3
4
5 --> Mumbai
6
7
8
9 --> Delhi

RESULT:
Thus, the python program to implement the concept of hashing using separate chaining. has been
implemented successfully.
EX:NO:9 TREE REPRESENTATION AND TRAVERSAL
ALGORITHM DATE:

AIM:

To write a python program to implement the tree representation and traversal algorithm

ALGORITHM:

1. The left sub tree of a node contains smaller nodes than a root node.
2. The right sub tree of a node contains greater nodes than a root node.
3. Both the left and right sub trees must also be binary search trees.
4. There are three types of tree traversals: Preorder, Postorder, and Inorder.

Pre-order traversal Algorithm:

1. Visit the root (we will print it when we visit to show the order of visiting)
2. Traverse the left subtree in pre-order
3. Traverse the right subtree in pre-order

In-order traversal
Visit the root node in between the left and right node (in)
Algorithm:
1. Traverse the left subtree in in-order
2. Visit the root (we will print it when we visit to show the order of visiting)
3. Traverse the right subtree in in-order

Post-order traversal
Visit the root node after (post) visiting the left and right subtree.
Algorithm:
1. Traverse the left subtree in in-order
2. Traverse the right subtree in in-order
3. Visit the root (we will print it when we visit to show the order of visiting)

PROGRAM:
class Node:
def init (self, key): [Link] = None [Link] = None [Link] = key
def printInorder(root):
if root:

printInorder([Link]) print([Link]),
printInorder([Link])
def printPostorder(root):
if root:
printPostorder([Link])
printPostorder([Link])
print([Link]),
def
printPreorder(root):
if root:
print([Link]),
printPreorder([Link])
printPreorder([Link])
root = Node(1) [Link] = Node(2) [Link] = Node(3) [Link] = Node(4)
[Link] = Node(5)
print "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 1 2 4 5 3
Inorder traversal of binary tree
is 4 2 5 1 3
Postorder traversal of binary tree
is 4 5 2 3 1

RESULT:

Thus, the python program to implement the concept of tree representation and traversal algorithm. has
been implemented successfully.
 EX:NO:10 BINARY SEARCH
TREE DATE:

AIM:
To write a python program creates a binary search tree and presents a menu to the user to
perform insertion, deletion and inorder traversal operations.

Binary search:
1. Read the search element from the user.
2. Find the middle element in the sorted list.
3. Compare, the search element with the middle element in the sorted list.
4. If both are matching, then display "Given element found!!!" and terminate the function
5. If both are not matching, then check whether the search element is smaller or larger than middle
element
6. If the search element is smaller than middle element, then repeat steps 2, 3, 4 and 5 for the left sublist of
the middle element.
7. If the search element is larger than middle element, then repeat steps 2, 3, 4 and 5 for the right
sublist of the middle element.
8. Repeat the same process until we find the search element in the list or until sublist contains only
one element.
9. If that element also doesn't match with the search element, then display "Element not found in the
list!!!" and terminate the function.

Binary Search Coding:

def BinarySearch(arr, low, high, key): if high
>= low:
mid = (high + low) // 2 if (arr[mid] == key):
return mid
elif (arr[mid] > key):
return BinarySearch(arr, low, mid - 1,
key) else:
return BinarySearch(arr, mid + 1, high, key)
else:
return -1
arr = [ 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 ]
key = 40
result = BinarySearch(arr, 0, len(arr)-1, key) if
result != -1:
print(key, "Found at index", str(result))
else:
print(key, "not Found")

OUTPUT:
40 Found at index 3

RESULT:

Thus, the python program to implement the concept of binary search tree has been implemented
successfully.
EX:NO:11 HEAP IMPLEMENTATION

DATE:

AIM:
To write a python program creates a binary max-heap and presents a menu to the user to perform
various operations on it.
ALGORITHM:
1. Create a class BinaryHeap with an instance variable items set to an empty list. This empty list
is used to store the binary heap.
2. Define methods size, parent, left, right, get, get_max, extract_max, max_heapify, swap
and insert.
3. The method size returns the number of elements in the heap.
4. The method parent takes an index as argument and returns the index of the parent.
5. The method left takes an index as argument and returns the index of its left child.
6. The method right takes an index as argument and returns the index of its right child.
7. The method get takes an index as argument and returns the key at the index.
8. The method get_max returns the maximum element in the heap by returning the first element
in the list items.
9. The method extract_max returns the the maximum element in the heap and removes it.
10. The method max_heapify takes an index as argument and modifies the heap structure at
and below the node at this index to make it satisfy the heap property.
11. The method swap takes two indexes as arguments and swaps the corresponding elements in
the heap.
12. The method insert takes a key as argument and adds that key to the heap.

PROGRAM:
class BinaryHeap: def init (self):
[Link] = []
def size(self):
return len([Link])
def parent(self, i): return (i - 1)//2
def left(self, i): return 2*i + 1
def right(self, i): return 2*i + 2
def get(self, i): return
[Link][i]
def get_max(self): if [Link]() == 0:
return None
return
[Link][0]
def extract_max(self): if [Link]() == 0: return None
largest = self.get_max() [Link][0] = [Link][-1]
del [Link][-1] self.max_heapify(0)
return largest
def max_heapify(self, i): l = [Link](i)
r = [Link](i)
if (l <= [Link]() - 1 and [Link](l) > [Link](i)): largest = l
else:
largest = i
if (r <= [Link]() - 1 and [Link](r) > [Link](largest)): largest = r
if (largest != i):
[Link](largest, i)
self.max_heapify(largest)
def swap(self, i, j):
[Link][i], [Link][j] = [Link][j], [Link][i]
def insert(self, key): index = [Link]()
[Link](key)
while (index != 0):
 p = [Link](index)
if [Link](p) <
[Link](index):
[Link](p, index)
index = p bheap = BinaryHeap()
print('Menu')
print('insert
<data>')
print('max get')
print('max
extract')
print('quit')
while True:
do = input('What would you like to do? ').split()
operation = do[0].strip().lower() if operation == 'insert':
data = int(do[1]) [Link](data)
elif operation == 'max':
suboperation =
do[1].strip().lower() if
suboperation == 'get':
print('Maximum value: {}'.format(bheap.get_max()))
elif suboperation == 'extract':
print('Maximum value removed: {}'.format(bheap.extract_max()))
elif operation == 'quit': break
OUTPUT:

Case 1:
Menu
insert
<data>
max get
max
extract
quit
What would you like to do? insert 5
What would you like to do? insert 3
What would you like to do? insert -
3 What would you like to do? insert
10 What would you like to do?
insert 8 What would you like to do?
max get Maximum value: 10
What would you like to do? max
extract Maximum value removed: 10
What would you like to do? max
extract Maximum value removed: 8
What would you like to do? max
extract Maximum value removed: 5
What would you like to do? max
extract Maximum value removed: 3
What would you like to do? max
get Maximum value: -3
What would you like to do? quit

Case 2:
Menu
insert
<data>
max get
max
extract
quit
What would you like to do? insert 3What would you like to do? insert 11 What would you like to do? insert 5
What would you like to do? max extract Maximum value removed: 11
What would you like to do? max
get Maximum value: 5
What would you like to do? max
extract Maximum value removed: 5
What would you like to do? insert 15
What would you like to do? max get
Maximum value: 15
What would you like to do? quit

RESULT:

Thus the program has been executed successfully.

 EX:NO:12 GRAPH REPRESENTATION AND TRAVERSAL
ALGORITHM DATE:

AIM:
To write a Python program to implement depth first search. and breadth first search.
ALGORITHM:
DFS:
Step 1 - Define a Stack of size total number of vertices in the graph.
Step 2 - Select any vertex as starting point for traversal. Visit that vertex and push it on to the
Stack. Step 3 - Visit any one of the non-visited adjacent vertices of a vertex which is at the top of
stack and push it on to the stack.
Step 4 - Repeat step 3 until there is no new vertex to be visited from the vertex which is at the top of the
stack.
Step 5 - When there is no new vertex to visit then use back tracking and pop one vertex from the stack.
Step 6 - Repeat steps 3, 4 and 5 until stack becomes Empty.
Step 7 - When stack becomes Empty, then produce final spanning tree by removing unused edges from the
graph
PROGRAM:
Depth First Search Program
from collections import
defaultdict class Graph:
def init (self):
[Link] = defaultdict(list)
def addEdge(self, u, v):
[Link][u].append(v)
def DFSUtil(self, v,
visited): [Link](v)
print(v, end=' ')
for neighbour in
[Link][v]: if neighbour
not in visited:
[Link](neighbour,
visited) def DFS(self, v):
visited = set() [Link](v, visited)
g = Graph()
[Link](0, 1)
[Link](0, 2)
[Link](1, 2)
[Link](2, 0)
[Link](2, 3)
[Link](3, 3)
print("Following is DFS from (starting from vertex 2)")
[Link](2)
OUTPUT:
Depth First Traversal (starting from vertex 2)
20193

Breadth First Search

Algorithm:
Step 1 - Define a Queue of size total number of vertices in the graph.
Step 2 - Select any vertex as starting point for traversal. Visit that vertex and insert it into the Queue.
Step 3 - Visit all the non-visited adjacent vertices of the vertex which is at front of the Queue and insert them
into the Queue.
Step 4 - When there is no new vertex to be visited from the vertex which is at front of the Queue then delete
that vertex.
Step 5 - Repeat steps 3 and 4 until queue becomes empty.
Step 6 - When queue becomes empty, then produce final spanning tree by removing unused edges from the
graph
Program:
from collections import defaultdict
class Graph:
def init (self):
[Link] =
defaultdict(list) def
addEdge(self,u,v):
[Link][u].append(v)
def BFS(self, s):
visited = [False] * (max([Link]) + 1)
queue = []
[Link](s) visited[s] = True
while queue:
s = [Link](0) print (s, end = " ") for i in [Link][s]:
if visited[i] == False: [Link](i) visited[i] = True
g = Graph()
[Link](0, 1)
[Link](0, 2)
[Link](1, 2)
[Link](2, 0)
[Link](2, 3)
[Link](3, 3)
print ("Following is Breadth First Traversal" " (starting from vertex 2)")
[Link](2)

OUTPUT:

Breadth First Traversal (starting from vertex 2)

2031

RESULT:
Thus, the Python program to implement depth first search. and breadth first search has been
executed successfully.
 EX:NO:13 SINGLE SOURCE SHORTEST PATH ALGORITHM

DATE:
Aim:
To implement single source shortest path algorithm using Bellman Ford Algorithm
Algorithm:
This step initializes distances from source to all vertices as infinite and distance to source itself as 0.
Create an array dist[] of size |V| with all values as infinite except dist[src] where src is source vertex.
This step calculates shortest distances.
Do following |V|-1 times where |V| is the number of vertices in given graph.
a) Do following for each edge u-v
If dist[v] > dist[u] + weight of edge uv, then update dist[v] dist[v] = dist[u] + weight of edge uv
This step reports if there is a negative weight cycle in graph.
Do following for each edge u-v If dist[v] > dist[u]+ weight of edge uv, then “Graph contains negative weight
cycle”
The idea of step 3 is, step 2 guarantees shortest distances if graph doesn’t contain negative weight cycle.
If we iterate through all edges one more time and get a shorter path for any vertex, then there is a negative
weight cycle
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):
if dis[graph[j][0]] + \
graph[j][2] < dis[graph[j][1]]:
dis[graph[j][1]] = dis[graph[j][0]] + \
graph[j][2]
for i in range(E): x = graph[i][0]
y = graph[i][1]
weight =
graph[i][2]
if dis[x] != maxsize and dis[x] + \
weight < dis[y]:
print("Graph contains negative weight cycle") print("Vertex Distance from Source")
for i in range(V): print("%d\t\t%d" % (i, dis[i]))
if name == " main ":
V = 5 # Number of vertices in graph
E = 8 # Number of edges in graph
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

Result:
Thus the Implementation of single source shortest path algorithm was successfully executed.
 EX:NO:14 MINIMUM SPANNING TREE

IMPLEMENTATION DATE:

Aim:
To implement the minimum spanning tree algorithms using Kruskal Algorithm
Algorithm:
1. Label each vertex
2. List the edges in non-decreasing order of weight.
[Link] with the smallest weighted and beginning growing the minimum weighted spanning tree from
this edge.
4. Add the next available edge that does not form a cycle to the construction of the minimum
weighted spanning tree. If the addition of the next least weighted edge forms a cycle, do not use it.
[Link] with step 4 until you have a spanning tree.
Coding:
class Graph:
def init (self, vertices): self.V =
vertices [Link] = []
def add_edge(self, u, v, w): [Link]([u, v, w])
def find(self, parent, i):
return [Link](parent, parent[i])
def apply_union(self, parent, rank, x, y): xroot =
[Link](parent, x)
yroot = [Link](parent, y) if
rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot rank[xroot] +=
1 def kruskal_algo(self):
result =[]
i, e = 0, 0
[Link] = sorted([Link], key=lambda item: item[2]) parent =
[] rank = []
for node in range(self.V): [Link](node) [Link](0)
while e < self.V - 1:
u, v, w = [Link][i] i = i + 1
x = [Link](parent, u) y
= [Link](parent, v) if x != y:
e = e + 1 [Link]([u, v, w])
self.apply_union(parent, rank, x, y) for u, v,
weight in result:
print("%d - %d: %d" % (u, v, weight)) g =
Graph(6)
g.add_edge(0, 1, 4)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 2)
g.add_edge(1, 0, 4)
g.add_edge(2, 0, 4)
g.add_edge(2, 1, 2)
 g.add_edge(2, 3, 3)
g.add_edge(2, 5, 2)
g.add_edge(2, 4, 4)
g.add_edge(3, 2, 3)
g.add_edge(3, 4, 3)
g.add_edge(4, 2, 4)
g.add_edge(4, 3, 3)
g.add_edge(5, 2, 2)
g.add_edge(5, 4, 3)
g.kruskal_algo()

Output:
1 - 2: 2
2 - 5: 2
2 - 3: 3
3 - 4: 3
0 - 1: 4

Result:
Thus the program was executed successfully.