Jayalakshmi Institute of

Technology
NH7, SalemMainRd, T. Kanigarahalli, Thoppur, Dharmapuri, Tamil Nadu636

CS3691- EMBEDDED SYSTEMS AND IOT LAB

MANUAL

(FOR II B.TECH ARTIFICIAL INTELLIGENCE AND DATA SCIENCE

STUDENTS)

NAME :
REGISTER NO :
YEAR/SEMESTER :
ACADEMIC YEAR :

AS PER ANNA UNIVERSITY (CHENNAI) SYLLABUS

2021 REGULATION
 ABOUT OBSERVATION NOTES & PREPARATION OF RECORD

1. Students are advised to come to the laboratory at least 5 minutes before (to the starting time), those who
come after 5 minutes will not be allowed into the lab.
2. Student should enter into the laboratory with:
a. Laboratory observation notes with all the details (Problem statement, Aim, Algorithm, Procedure,
Program, Expected Output, etc.,) filled in for the lab session.
b. Laboratory Record updated up to the last session experiments and other utensils (if any) needed in the lab.
c. Proper Dress code and Identity card.
d. Sign in the laboratory login register, write the TIME-IN, and occupy the computer system allotted to you
by the faculty.
3. Execute your task in the laboratory, and record the results / output in the lab observation note book, and get
certified by the concerned faculty.
4. All the students should be polite and cooperative with the laboratory staff, must maintain the discipline and
decency in the laboratory.
5. Computer labs are established with sophisticated and high-end branded systems, which should be utilized
properly.
6. Students / Faculty must keep their mobile phones in SWITCHED OFF mode during the lab sessions with the
staff and systems etc., will attract severe punishment.
7. Students must take the permission of the faculty in case of any urgency to go out; if anybody found loitering
outside the lab / class without permission during working hours will be treated seriously and punished
appropriately.
8. Students should LOG OFF/ SHUT DOWN the computer system before he/she leaves the lab after
completing the task (experiment) in all aspects. He/she must ensure the system / seat is kept properly.
9. This Observation contains the basic diagrams of the circuits enlisted in the syllabus of the CS3691
EMBEDDED SYSTEMS AND IOT course, along with the design of various components of the circuit and
controller.
10. The aim of the experiment is also given at the beginning of each experiment. Once the student can design the
circuit as per the circuit diagram, he/she is supposed to go through the instructions carefully and do the
experiments step by step.
11. They should get their observations verified and signed by the staff within two days and prepare & submit the
record of the experiment when they come to the laboratory in the subsequent week.
12. The record should contain experiment No., Date, Aim, Apparatus required, Theory, Procedure, and result on
one side (i.e., Right-hand side, where rulings are provided) and Circuit diagram, Design, Model Graphs,
Tabulations, Calculations. Pre-Lab and Post Lab questions on the other side (i.e., Left-hand side, where
black space are provided)
13. The students are directed to discuss & clarify their doubts with the staff members as and when required.
They are also directed to follow strictly the guidelines specified.
 Jayalakshmi Institute of
Technology
Thoppur, Dharmapuri, Tamil Nadu 636 352.

BONAFIDE CERTIFICATE

Name: ………………………………………………………………………..
Academic Year:………………….. Semester:…………… Branch:……………….

Register No.

Certified that this is the bonafide record of work done by the above student in the

… Laboratory during the year

202 - 202.

Signature of Faculty in-charge

Submitted for the Practical Examination held on …………………………………….

Internal Examiner External Examiner

 Jayalakshmi Institute of
Technology
NH7, SalemMainRd, T. Kanigarahalli, Thoppur, Dharmapuri, Tamil Nadu636
Department of Artificial intelligence And Data Science
VISION

To evolve as a Centre of Academic Excellence and Advanced Research in the field of

Computer Science and Engineering and develop professionals who can meet with the
societal issues.

MISSION

 To provide a good environment with latest technological infrastructure facilities,

teaching-learning ambience and interaction with industry in the area of Computer
Science and Engineering.
 To develop graduates of world class technical competence, entrepreneurial skill and
to encourage for higher education in the area of Computer Science and Engineering,
with necessary skills to solve real world problems.
 To inculcate graduates with high social responsibility, right attitude, discipline and
an inclination towards offering their professional expertise in serving the society.

Program Educational Objectives (PEO):

PEO 1.Apply the principles and practices of Computer Science and Engineering
encompassing Mathematics, Science and Basic Engineering and to employ the modern
engineering tools effectively in their profession with their world class technical
competence.
PEO 2.Possess expertise to function as members of multi-disciplinary teams and
implement software technology solutions for real world problems of international
standards and will be achievers at global level.
PEO 3.Excel in the field of software industry or in higher studies endowed with the spirit
of innovation and entrepreneurship by evolving their professional knowledge on a lifelong
basis.
PEO 4.Practice the profession with ethics, integrity, leadership and social responsibility
with a good insight of the changing societal needs for the benefit of humanity.
Program Outcomes (POs)
Computer Science and Engineering Graduates will be able to:

PO1: Engineering knowledge: Apply the knowledge of mathematics, science,

engineering fundamentals, and an engineering specialization to the solution of complex
engineering problems.

PO2: Problem analysis: Identify, formulate, review research literature, and analyze
complex engineering problems reaching substantiated conclusions using first principles
of mathematics, natural sciences, and engineering sciences.

PO3: Design/development of solutions: Design solutions for complex engineering

problems and design system components or processes that meet the specified needs with
appropriate consideration for the public health and safety, and the cultural, societal, and
environmental considerations.

PO4: Conduct investigations of complex problems: Use research-based knowledge

and research methods including design of experiments, analysis and interpretation of
data, and synthesis of the information to provide valid conclusions.

PO5: Modern tool usage: Create, select, and apply appropriate techniques, resources,
and modern engineering and IT tools including prediction and modeling to complex
engineering activities with an understanding of the limitations.

PO6: The engineer and society: Apply reasoning informed by the contextual knowledge
to assess societal, health, safety, legal and cultural issues and the consequent
responsibilities relevant to the professional engineering practice.

PO7: Environment and sustainability: Understand the impact of the professional

engineering solutions in societal and environmental contexts, and demonstrate the
knowledge of, and need for sustainable development.

PO8: Ethics: Apply ethical principles and commit to professional ethics and
responsibilities and norms of the engineering practice.

PO9: Individual and team work: Function effectively as an individual, and as a

member or leader in diverse teams, and in multidisciplinary settings.
PO10: Communication: Communicate effectively on complex engineering activities with
the engineering community and with society at large, such as, being able to comprehend
and write effective reports and design documentation, make effective presentations,
and give and receive clear instructions.

PO11: Project management and finance: Demonstrate knowledge and understanding

of the engineering and management principles and apply these to one’s own work, as a
member and leader in a team, to manage projects and in multidisciplinary
environments.

PO12: Life-long learning: Recognize the need for, and have the preparation and ability
to engage in independent and life-long learning in the broadest context of technological
change.

