SSM INSTITUTE OF ENGINEERING AND TECHNOLOGY

(Approved by AICTE, New Delhi / Affiliated to Anna University / Accredited by NAAC)

Dindigul – Palani Highway, Dindigul – 624 002.

DEPARTMENT OF COMPUTER SCIENCE AND BUSINESS SYSTEM

LAB MANUAL

COURSE CODE AD3271

DATA STRUCTURES DESIGN LABORATORY

COURSE NAME

REGULATION 2021 R

YEAR/SEM I/II

Prepared by,

D.Devi Shree AP/CSE

1
SSM INSTITUTE OF ENGINEERINGAND
TECHNOLOGY
Dindigul- Palani Highway, Dindigul – 624 002.

DEPARTMENT OF COMPUTER SCIENCE AND BUSINESS SYSTEM

Vision
To grow as an eminent department with excellence in computing and research by integrating
computer and information technology to develop products and services for the benefit of the society

with ethical values.

Mission
 To instill in students the urge to learn by imparting finest quality education.
 To impart good attitude and integrate creativity and research orientation.
 To initiate interest and equip students to design and develop intelligent products.
 To inculcate the desire to serve the society with ethical values.

Programme Educational Objectives

Graduates of Computer Science and Engineering Programme will:
PEO Program Educational Outcome(s)
Technical Proficiency
Advance professionally to roles of greater computer engineering responsibilities in
PEO.1 Government and private organizations, through providing solutions to challenging
problems in their profession by applying computer engineering theory and principles.
Continuous Educational growth
Engage in life-long learning through successful completion of post graduate programs in
PEO.2
engineering and interdisciplinary areas to emerge as researchers, experts, and educators.
Managerial Skills
Develop and refine their knowledge to provide exposure to emerging cutting-edge
PEO.3 technologies, adequate training and opportunities to work as teams on multidisciplinary
Projects with effective communication skills and leadership qualities.
Service to the society
Establish a commitment to the society by applying technical skills and knowledge to
PEO.4
support various service activities.

2
PO Program Outcome(s)
PO 01 # Engineering knowledge
PO 02 # Problem analysis
PO 03 # Design/development of solutions
PO 04 # Conduct investigations of complex problems
PO 05 # Modern tool usage
PO 06 # The engineer and society
PO 07 # Environment and sustainability
PO 08 # Ethics
PO 09 # Individual and team work
PO 10 # Communication
PO 11 # Project management and finance
PO 12 # Life-long learning

Programme Specific Outcomes

At the end of the Programme graduate will be able to
PSO Description
PSO.1 Understand the principles of basic engineering and acquire the hardware and
software aspects of computer science and engineering.
PSO.2 Design and develop applications or products using various programming
languages.

3
AD3271 – DATA STRUCTURES DESIGN LABORATORY LTPC
202 3

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: 30 PERIODS

OUTCOMES:

3|N I E T
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.

4|N I E T
CONTENTS
S.No. 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

5|N I E T
14 MINIMUM SPANNING TREE
IMPLEMENTATION

6|N I E T
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 self.n.append(a)
def remove(self,b):
self.n.remove(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: "))
obj.add(n)
print("List: ",obj.dis())
elif choice==2:
n=int(input("Enter number to remove: "))
obj.remove(n)
print("List: ",obj.dis())
elif choice==3:
print("List: ",obj.dis())
elif choice==0:
print("Exiting!")
else:
print("Invalid choice!!")
print()

7|N I E T
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
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
2. Delete

8|N I E T
3. Display
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.

9|N I E T
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.

10 | N I E T
EX.NO: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:

11 | N I E T
Thus, the Python program determines the towers of hanoi using recursion has been
implemented successfully.

EX.NO: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))

12 | N I E T
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.