PROGRAMME SPECIFIC OUTCOMES (PSOs)

PSO1: Apply knowledge acquired from the basic hardware design and software core areas
of Computer Science and Engineering for solving real world problems.

PSO2: Apply cutting edge technologies and strong analytical skills to develop quality
software in scientific and business applications for the betterment of society and
Industry.

PSO3: Employ modern computer languages, environments and platforms in creating

innovative career paths to be an entrepreneur and with a zeal for higher studies.
 AD3271– DATA STRUCTURES DESIGN LABORATORY
COURSE OBJECTIVES:
 To implement ADTs in Python.
 To design and implement linear data structures – lists, stacks, and queues
 To implement sorting, searching and hashing algorithms
 To solve problems using tree and graph structures
LIST OF EXPERIMENTS

PRACTICAL EXERCISES: TOTAL: 6 0 PERIODS

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 algorithms
15.Content beyond Syllabus
OUTCOMES:
CO1: implement ADTs as Python classes.
CO2: Design, implement, and analyze linear data structures, such as lists,
queues, and stacks, according to the needs of different applications.
CO3: Design, implement, and analyze efficient tree structures to meet
requirements such as searching, indexing, and sorting.
CO4: Model problems as graph problems and implement efficient graph algorithms
to solve them
.

7
8
 INDEX
Page Marks
S.No. Date Name of the Experiment Sign
No. Awarded

10

11

12

13

14

15

16

17

Average Marks:

9
Sample Output:

INPUT OUTPUT

10
 EXP NO: 1
Write a Program to Implement the simple ADTs as Python
DATE: classes

Aim. To Implement simple ADTs as Python classes using Stack, Queue, List using python.

Algorithm:
1. Create a Stack[ ],Queue[],List[] with MAX size as your wish.
2. Write function for all the basic operations of stack, Queue, List - PUSH(), POP() and
DISPLAY(),append(),Extend().
3. Close the program

Coding :
Stack:
stack = []
stack.append('a')
stack.append('b')
stack.append('c')
print('Initial stack')
print(stack)
print('\nElements poped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())
print('\nStack after elements are poped:')
print(stack)

Queue:
queue = []
queue.append('a')
queue.append('b')
queue.append('c')
print("Initial queue")
print(queue)
print("\nElements dequeued from queue")
print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))
print("\nQueue after removing elements")
print(queue)

11
List:
List = [1,2,3,4]
print("Initial List: ")
print(List)
List.extend([8, 'Geeks', 'Always'])
print("\nList after performing Extend Operation: ")
print(List)

Output:
Stack:
Initial stack ['a',
'b', 'c']
Elements poped from stack: c
ba
Stack after elements are poped: []
Queue:
['a', 'b', 'c']
Elements dequeued from queue a
bc
Queue after removing elements []
List:
Initial List:
[1, 2, 3, 4]
List after performing Extend
Operation: [1, 2, 3, 4, 8, 'Geeks',
'Always']

12
Pre-lab questions:

1. What is an Abstract Data Type (ADT)?

2. What is the difference between an ADT and a data structure?
3. What operations are typically associated with a Stack ADT?
4. What operations are typically associated with a Queue ADT?
5. What are the differences between a singly linked list and a doubly linked list?

Post Lab Questions:

1. Explain how a Stack ADT works.

2. What are the main advantages of using a Deque over a regular Queue?
3. How does a Priority Queue manage the elements compared to a regular Queue?
4. How does a dynamic Array List compare with a static array in terms of flexibility
and resizing?
5. Explain the concept of push, pop, and peek operations in the Stack ADT.

MARKS ALLOCATION

Details Marks Marks

Allotted Awarded
Pre Lab Questions 10
Aim & Procedure 30
Coding 30
Execution & Output 20
Post Lab 10
Questions(Viva)
Total 100

Result:
Thus the Implementation of simple ADTs as Python classes was executed successfully.

13
 EXP NO: 2
Write a Program to Implement the recursive algorithms in
DATE: Python

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

Algorithm:
Step 1: Input the 'n' value until which the Fibonacci series has to be generated

Step 2: Initialize sum = 0, a = 0, b = 1 and count = 1

Step 3: while (count <= n)

Step 4: print sum

Step 5: Increment the count variable

Step 6: swap a and b

Step 7: sum = a + b

Step 8: while (count > n) Step

Step 9: End the algorithm Step

Step 10: Else

Step 11: Repeat from steps 4 to 7

Coding:
No = 10
num1, num2 = 0, 1
count = 0 if No
<= 0:
print("Invalid Number") elif
No == 1:
print("Fibonacci sequence for limit of ",No,":")
print(num1)
else:
print("Fibonacci sequence:")
while count < No:
14
 print(num1)
nth = num1 + num2
num1 = num2
num2 = nth
count += 1

Output:
Fibonacci sequence:
0
1
1
2
3
5
8
13
21
34

15
Pre-lab questions:

1. What is recursion?
2. What is the recursive case in a recursive function?
3. What are some advantages and disadvantages of recursion?
4. What is the base case in a recursive function?
5. How do you identify when a problem is suited for recursion?
Post Lab Questions:

1. Explain the process of recursion with an example.

2. What is the time complexity of the recursive algorithm for calculating factorial?
3. Explain how the recursive approach for Fibonacci works.
4. What is the difference between recursion and iteration for solving problems?
5. How does recursion handle problems with multiple subproblems, like tree traversal?

MARKS ALLOCATION

Details Marks Marks

Allotted Awarded
Pre Lab Questions 10
Aim & Procedure 30
Coding 30
Execution & Output 20
Post Lab 10
Questions(Viva)
Total 100

Result:
Thus the Implementation of recursive algorithms in Python using Fibonacci series was executed
successfully.

16
 EXP NO: 3
Write a Program to Implement List ADT using Python
DATE: arrays

Aim:
To Implement List ADT using Python arrays

Algorithm
1. Using define function initialize the list
2. while loop to declare the elements until the condition is satisfied.
3. using converter function to convert the elements to an array
Stop the program

Coding:

class node:
def init (self, data):
self.data=data
self.next=None
def add(data):
nn=node(0)
nn.data=data
nn.next=None
return nn
def
printarray(a,n):
i=0
while(i<n):
print(a[i], end = "
") i=i+1
def
findlength(head)
: cur=head
count=0
while(cur!
=None):
count=count+1

cur=cur.next
return count
def convertarr(head):

17
 index=0
cur=hea
d
while(cur!=None):
arr.append(cur.data)
cur=cur.next
printarray(arr,
len) head=node(0)
head=add(6)
head.next = add(4)
head.next.next = add(3)
head.next.next.next = add(4)
convertarr(head)

Output:
[6,4,3,4]
[6 4 3 4]

18
Pre-lab questions:

1. What is a List ADT?

2. What are the main operations of a List ADT?
3. What is the difference between a list and an array?
4. What are the advantages of using a list as an ADT?
5. What are the time complexities of different operations in a List ADT (insert,
delete, get)?

Post Lab Questions:

1. What operations are supported by a List ADT?

2. Explain how an array-based List is different from a linked list.
3. What is the time complexity of accessing an element by index in an array-based List?
4. Explain how the delete operation works in an array-based List.
5. What are the advantages of using an array-based List over a linked list?

MARKS ALLOCATION

Details Marks Marks

Allotted Awarded
Pre Lab Questions 10
Aim & Procedure 30
Coding 30
Execution & Output 20
Post Lab 10
Questions(Viva)
Total 100

Result:
Thus the implementation of List in arrays was executed successfully.

19
 EXP NO: 4
Write a Program to 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
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)
List.remove(5)
List.remove(6)
print("\nList after Removal of two elements: ")

20
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]

Pre-lab questions:
21
 1. What is a Linked List?
2. What are the main types of Linked Lists?
3. How is a Linked List different from an array or an array-based list?
4. What are the advantages and disadvantages of Linked Lists?
5. What is the difference between singly linked lists and doubly linked lists?

Post Lab Questions:

1. What operations are supported by a Linked List ADT?
2. Explain how inserting an element at the head, tail, and in the middle works in a
singly linked list.
3. What are the advantages of using a Linked List over an array-based List?
4. What is the time complexity of searching for an element in a Linked List?
5. What is a circular linked list, and how does it differ from a regular linked list?

MARKS ALLOCATION

Details Marks Marks

Allotted Awarded
Pre Lab Questions 10
Aim & Procedure 30
Coding 30
Execution & Output 20
Post Lab 10
Questions(Viva)
Total 100

Result:
Thus the list was created, inserted, removed and extend the element was executed successfully.

EXP NO: 5

22
 DATE:
Write a Program to Implementation of Stack and Queue
ADTs

Aim:
To Implementation of Stack and Queue ADTs

Algorithm:

1. Create a Stack[ ],Queue[] with MAX size as your wish.

2. Write function for all the basic operations of stack - append(), POP()
3. Close the program.

Coding:
stack = []
stack.append('a')
stack.append('b')
stack.append('c')
print('Initial stack')
print(stack)
print('\nElements poped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())
print('\nStack after elements are poped:')
print(stack)

Queue:
queue = []
queue.append('a')
queue.append('b')
queue.append('c')
print("Initial queue")
print(queue)
print("\nElements dequeued from queue")
print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))
print("\nQueue after removing elements")
print(queue)

23
Output:
Initial stack ['a', 'b', 'c']
Elements poped from stack:
cba
Stack after elements are poped: []

24
Pre-lab questions:

1. What is a Stack ADT?

2. What are the main operations of a Stack?
3. What is a Queue ADT?
4. What are the main operations of a Queue?
5. What is the LIFO (Last In, First Out) property of a Stack?

Post Lab Questions:

1. Explain the implementation of a Stack using an array or linked list.

2. How do you implement a Queue using an array or linked list?
3. What are the time complexities of queue operations (enqueue, dequeue, peek)?
4. How does the Stack ADT work in recursion?
5. What are the advantages of using a Stack over other data structures?

MARKS ALLOCATION

Details Marks Marks

Allotted Awarded
Pre Lab Questions 10
Aim & Procedure 30
Coding 30
Execution & Output 20
Post Lab 10
Questions(Viva)
Total 100

Result:
Thus the program was executed successfully

25
 EXP NO: 6 a Write a Program to implement the Application of List
DATE: using Polynomial Addition in python

Aim:
To implement list application using Polynomial Addition in python

Algorithm:
1. Using the define function intial elements will be declared.
2. for loop gives the output of sum of the elements
3. print[poly] statement have the sum of two polynomial elements.
4. Close the program

Coding:

students = ['John', 'Alice', 'Bob', 'Sarah', 'Michael']

grades = [85, 90, 78, 92, 88]

# 1. Displaying the list of students and their grades

print("Student Grades List:")
for i in range(len(students)):
print(f"{students[i]}: {grades[i]}")

# 2. Adding a new student and their grade

students.append('Emma')
grades.append(95)
print("\nAfter adding a new student:")
for i in range(len(students)):
print(f"{students[i]}: {grades[i]}")

# 3. Updating a student's grade

grades[students.index('Bob')] = 80
print("\nAfter updating Bob's grade:")
for i in range(len(students)):
print(f"{students[i]}: {grades[i]}")

# 4. Removing a student from the list

student_to_remove = 'Alice'
index_to_remove = students.index(student_to_remove)
students.pop(index_to_remove)
grades.pop(index_to_remove)
print(f"\nAfter removing {student_to_remove}:")
for i in range(len(students)):
print(f"{students[i]}: {grades[i]}")

# 5. Sorting students based on grades (ascending order)

sorted_indices = sorted(range(len(grades)), key=lambda i: grades[i])
sorted_students = [students[i] for i in sorted_indices]
26
sorted_grades = [grades[i] for i in sorted_indices]
print("\nStudents sorted by grade (ascending):")
for i in range(len(sorted_students)):
print(f"{sorted_students[i]}: {sorted_grades[i]}")

# 6. Finding the student with the highest grade

max_grade = max(grades)
top_student = students[grades.index(max_grade)]
print(f"\nThe student with the highest grade is {top_student} with {max_grade}.")

# 7. Filtering students who scored above 85

high_achievers = [students[i] for i in range(len(grades)) if grades[i] > 85]
print("\nStudents who scored above 85:")
print(high_achievers)

Output:
Student Grades List:
John: 85
Alice: 90
Bob: 78
Sarah: 92
Michael: 88

After adding a new student:

John: 85
Alice: 90
Bob: 78
Sarah: 92
Michael: 88
Emma: 95

After updating Bob's grade:

John: 85
Alice: 90
Bob: 80
Sarah: 92
Michael: 88
Emma: 95

After removing Alice:

John: 85
Bob: 80
Sarah: 92
Michael: 88
Emma: 95

27
Students sorted by grade (ascending):
Bob: 80
John: 85
Michael: 88
Sarah: 92
Emma: 95

The student with the highest grade is Emma with 95.

Students who scored above 85:

['Sarah', 'Michael', 'Emma']

28
Pre-lab questions:

1. What are the applications of Lists in real-world programming scenarios?

2. Why are Lists a preferred data structure in Python for storing collections of data?
3. How do you access and manipulate elements in a List?
4. How can Lists be used to implement other data structures like stacks and
queues?
5. What are the advantages and limitations of using Lists in Python?

Post Lab Questions:

1. How can Lists be used to implement searching algorithms such as linear search or
binary search?
2. What are some practical use cases of Lists in sorting algorithms (e.g., Bubble
Sort, Merge Sort)?

3. Can Lists be used to simulate real-world systems, such as a to-do list or a customer
queue?
4. How can Lists be used to represent matrix operations, and what are the
advantages of doing so?