13 | N I E T
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 = array.array('i', [1, 2, 3])
print ("The new created array is : ",end=" ")
for i in range (0, 3):
print (arr[i], end=" ")
print("\r")
arr.append(4);
print("The appended array is : ", end="")
for i in range (0, 4):
print (arr[i], end=" ")
arr.insert(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.

14 | N I E T
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)
List.extend([8, 'Geeks', 'Always'])
print("\nList after performing Extend Operation: ")
print(List)
List = []
print("Blank List: ")
print(List)
List = [10, 20, 14]
print("\nList of numbers: ")
print(List)
List = ["Geeks", "For", "Geeks"]
print("\nList Items: ")
print(List[0])
print(List[2])
Adding the elements:
List = [1,2,3,4]
print("Initial List: ")
print(List)
List.insert(3, 12)
List.insert(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)

15 | N I E T
List.remove(5)
List.remove(6)
print("\nList after Removal of two elements:
") print(List)
for i in range(1, 5):
List.remove(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 1.py
=====================
Initial List:
[1, 2, 3, 4]
List after performing Insert Operation:
['Geeks', 1, 2, 3, 12, 4]
>>>
===================== RESTART: Z:/New folder/queue 1.py
=====================
Intial 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.

16 | N I E T
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):
self.data = data
self.next = None
class Stack:
def init (self):
self.head = None

def push(self, data):

if self.head is None:
self.head = Node(data)
else:
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def pop(self):
if self.head is None:
return None
else:
popped = self.head.data
self.head = self.head.next
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':
17 | N I E T
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>
pop
quit
What would you like to do? push 3
push <value>
pop
quit
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.

18 | N I E T
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):
self.data = data
self.next = None

class Queue:
def init (self):
self.head = None
self.last = None

def enqueue(self, data):

if self.last is None:
self.head = Node(data)
self.last = self.head
else:
self.last.next = Node(data)
self.last = self.last.next

def dequeue(self):
if self.head is None:
return None
else:
to_return =
self.head.data self.head =
self.head.next return
to_return

a_queue = Queue()
while True:
print('enqueue <value>')
print('dequeue')
19 | N I E T
print('quit')

20 | N I E T
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>
dequeue
quit
What would you like to do? enqueue 4
enqueue <value>
dequeue
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 empty.
21 | N I E T
enqueue <value>
dequeue
quit
What would you like to do? enqueue 5
enqueue <value>
dequeue
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.

22 | N I E T
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)
23 | N I E T
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.

24 | N I E T
B. APPLICATIONS OF STACK ADT

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):
self.items = []

def is_empty(self):
return self.items == []

def push(self, data):

self.items.append(data)

def pop(self):
return self.items.pop()

s = Stack()
exp = input('Please enter the expression: ')

for c in exp:
if c == '(':
s.push(1)
elif c == ')':
if s.is_empty():
is_balanced = False
break
s.pop()
else:
if s.is_empty():
is_balanced = True
else:
is_balanced = False

if is_balanced:
print('Expression is correctly parenthesized.')
25 | N I E T
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.

26 | N I E T
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)

27 | N I E T
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:

1 10 Burst
Processes 0 time
10 Waiting time Turn around time
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

28 | N I E T
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.

29 | N I E T
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.

30 | N I E T
31 | N I E T
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.
32 | N I E T
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):
self.left = None
self.right = None
self.val = key
def printInorder(root):

if root:
printInorder(root.left)
print(root.val),
printInorder(root.right)

33 | N I E T
def printPostorder(root):

if root:
printPostorder(root.left)
printPostorder(root.right)
print(root.val),
def printPreorder(root):

if root:
print(root.val),
printPreorder(root.left)
printPreorder(root.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print "Preorder traversal of binary tree is"
printPreorder(root)

print "\nInorder traversal of binary tree is"

printInorder(root)

print "\nPostorder traversal of binary tree is"

printPostorder(root)

OUTPUT:

Preorder traversal of binary tree is

12453
Inorder traversal of binary tree is
42513
Postorder traversal of binary tree is
45231

RESULT:

Thus, the python program to implement the concept of tree representation and traversal algorithm.
has been implemented successfully.
34 | N I E T
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")

35 | N I E T
OUTPUT:
40 Found at index 3

RESULT:

Thus, the python program to implement the concept of binary search tree has been implemented
successfully.

36 | N I E T
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):
self.items = []

def size(self):
return len(self.items)

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 self.items[i]