5. How can you optimize List operations when dealing with large datasets?

MARKS ALLOCATION

Details Marks Marks

Allotted Awarded
Pre Lab Questions 10
Aim & Procedure 30
Coding 30
Execution & Output 20
Post Lab 10
Questions(Viva)
Total 100

Result:
Thus the program was executed successfully.

EXP NO: 6 b

29
 DATE:
Write a Program to implement the Application of Stack

Aim:
To implement the conversion of infix to postfix in stack

Algorithm:
1. Read the given expression
2. check ifempty or not ,the stack will insert the elements.
3. Using push(),pop() to insert the element or remove the element.
4. Check the operator based on the precedence the expression will be evaluated
5. Close the program

Coding:
class Conversion:
def __init__(self, capacity):
self.top = -1
self.capacity = capacity
self.array = [] # stack to store operators
self.output = [] # list to store postfix expression
self.precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}

# Check if the stack is empty

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

# Peek the top element of the stack

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

# Pop the top element from the stack

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

# Push an element onto the stack

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

# Check if the character is an operand (letter or number)

def isOperand(self, ch):
return ch.isalpha()

# Compare precedence of operators

def notGreater(self, i):
try:
a = self.precedence[i]
30
 b = self.precedence[self.peek()]
return True if a <= b else False
except KeyError: # in case the operator is not in precedence dictionary
return False

# Convert infix to postfix

def infixToPostfix(self, exp):
for i in exp:
# If the character is an operand, add it to the output list
if self.isOperand(i):
self.output.append(i)
# If the character is '(', push it to the stack
elif i == '(':
self.push(i)
# If the character is ')', pop and output until '(' is encountered
elif i == ')':
while not self.isEmpty() and self.peek() != '(':
a = self.pop()
self.output.append(a)
if not self.isEmpty() and self.peek() != '(':
return -1
else:
self.pop() # remove '(' from the stack
# If the character is an operator, pop operators from the stack
else:
while not self.isEmpty() and self.notGreater(i):
self.output.append(self.pop())
self.push(i)

# Pop the remaining operators in the stack and append to output

while not self.isEmpty():
self.output.append(self.pop())

# Join and print the postfix expression

print("".join(self.output))

# Test the conversion with an example expression

exp = "a+b*(c^d-e)^(f+g*h)-i"
obj = Conversion(len(exp))
obj.infixToPostfix(exp)

Output:
abcd^e-fgh*+^*+i-

Pre-lab questions:

1. What is a Stack ADT, and how is it different from other data structures?
31
 2. What are the main operations of a Stack?
3. What are the practical applications of Stacks in real-world programming?
4. What is the role of a stack in the Undo/Redo feature in applications?
5. Why are stacks used for parsing expressions in compilers or calculators?

Post Lab Questions:

1. How can a stack be used to reverse a string?
2. Explain how stacks are used in evaluating arithmetic expressions (e.g., infix,
postfix).
3. What are the advantages of using a stack in managing function calls (e.g., in
recursion)?
4. How can a stack be used to check for balanced parentheses in an expression?
5. Can stacks be used for implementing the browser history feature?

MARKS ALLOCATION

Details Marks Marks

Allotted Awarded
Pre Lab Questions 10
Aim & Procedure 30
Coding 30
Execution & Output 20
Post Lab 10
Questions(Viva)
Total 100

Result:

Thus the conversion can be successfully executed

EXP NO: 6 c Write a Program to implement the Application of Queue

DATE:

Aim:
To implement the application of queue using FCFS CPU Scheduling
32
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")

33
 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 = "+ tr(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 Turnaround Time
1 10 0 10
2 5 10 15
3 8 15 23
Average Waiting Time = 8.333333333333334
Average Turnaround Time = 16.0

Pre-lab questions:

1. What is a Queue ADT and how does it differ from a Stack?

2. What are the primary operations of a Queue?
3. How do Queues work in real-world applications, such as print queues or task
scheduling?
4. What is the role of a Queue in managing process execution in operating
systems?
34
 5. What is the significance of the First-In-First-Out (FIFO) principle in a Queue?

Post Lab Questions:

1. How can a Queue be used to implement a print queue system in a printer?

2. Explain how a Queue can be used in the simulation of a real-time task
scheduling system.
3. What is the advantage of using a Queue in managing customer requests in a bank
or helpdesk system?
4. Can Queues be used to simulate a traffic control system? If yes, how?
5. How can a Queue be used to implement a job queue in an operating system?

MARKS ALLOCATION

Details Marks Marks

Allotted Awarded
Pre Lab Questions 10
Aim & Procedure 30
Coding 30
Execution & Output 20
Post Lab 10
Questions(Viva)
Total 100

Result:
Thus the FCFS CPU Scheduling was Executed Successfully.

EXP NO: 7a Write a Program to implement searching using Linear and

Binary Search algorithm using python
DATE:

Aim:
To implement searching using Linear and Binary Search algorithm using python.

Algorithm:
Linear Search:
1. Read the search element from the user
2. Compare, the search element with the first element in the list
3. If both are matching, then display "Given element found!!!" and terminate the function
35
4. If both are not matching, then compare search element with the next element in the list.
5. Repeat steps 3 and 4 until the search element is compared with the last element in the list.
6. If the last element in the list is also doesn't match, then display "Element not found!!!" and
terminate the function.

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

Linear Search Coding:

def linearsearch(arr, x): for i
in range(len(arr)):
36
 if arr[i] == x:
return i
return -1
arr = ['t','u','t','o','r','i','a','l']
x = 'a'
print("element found at index "+str(linearsearch(arr,x)))

Output of Binary Search:

40 Found at index 3
Output of Linear Search:
element found at index 6

Result:
Thus, the implementation of searching using Linear and Binary Search using python was
executed successfully

EXP NO: 7b Write a Program to Implement of Sorting Algorithm

DATE:

Aim:
To Implement sorting Algorithm using Quick Sort and Insertion Sort algorithm using python

Algorithm:
Quick Sort:

1. Find a “pivot” item in the array. This item is the basis for comparison for a single
round.
2. Start a pointer (the left pointer) at the first item in the array.
3. Start a pointer (the right pointer) at the last item in the array.
4. While the value at the left pointer in the array is less than the pivot value, move the
left pointer to the right (add 1). Continue until the value at the left pointer is greater
37
 than or equal to the pivot value.
5. While the value at the right pointer in the array is greater than the pivot value, move the
right pointer to the left (subtract 1). Continue until the value at the right pointer is less
than or equal to the pivot value.
6. If the left pointer is less than or equal to the right pointer, then swap the values at
these locations in the array.
7. Move the left pointer to the right by one and the right pointer to the left by one.

Insertion Sort:

1. Compare each element with preceding elements

2. Shift each compared element on the right
3. Place the element at the empty spot
4. Print the sorted array

Coding of Quick Sort:

# QuickSort Partition function
def partition(arr, low, high):
i = (low - 1) # index of smaller element
pivot = arr[high] # pivot element
for j in range(low, high):
# If current element is smaller than or equal to pivot
if arr[j] <= pivot:
i = i + 1 # increment index
arr[i], arr[j] = arr[j], arr[i] # swap elements

arr[i + 1], arr[high] = arr[high], arr[i + 1] # swap pivot with the element at i+1
return (i + 1) # return pivot index

# QuickSort function
def quickSort(arr, low, high):
if low < high:
pi = partition(arr, low, high) # partitioning index
quickSort(arr, low, pi - 1) # sort the left subarray
quickSort(arr, pi + 1, high) # sort the right subarray

# Insertion Sort function

def insertionSort(arr):
for i in range(1, len(arr)):
38
 key = arr[i]
j=i-1
# Move elements of arr[0..i-1], that are greater than key, to one position ahead
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key # Insert the key at the correct position

# Test QuickSort
arr1 = [2, 5, 3, 8, 6, 5, 4, 7]
n = len(arr1)
quickSort(arr1, 0, n - 1)
print("QuickSort Sorted array is:")
for i in range(n):
print(arr1[i], end=" ")
print() # Add a new line

# Test Insertion Sort

arr2 = ['t', 'u', 't', 'o', 'r', 'i', 'a', 'l']
insertionSort(arr2)
print("Insertion Sort Sorted array is:")

for i in range(len(arr2)):
print(arr2[i], end=" ")

39
Output:

QuickSort Sorted array is:

23455678
Insertion Sort Sorted array is:
ailorttu

Pre-lab questions:

1. What is the time complexity of Quick Sort in the average and worst-case scenarios?
2. How does the Quick Sort algorithm work, and what is its partitioning step?
3. Why is Quick Sort considered efficient on average, despite its worst-case time
complexity?
4. What are the benefits and drawbacks of using Insertion Sort for small datasets?
5. What type of data structure is best suited for Quick Sort, and why is it more
efficient with certain types of data (e.g., partially sorted data)?

Post Lab Questions:

1. Compare the performance of Quick Sort and Insertion Sort on an already sorted list
versus a reversed list.
2. How does Quick Sort handle duplicate values in the list, and what effect does
this have on performance?
3. What modifications can be made to the Quick Sort algorithm to improve its worst-
case performance?
4. What is the space complexity of Quick40Sort and Insertion Sort?
 5. Explain why Quick Sort might not be stable, and why that might matter for some
applications.

MARKS ALLOCATION

Details Marks Marks

Allotted Awarded
Pre Lab Questions 10
Aim & Procedure 30
Coding 30
Execution & Output 20
Post Lab 10
Questions(Viva)
Total 100

Result:
Thus, the implementation of searching Quick and Insertion Sort algorithm using python was
executed successfully.

EXP NO: 8
Write a Program to Implement of Hash tables
DATE:

Aim:
To Implement the Hash tables using python.

Algorithm:
1. Create a structure, data (hash table item) with key and value as data.
2. for loops to define the range within the set of elements.
3.hashfunction(key) for the size of capacity
4. Using insert (), removal () data to be presented or removed.
5. Stop the program

Coding:

# Initialize an empty hash table with 10 slots

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

# Function to check if a number is prime

def checkPrime(n):
41
 if n == 1 or n == 0:
return False
for i in range(2, int(n**0.5) + 1): # Check till sqrt(n)
if n % i == 0:
return False
return True

# Function to get the next prime number greater than the given number
def getPrime(n):
if n % 2 == 0:
n += 1 # Start from the next odd number if n is even
while not checkPrime(n):
n += 2 # Check only odd numbers
return n

# Hash function to compute the index of a key

def hashFunction(key):
capacity = getPrime(10) # Capacity based on prime number greater than 10
return key % capacity

# Insert data into the hash table

def insertData(key, data):
index = hashFunction(key)
# Handle collisions by appending to the list at hashTable[index]
hashTable[index].append([key, data])

# Remove data from the hash table

def removeData(key):
index = hashFunction(key)
# Iterate through the list to remove the key-value pair
for i, (k, v) in enumerate(hashTable[index]):
if k == key:
hashTable[index].pop(i)
return
print(f"Key {key} not found.")

# Test the hash table

insertData(123, "apple")
insertData(432, "mango")
insertData(213, "banana")
insertData(654, "guava")
print("Hash table after insertions:")
print(hashTable)
removeData(123)
print("\nHash table after removing key 123:")
print(hashTable)
42
Output:

Hash table after insertions:

[[], [], [[123, 'apple']], [[432, 'mango']], [[213, 'banana']], [[654, 'guava']], [], [], [], []]

Hash table after removing key 123:

[[], [], [], [[432, 'mango']], [[213, 'banana']], [[654, 'guava']], [], [], [], []]

Pre-lab questions:

1. What is a hash table, and how does it work?

2. What is the purpose of a hash function in a hash table?
3. What are the different types of collision resolution techniques in hash tables?

4. What are the key differences between hash tables and arrays or lists?
5. What are the advantages and disadvantages of hash tables compared to other
data structures like trees or lists?

Post Lab Questions:

1. Compare the performance of hash tables with binary search trees. In what scenarios
would one be preferred over the other?
2. What happens if two keys produce the same hash value (i.e., a hash collision)?

3. What is the space complexity of a hash table? How does the size of the table
impact its performance?
4. How does a hash table handle deletion of an element?
5. Why is it important to choose a good hash function, and how can a poor hash function
affect performance?

43
 MARKS ALLOCATION

Details Marks Marks

Allotted Awarded
Pre Lab Questions 10
Aim & Procedure 30
Coding 30
Execution & Output 20
Post Lab 10
Questions(Viva)
Total 100

Result:
Thus, the Implementation of hashing was executed successfully

EXP NO: 9 a
Write a Program to Implement Tree representation
DATE:

Aim:
To implement tree representation in binary tree format

Algorithm:
1. Create a binary tree.
2. Initially all the left and right vertex are none, then declare the values using insert ()
function.
3. If data>right element place the element in right
4. If data<left element place the element in left
5. print the tree
6. Stop the program

Coding:

# Define the Node class

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

# Method to insert data into the tree

def insert(self, data):
if self.data:
if data < self.data:
# If data is smaller, go left
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
# If data is larger, go right
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:

# Set the root node's data

self.data = data

# Method to print the tree in an in-order traversal

def printTree(self):
if self.left:
self.left.printTree()
print(self.data, end=" ") # Print the current node's data
if self.right:
self.right.printTree()

# Create the root node and insert values

root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)

# Print the tree (in-order traversal)

print("In-order traversal of the tree:")
root.printTree()

45
Output:
In-order traversal of the tree:
3 6 12 14

Result:
Thus, the binary tree was successfully created

EXP NO: 9 b
Write a Program to Implement Tree Traversal Algorithms
DATE:

Aim:
To Implement traversal using In order, Preorder,Postorder techniques.