37 | N I E T
def get_max(self):
if self.size() ==
0:
return None
return self.items[0]

def extract_max(self):
if self.size() == 0:
return None
largest = self.get_max()
self.items[0] = self.items[-1]
del self.items[-1]
self.max_heapify(0)
return largest

def max_heapify(self, i):

l = self.left(i)
r = self.right(i)
if (l <= self.size() - 1 and self.get(l) > self.get(i)):
largest = l
else:
largest = i
if (r <= self.size() - 1 and self.get(r) > self.get(largest)):
largest = r
if (largest != i):
self.swap(largest, i)
self.max_heapify(largest)

def swap(self, i, j):

self.items[i], self.items[j] = self.items[j], self.items[i]

def insert(self, key):

index = self.size()
self.items.append(key)

while (index != 0):

p = self.parent(index)
if self.get(p) < self.get(index):
self.swap(p, index)
index = p

bheap = BinaryHeap()

print('Menu')
print('insert <data>')
print('max get')
print('max extract')
print('quit')

while True:
38 | N I E T
do = input('What would you like to do? ').split()

39 | N I E T
operation = do[0].strip().lower()
if operation == 'insert':
data = int(do[1])
bheap.insert(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 3
40 | N I E T
What 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:
To write a python program that creates a binary max-heap and presents a menu to the user to
perform various operations on it. has been implemented successfully.

41 | N I E T
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):

self.graph = defaultdict(list)

def addEdge(self, u, v):

self.graph[u].append(v)

def DFSUtil(self, v, visited):

visited.add(v)
print(v, end=' ')
42 | N I E T
for neighbour in self.graph[v]:
if neighbour not in visited:
self.DFSUtil(neighbour, visited)

def DFS(self, v):

visited = set()
self.DFSUtil(v, visited)

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 DFS from (starting from vertex 2)")

g.DFS(2)

OUTPUT:

Depth First Traversal (starting from vertex

2) 2 0 1 9 3

Breadth First Search Program;

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

43 | N I E T
Program:

from collections import defaultdict

class Graph:
def init (self):

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

def BFS(self, s):

visited = [False] * (max(self.graph) + 1)
queue = []
queue.append(s)
visited[s] = True

while queue:
s = queue.pop(0)
print (s, end = " ")
for i in self.graph[s]:
if visited[i] == False:
queue.append(i)
visited[i] = True
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)

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.

44 | N I E T
45 | N I E T
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

Coding:
from sys import maxsize
def BellmanFord(graph, V, E, src):
dis = [maxsize] * V
dis[src] = 0
for i in range(V - 1):
for j in range(E):
if dis[graph[j][0]] + \
graph[j][2] < dis[graph[j][1]]:
dis[graph[j][1]] = dis[graph[j][0]] + \
graph[j][2]
for i in range(E):
x = graph[i][0]
y = graph[i][1]
weight = graph[i][2]
if dis[x] != maxsize and dis[x] + \
weight < dis[y]:
print("Graph contains negative weight cycle")
print("Vertex Distance from Source")

46 | N I E T
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.

47 | N I E T
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.
3. Start 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.
5. Continue with step 4 until you have a spanning tree.
Coding:
class Graph:
def init (self, vertices): self.V =
vertices self.graph = []
def add_edge(self, u, v, w): self.graph.append([u, v, w])
def find(self, parent, i):
return self.find(parent, parent[i])
def apply_union(self, parent, rank, x, y): xroot =
self.find(parent, x)
yroot = self.find(parent, y) if
rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot rank[xroot] +=
1
def kruskal_algo(self): result = []
i, e = 0, 0
self.graph = sorted(self.graph, key=lambda item: item[2]) parent = []
rank = []
for node in range(self.V):
parent.append(node) rank.append(0)
while e < self.V - 1:
u, v, w = self.graph[i] i = i + 1
x = self.find(parent, u) y =
self.find(parent, v) if x != y:
e = e + 1 result.append([u, v, w])
self.apply_union(parent, rank, x, y) for u, v,
48 | N I E T
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.

49 | N I E T