Algorithm:
In order(tree)
1. Traverse the left subtree, i.e., call In order(left-subtree)
2. Visit the root.
3. Traverse the right subtree, i.e., call In order(right-
subtree) Preorder(tree)
1. Visit the root.
2. Traverse the left subtree, i.e., call Preorder(left-subtree)
3. Traverse the right subtree, i.e., call Preorder(right-
subtree) Post order(tree)
1. Traverse the left subtree, i.e., call Post order(left-subtree)
2. Traverse the right subtree, i.e., call Post order(right-subtree)

3. Visit the root

Coding:

# Define the Node class

class Node:
def __init__(self, key): # Constructor to initialize the node
46
 self.left = None
self.right = None
self.val = key

# Function for inorder traversal (Left, Root, Right)

def printInorder(root):
if root:
printInorder(root.left) # Traverse left subtree
print(root.val, end=" ") # Print root node
printInorder(root.right) # Traverse right subtree

# Function for postorder traversal (Left, Right, Root)

def printPostorder(root):
if root:

printPostorder(root.left) # Traverse left subtree

printPostorder(root.right) # Traverse right subtree
print(root.val, end=" ") # Print root node

# Function for preorder traversal (Root, Left, Right)

def printPreorder(root):

if root:
print(root.val, end=" ") # Print root node
printPreorder(root.left) # Traverse left subtree
printPreorder(root.right) # Traverse right subtree

# Creating the binary tree

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

# Print the tree traversals

print("\nPreorder 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)

47
 Output:
Preorder traversal of binary tree is
12453
In order traversal of binary tree is
42513
Post order traversal of binary tree is
45231

48
Result:
Thus the Implementation of traversal using In order, Preorder,Postorder techniques was executed
successfully

Pre-lab questions:

1. What is a binary tree, and how is it structured?

2. What is the difference between depth-first traversal and breadth-first traversal in a
tree?
3. Explain what in-order, pre-order, and post-order traversal methods are.

4. What happens when you perform pre-order traversal on a binary tree?

5. In which situations would in-order traversal be particularly useful, such as in a
binary search tree?

Post Lab Questions:

1. How would you implement a tree traversal that visits each node in both pre-order
and post-order sequentially?
2. Compare the use cases of pre-order traversal vs. post-order traversal in
practical applications like expression evaluation or tree construction.
3. In a binary search tree (BST), what would be the output of an in-order traversal?
Why is this important?
4. How can tree traversal be used in evaluating expressions in a tree (e.g., in a binary
expression tree)?
5. What is the space complexity of each tree traversal method (in-order, pre-order,
post-order)?

MARKS ALLOCATION

Details Marks Marks

Allotted Awarded
Pre Lab Questions 10
Aim & Procedure 30
Coding 30
Execution & Output 20
Post Lab 10
Questions(Viva)
Total 100
49
Result:
Thus the Implementation of traversal using Inorder,Preorder,Postorder techniques was executed
successfully

EXP NO: 10
Write a Program to Implementation of Binary Search
DATE: Trees

Aim:
To Implement the Binary Search Trees using python.

Algorithm:

Step 1-Read the search element from the user.

Step 2 - Compare the search element with the value of root node in the tree.

Step 3 - If both are matched, then display "Given node is found!!!" and terminate the function

Step 4 - If both are not matched, then check whether search element is smaller or larger than
that node value.

Step 5 - If search element is smaller, then continue the search process in left subtree.

Step 6- If search element is larger, then continue the search process in right subtree.

Step 7 - Repeat the same until we find the exact element or until the search element is compared
with the leaf node

Step 8 - If we reach to the node having the value equal to the search value then display "Element
is found" and terminate the function.

Coding:

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

def insert(self, data):

if data < self.data:
if self.left is None:
self.left = Node(data)
50
 else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)

def findval(self, lkpval):

if lkpval < self.data:
if self.left is None:

return str(lkpval) + " Not Found"

return self.left.findval(lkpval)
elif lkpval > self.data:
if self.right is None:
return str(lkpval) + " Not Found"
return self.right.findval(lkpval)
else:
return str(self.data) + ' is found'
def PrintTree(self):
if self.left:
self.left.PrintTree()
print(self.data)
if self.right:
self.right.PrintTree()
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
print(root.findval(7))

Output:
7 Not Found

51
Pre-lab questions:

1. What is a Binary Search Tree (BST), and what are its properties?
2. How does the insertion process work in a Binary Search Tree?
3. What is the time complexity of searching, inserting, and deleting nodes in a Binary
Search Tree?
4. Explain the difference between a balanced and an unbalanced BST. How does
balance affect performance?
5. What are the advantages of using a BST over an unsorted array or list for search
operations?

Post Lab Questions:

1. What are the advantages and disadvantages of using a Binary Search Tree (BST)
compared to other data structures such as arrays or linked lists?
2. Compare the time complexity of BST operations (insert, search, delete) in a
balanced tree versus an unbalanced tree.
3. Explain how tree rotations (left and right) are used to maintain a balanced Binary
Search Tree
4. How would you implement the deletion of a node with two children in a Binary
Search Tree?
5. What are some real-world applications of Binary Search Trees?

MARKS ALLOCATION

Details Marks Marks

Allotted Awarded
Pre Lab Questions 10
Aim & Procedure 30
Coding 30
Execution & Output 20
Post Lab 10
Questions(Viva)
Total 100

Result:
Thus, the Implementation of B i n a r y Search Trees using python was executed successfully.

EXP NO: 10
52
 DATE: Write a Program to Implementation of Heaps

Aim:
To Implement the Heap algorithm using python.

Algorithm:
1. Insert the heap function in the list
2. using heap push(),heap pop(),heap ify() to insert ,delete, display the elements.
3. Stop the program

Coding:

import heapq

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

heapq.heapify(H) # Convert the list H into a heap
print(H)

heapq.heappush(H, 8) # Add a new element (8) to the heap

print(H)

heapq.heappop(H) # Remove the smallest element from the heap

print(H)

Output:

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

[1, 3, 5, 78, 21, 45, 8]
[3, 8, 5, 78, 21, 45]

Pre-lab questions:

1. What is a heap, and how does it differ from a binary search tree (BST)?
53
 2. What are the properties of a max heap and a min heap?
3. How does the heap property affect the structure of a heap?
4. Explain how the heap insertion process works
5. What is the time complexity for insertion and deletion in a heap?

Post Lab Questions:

1. What are the advantages of using a heap over other data structures like arrays or
linked lists?

2. How does the time complexity of heap operations (insert, delete, and extract-
max/min) compare to other data structures like balanced trees or arrays?
3. In heapsort, what is the role of the heapify operation in sorting the array?
4. Explain how you can efficiently build a heap from an unsorted array.
5. How can you implement a heap using a dynamic array (list in Python)?

MARKS ALLOCATION

Details Marks Marks

Allotted Awarded
Pre Lab Questions 10
Aim & Procedure 30
Coding 30
Execution & Output 20
Post Lab 10
Questions(Viva)
Total 100

Result:
Thus, the Implementation of the Heap algorithm was executed successfully.

EXP NO: 12 a
Write a Program to Implement the Graph representation
DATE:

Aim:
54
 To implement the graph representation using python

Algorithm:
1. Initialize Graph: Create a matrix of size V x V (where V is the number of vertices) and
initialize all elements to 0. This represents that initially, there are no edges between any
vertices
2. Add Edge: To add an edge between two vertices u and v, set adj_matrix[u][v] = 1 for an
unweighted graph (or the edge weight if it's a weighted graph).
3. Remove Edge: To remove an edge between two vertices u and v, set adj_matrix[u][v] =
0.
4.. Display Graph: Print the matrix to show the adjacency matrix representation of the
graph.

Graph Representation Coding:

class Graph:
def __init__(self, gdict=None):
if gdict is None:
gdict = {}
self.gdict = gdict

def getVertices(self):
return list(self.gdict.keys())

# Example graph with vertices and edges

graph_elements = {
"a" : ["b", "c"],
"b" : ["a", "d"],
"c" : ["a", "d"],
"d" : ["e"],
"e" : ["d"]
}

g = Graph(graph_elements)
print(g.getVertices())
class Graph:
def __init__(self, gdict=None):
if gdict is None:
gdict = {}
self.gdict = gdict

def edges(self):
return self.findedges()

def findedges(self):
edgename = []
for vrtx in self.gdict:
for nxtvrtx in self.gdict[vrtx]:
55
 if {nxtvrtx, vrtx} not in edgename: # Prevents duplicate edges
edgename.append({vrtx, nxtvrtx})
return edgename

# Example graph with vertices and edges

graph_elements = {
"a" : ["b", "c"],
"b" : ["a", "d"],
"c" : ["a", "d"],
"d" : ["e"],
"e" : ["d"]
}

g = Graph(graph_elements)
print(g.edges())

Output:

DISPLAYING VERTICES
['a', 'b', 'c', 'd', 'e']
DISPLAYING EDGES
[{'a', 'b'}, {'a', 'c'}, {'d', 'b'}, {'c', 'd'}, {'d', 'e'}]

Result:
Thus, the implementation of graphs was executed successfully.

EXP NO: 12 b Write a Program to Implementation of Graph Traversal

DATE: Algorithms

Aim:
To Implement using BFS, DFS can be traversed.

Algorithm:

56
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

BFS:

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

Coding:
BFS
import collections

def bfs(graph, root):

visited, queue = set(), collections.deque([root])
visited.add(root)

while queue:
vertex = queue.popleft()
print(str(vertex) + " ", end="")
57
 for neighbour in graph[vertex]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)

# Ensure the script runs only if it's being executed directly

if __name__ == "__main__":
graph = {0: [1, 2], 1: [2], 2: [3], 3: [1, 2]}
print("Following is Breadth First Traversal: ")
bfs(graph, 0)

DFS Coding:
ef dfs_recursive(graph, vertex, visited=None):
if visited is None:
visited = set()
visited.add(vertex)
print(vertex, end=" ")
for neighbor in graph[vertex]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)
# Example graph
graph = {
'A': ['B', 'C', 'D'],
'B': ['A', 'E'],
'C': ['A', 'F'],
'D': ['A', 'F'],
'E': ['B', 'J'],

'F': ['C', 'D', 'K', 'G'],

'G': ['F', 'I'],
'H': ['J'],
'I': ['G', 'J'],
'J': ['H', 'I'],
'K': ['F']
}
# Perform DFS starting from vertex 'A'
print("DFS Recursive Traversal:")
58
dfs_recursive(graph, 'A')

Output:
DFS Recursive Traversal:
ABEJHIGFCDK

Following is Breadth First Traversal: 0 1 2 3

Pre-lab questions:

1. What is the difference between Depth-First Search (DFS) and Breadth-First Search
(BFS)?
2. How does DFS use a stack to traverse a graph?
3. How does BFS use a queue to traverse a graph?
4. What are the advantages of DFS over BFS, and vice versa?
5. How can you implement DFS using recursion?

Post Lab Questions:

1. In what scenarios would you prefer BFS over DFS?
2. Explain how DFS can be used to perform topological sorting in a Directed Acyclic
Graph (DAG).
59
 3. What are the applications of BFS in real-world problems (e.g., shortest path in
an unweighted graph)?
4. What is the space complexity of DFS and BFS?
5. What is the role of backtracking in DFS?
6. How do DFS and BFS work in directed vs. undirected graphs?

MARKS ALLOCATION

Details Marks Marks

Allotted Awarded
Pre Lab Questions 10
Aim & Procedure 30
Coding 30
Execution & Output 20
Post Lab 10
Questions(Viva)
Total 100

Result:
Thus the implementation of using BFS,DFS graph can be traversed.

EXP NO: 13 Write a Program to Implementation of single source shortest

DATE: path algorithm

Aim:
To Implement single source shortest path algorithm using Bellman Ford Algorithm.

Algorithm:

1) 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.
2) 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 60
 3) 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):

# Step 1: Initialize distances from src to all other vertices as INFINITE
dis = [maxsize] * V
dis[src] = 0

# Step 2: Relax all edges |V| - 1 times.

for i in range(V - 1):
for j in range(E):
u = graph[j][0]
v = graph[j][1]
weight = graph[j][2]
if dis[u] != maxsize and dis[u] + weight < dis[v]:
dis[v] = dis[u] + weight

# Step 3: Check for negative-weight cycles.

for i in range(E):
u = graph[i][0]
v = graph[i][1]
weight = graph[i][2]
if dis[u] != maxsize and dis[u] + weight < dis[v]:
print("Graph contains negative weight cycle")

return
# Step 4: Print the distance array.
print("Vertex Distance from Source")
for i in range(V):
print(f"{i}\t\t{dis[i]}")

# Driver Code
if __name__ == "__main__":
V = 5 # Number of vertices in graph
E = 8 # Number of edges in graph
graph = [
[0, 1, -1], # Edge 0->1 with weight -1
[0, 2, 4], # Edge 0->2 with weight 4
[1, 2, 3], # Edge 1->2 with weight 3
[1, 3, 2], # Edge 1->3 with weight 2
[1, 4, 2], # Edge 1->4 with weight 2
[3, 2, 5], # Edge 3->2 with weight 5
[3, 1, 1], # Edge 3->1 with weight 1
[4, 3, -3] # Edge 4->3 with weight -3
61
 ]

BellmanFord(graph, V, E, 0)

OUTPUT:

Vertex Distance from Source

0 0
1 -1
2 2
3 -2
4 1

Pre-lab questions:

1. What is the Bellman-Ford algorithm and how does it differ from Dijkstra’s algorithm?
2. How does the Bellman-Ford algorithm handle negative weights in a graph?
3. What is the time complexity of the Bellman-Ford algorithm?
4. What is a negative weight cycle and how does Bellman-Ford detect it?
5. What is the main advantage of using the Bellman-Ford algorithm over other shortest path
algorithms?
Post Lab Questions:

1. Explain how the Bellman-Ford algorithm detects negative weight cycles in a graph.
2. What are the practical applications of the Bellman-Ford algorithm?
3. Can Bellman-Ford work with both directed and undirected graphs?
4. What is the role of the 'relaxation' step in the Bellman-Ford algorithm?
5. How can the Bellman-Ford algorithm be optimized to run faster in some cases?

62
 MARKS ALLOCATION

Details Marks Marks

Allotted Awarded
Pre Lab Questions 10
Aim & Procedure 30
Coding 30
Execution & Output 20
Post Lab 10
Questions(Viva)
Total 100

Result:
Thus, the Implementation of single source shortest path algorithm was executed successfully.

EXP NO: 14 Write a Program to Implementation of minimum spanning

DATE: tree algorithms

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:

63
class Graph:
def __init__(self, vertices):
self.V = vertices # Number of vertices
self.graph = [] # List to store the graph edges

# Function to add an edge to the graph

def add_edge(self, u, v, w):
self.graph.append([u, v, w]) # Edge represented as [u, v, weight]

# Find function using path compression

def find(self, parent, i):
if parent[i] == i:
return i
else:
parent[i] = self.find(parent, parent[i]) # Path compression
return parent[i]

# Apply union by rank

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

# Kruskal's Algorithm to find the MST

def kruskal_algo(self):
result = [] # Store the resultant MST
i, e = 0, 0 # i is the index for sorted edges, e is the number of edges in MST

# Step 1: Sort all edges in the graph based on their weight

self.graph = sorted(self.graph, key=lambda item: item[2])

# Step 2: Initialize parent and rank for each vertex

parent = [i for i in range(self.V)] # Initially, each node is its own parent
rank = [0] * self.V # Rank to store the depth of trees

# Step 3: Process each edge in the sorted graph

while e < self.V - 1: # The MST will have V-1 edges
64
 u, v, w = self.graph[i]
i = i + 1 # Move to the next edge
x = self.find(parent, u)
y = self.find(parent, v)

# If u and v are not connected (not forming a cycle), include the edge
if x != y:
e=e+1
result.append([u, v, w])
self.apply_union(parent, rank, x, y)

# Print the MST result

print("Minimum Spanning Tree (MST) Edges:")
for u, v, weight in result:
print(f"{u} - {v}: {weight}")

# Driver code to test Kruskal's algorithm

if __name__ == "__main__":
g = Graph(6) # Graph with 6 vertices

# Adding edges (u, v, weight)

g.add_edge(0, 1, 4)
g.add_edge(0, 2, 4)

g.add_edge(1, 2, 2)
g.add_edge(2, 3, 3)
g.add_edge(2, 5, 2)
g.add_edge(2, 4, 4)
g.add_edge(3, 4, 3)
g.add_edge(4, 5, 3)

# Running Kruskal's algorithm to find MST

g.kruskal_algo()

65
Output:

Minimum Spanning Tree (MST) Edges:

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

Pre-lab questions:

1. What is a Minimum Spanning Tree (MST)?

2. Explain Kruskal's algorithm for finding the Minimum Spanning Tree of a graph.
3. What data structures are used in Kruskal's algorithm to efficiently check for
cycles?
4. Why does Kruskal’s algorithm sort the edges by weight?
5. What is the role of the union-find (disjoint-set) data structure in Kruskal’s
algorithm? 66
 Post Lab Questions:
1. What is the significance of sorting the edges in Kruskal’s algorithm?
2. How does the union-find structure help improve the efficiency of Kruskal’s
algorithm?
3. In what kind of graphs would Kruskal's algorithm perform better than Prim's
algorithm?
4. How can Kruskal’s algorithm be modified to find all MSTs of a graph (if there are
multiple)?
5. What are the practical applications of Minimum Spanning Trees in real-world
scenarios?

MARKS ALLOCATION

Details Marks Marks

Allotted Awarded
Pre Lab Questions 10
Aim & Procedure 30
Coding 30
Execution & Output 20
Post Lab 10
Questions(Viva)
Total 100

Result:
Thus, the program was executed successfully.

EXP NO: 15 Write a Program to Implementation Binary search

DATE: algorithm.

Aim:
To implement the Binary search algorithm using python.

Algorithm:

67
 1. Initial Setup: Given a sorted array and a target value, set the low and high bounds for
the search (initially low = 0 and high = len(array) - 1).
2. Repeat until the target is found or the bounds cross:
 Calculate the middle index: mid = (low + high) // 2.
 Compare the target with the element at mid:
o If the target is equal to the element at mid, return mid (index of the target).
o If the target is smaller than the element at mid, narrow the search to the lower
half by setting high = mid - 1.
o If the target is larger than the element at mid, narrow the search to the upper half
by setting low = mid + 1.
3. If the target is not found and the search interval becomes invalid (low > high), return -1
to indicate that the target is not in the list.

Coding:

def binary_search(arr, target):

# Set the initial boundaries for the search
low = 0
high = len(arr) - 1

# Continue searching as long as the search interval is valid

while low <= high:
# Calculate the middle index
mid = (low + high) // 2

# Check if the target is at the middle

if arr[mid] == target:
return mid # Return the index of the target

# If the target is smaller, search the left half

elif arr[mid] > target:
high = mid - 1

# If the target is larger, search the right half

else:
low = mid + 1

# If the target is not found, return -1

return -1

# Example usage:
arr = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20] # Sorted array
68
target = 14 # Target to search for

result = binary_search(arr, target)

if result != -1:
print(f"Element found at index {result}")
else:

print("Element not found")

Output:

Element found at index 6

Pre-lab questions:

1. What is the purpose of the Binary Search algorithm, and how does it differ from a
linear search?
2. Why is Binary Search applicable only to sorted arrays or lists? Explain the reasoning
behind this requirement.
3. What is the time complexity of the Binary Search algorithm, and how does it
compare to the time complexity of a linear search?
4. How does the Binary Search algorithm narrow down the search space during
each iteration?
69
 5. What are the advantages and disadvantages of using Binary Search over other
search algorithms?

Post Lab Questions:

1. Explain how the Binary Search algorithm ensures efficiency by reducing the
problem size in each step.

2. What happens if you try to use Binary Search on an unsorted array? What issues
would arise?
4. What would be the effect of not checking the condition low <= high in the Binary
Search loop?
5. Can you implement Binary Search recursively instead of iteratively? If so, how would
the recursive approach differ from the iterative version?

MARKS ALLOCATION

Details Marks Marks

Allotted Awarded
Pre Lab Questions 10
Aim & Procedure 30
Coding 30
Execution & Output 20
Post Lab 10
Questions(Viva)
Total 100

Result:
Thus , the program was executed successfully.

70