asd asd asd PROGRAM OUTCOMES A B.Tech –graduate should possess the following program outcomes .

1 Engineering knowledge : Apply the knowledge of mathematics, science, engineering fundamentals and an engineering specialization to the solution of complex engineering problems.

2 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.

3 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.

4 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.

5 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.

6 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.

7 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.

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

9 Individual and teamwork : Function effectively as an individual, and as a member or leader in diverse teams ,and in multi disciplinary settings.

10 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.

11 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 multi disciplinary environments.

12 Lifelong 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.

MALLA REDDY COLLEGE OF ENGINEERING AND TECHNOLOGY I Year B. Tech -II Sem L/ T/P/C -/-/3/1.5 (R22A0 582) DATA STRUCTURES AND IT’S APPLICATIONS LAB PROGRAM OBJECTIVES

This course will enable the students:

1. To understand a range of Object -Oriented Programming, as well as in-depth data and information processing techniques.

2. To know how linear data structures work.

3. To implement non-linear data structures.

4. To simulate searching and sorting techniques.

5. To develop programs for performing operations on Trees and Graphs.

WEEK 1:

Write a Python program for class, Flower, that has three instance variables of typestr, int, and float, that respectively represent the name of the flower, its number of petals, and its price. Your class must include a constructor method that initializes each variable to an appropriate value, and your class should include methods for setting the value of each type, and retrieving the value of each type.

WEEK 2:

Develop an inheritance hierarchy based upon a Polygon class that has abstract methods area( ) and perimeter( ). Implement classes Triangle, Quadrilateral, Pentagon, that extend this base class, with the obvious meanings for the area( ) and perimeter( ) methods. Write a simple program that allows users to create polygons of the various types and input their geometric dimensions, and the program then outputs their area and perimeter.

WEEK 3:

a) Write a Python program to implement method overloading.

b) Write a Python program to implement method overriding.

WEEK 4:

Write a Python program to illustrate the following comprehensions:

a) List Comprehensions b) Dictionary Comprehensions c) Set Comprehensions d) Generator Comprehensions WEEK 5:

a) Write a Python program for Linear Search.

b) Write a Python program for Binary Search.

WEEK 6:

a) Write a Python program to implement Bubble Sort.

b) Write a Python program to implement Selection Sort.

WEEK 7:

a) Write a Python program to implement Merge sort.

b) Write a Python program to implement Quick sort.

WEEK 8:

a) Write a Python program to implement Stack using List.

b) Write a Python program to implement Queue using List.

WEEK 9:

Write a Python program to implement Singly Linked List.

WEEK 10:

Write a Python program to implement Doubly Linked list.

WEEK 11:

Write a Python program to implement Breadth First Search.

WEEK 12:

Write a Python program to implement Depth First Search.

PROGRAM OUTCOMES:

The student able to:

1. Examine Python syntax and semantics and apply Python flow control and functions.

2. Create, run and manipulate Python Programs using core data structures like Lists.

3. Apply Dictionaries and use Regular Expressions.

4. Interpret the concepts of Object -Oriented Programming as used in Python.

5. Master object -oriented programming to create an entire python project using objects and classes .

CONTENTS Week - No S.No/ Program No List of Programs 1 1) Write a Python program for class, Flower, that has three instance variables

of typestr, int, and float, that respectively represent the name of the flower, its number of petals, and its price. Your class must include a constructor method that initializes each variable to an appropriate value, and your class should include methods for setting the value of each type, and retrieving the value of each type

2 2) Develop an inheritance hierarchy based upon a Polygon class that has abstract methods area( ) and perimeter( ). Implement classes Triangle, Quadrilateral, Pentagon, that extend this base class, with the obvious meanings for the area( ) and perimeter( ) methods. Write a simple program that allows users to create polygons of the various types and input their

geometric dimensions, and the program then outputs their area and perimeter 3 1) Write a Python program to implement method overloading.

2) Write a Python program to implement method overriding .

4 1) Write a Python program to illustrate the following comprehensions:

a) List Comprehensions b) Dictionary Comprehensions c) Set Comprehensions d) Generator Comprehensions 5 1) Write a Python program for Linear Search.

2) Write a Python program for Binary Search.

6 1) Write a Python program to implement Bubble Sort 2) Write a Python program to implement Selection Sort 7 1) Write a Python program to implement Merge Sort 2) Write a Python program to implement Quick Sort 8 1) Write a Python program to implement stack using List

2) Write a Python program to implement Qu eue using List 9 1) Write a Python program to implement Singly Linked List 10 1) Write a Python program to implement Doubly Linked List 11 1) Write a python program to implement Breadth First Search 12 1) Write a python program to implement Depth First Search

INSTRUCTIONS TO STUDENTS 1. Students should bring lab Manual/Record for every laboratory session and should enter the readings /observations in the manual while performing the experiment.

2. The group - wise division made in the beginning should be adhered to, and no mix up of students among different groups will be permitted later.

3. The components required pertaining to the experiment should be collected from stores in –charge after duly filling in the requisition form.

4. When the experiment is completed, students should disconnect the setup made by them, and should return all the components/instruments taken for the purpose.

5. Any damage to the apparatus that occurs during the experiment should be brought to the notice of lab in -charge, consequently, the cost of repair or new apparatus should be brought by the students.

6. After completion of the experiment, certification of the concerned staff in –charge in the observation book is necessary.

7. Students should be present in the labs for the total scheduled duration.

8. Students should not carry ant food items inside the laboratory.

9. Use of cell phones and IPODs is forbidden.

10. Students should not write on or deface any lab desks, computers, or any equipment provided to them during the experiment.

11. Every student should keep his/her work area properly before leaving the laboratory.

MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER PROGRAM-1 Date:

Aim:

Write a Python program for class, Flower, that has three instance variables of type str, int, and float, that respectively represent the name of the flower, its number of petals, and its price.

Your class must include a constructor method that initializes each variable to an appropriate value, and your class should include methods for setting the value of each type, and retrie ving the value of each type.

class Flower:

#Common base class for all Flowers def init (self, petalName, petalNumber, petalPrice):

self.name = petalName self.petals = petalNumber self.price = petalPrice def setName(self, petalName):

self.name = petalName def setPetals(self, petalNumber):

self.petals = petalNumber def setPrice(self, petalPrice):

self.price = petalPrice def getName(self):

return self.name def getPetals(self):

return self.petals def getPrice(self):

return self.price #This would create first object of Flower class f1 = Flower("Sunflower", 2, 1000) print ("Flower Details:") print ("Name: ", f1.getName())

print ("Number of petals:", f1.getPetals()) print ("Price:",f1.getPrice()) print ("\n") #This would create second object of Flower class f2 = Flower("Rose", 5, 2000)

f2.setPrice(3333) f2.setPetals(6) print ("Flower Details:") print ("Name: ", f2.getName()) print ("Number of petals:", f2.getPetals())

print ("Price:",f2.getPrice()) MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER Output:

Signature of the Faculty MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER Record Notes

MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB

B TECH I YEAR II SEMESTER PROGRAM-2 Date:

Aim:

Develo p an inheritance hierarchy based upon a Polygon class that has abstract methods area() and perimeter(). Implement classes Triangle, Quadrilateral, Pentagon, that extend this base class, with the obvious meanings for the area() and perimeter() methods. Writ e a simple program that allows users to create polygons of the various types and input their geometric dimensions, and the program then outputs their area and perimeter.

Program:

from abc import abstractmethod, ABCMeta import math class Polygon(metaclass = ABCMeta):

def init (self, side_lengths = [1,1,1], self._side_lengths = side_lengths self._num_sizes = 3 num_sides = 3):

@abstractmethod def area(self):

pass @abstractmethod def perimeter(self):

pass def repr (self):

return (str(self._side_lengths)) class Triangle(Polygon):

def init (self, side_lengths):

super(). init (side_lengths, 3) self._perimeter = self.perimeter() self._area = self.area() def perimeter(self):

return(sum(self._side_lengths)) def area(self):

#Area of Triangle s = self._perimeter/2 product = s for i in self._side_lengths:

product*=(s -i) return product**0.5 class Quadrilateral(Polygon):

def init (self, side_lengths):

super(). init (side_lengths, 4) self._perimeter = self.perimeter() MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER

self._area = self.area() def perimeter(self):

return(sum(self._side_lengths)) def area(self):

# Area of an irregular Quadrilateral semiperimeter = sum(self._side_lengths) / 2 return math.sqrt((semiperimeter - self._side_lengths[0]) * (semiperimeter - self._side_leng ths[1]) * (semiperimeter - self._side_lengths[2]) *

(semiperimeter - self._side_lengths[3])) class Pentagon(Polygon):

def init (self, side_lengths):

super(). init (side_lengths, 5) self._perimeter = self.perimeter() self._area = self.area() def perimeter(self):

return((self._side_lengths) * 5) def area(self):

# Area of a regular Pentagon a = self._side_lengths return (math.sqrt(5 * (5 + 2 * (math.sqrt(5)))) * a * a) / 4 #object of Triangle t1 = Triangle([1,2,2])

print(t1.perimeter(), t1.area()) #object of Quadrilateral q1 = Quadrilateral([1,1,1,1]) print(q1.perimeter(), q1.area()) #object of Pentagon

p1 = Pentagon(1) print(p1.perimeter(), p1.area()) Output:

Signature of the Faculty MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER Record Notes

MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB

B TECH I YEAR II SEMESTER PROGRAM-3 Date:

Aim:

Write a python program to implement method overloading.

class OverloadDemo:

# sum method with default as None for parameters def sum(self, a=None, b=None, c=None):

# When three params are passed if a!=None and b!=None and c!=None:s = a + b + c print('Sum = ', s) # When two params are

passedelif a!=None and b!=None:

s = a + b print('Sum = ', s) od = OverloadDemo() od.sum(7, 8)

od.sum(7, 8, 9) Output:

Signature of the Faculty MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER b) Write a python program to implement method overriding.

class Person:

def init (self, name, age):self.name = name self.age = age def displayData(self):

print('In parent class displayData method') print(self.name) print(self.age) class Employee(Person):

def init (self, name, age, id):

# calling constructor of super classsuper(). init (name, age) self.empId = id def displayData(self):

print('In child class displayData method') print(self.name) print(self.age) print(self.empId) #Person class object

person = Person('Karthik Shaurya', 26)person.displayData() #Employee class object emp = Employee(''Karthik Shaurya', 26, 'E317') emp.displayData()

Output:

Signature of the Faculty MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER Record Notes

MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB

B TECH I YEAR II SEMESTER PROGRAM-4 Date:

Aim:

Write a Python program to illustrate the following comprehensions:

a) List Comprehensionsb) Dictionary Comprehensions c) Set Comprehensions d) Generator Comprehensions a) List Comprehensions :

List Comprehensions provide an elegant way to create new lists. The following is the basic structure of a list comprehension:

output_list = [output_exp for var in input_list if (var satisfies this condition)] Note that list comprehension may or may not contain an if condition. List comprehensions can contain multiple for (nested list comprehensions).

Example: Suppose we want to create an output list which contains only the even numbers which are present in the input list. Let’s see how to do this using for loop and list comprehension and decide which method suits better.

Using Loop:

#Constructing output list WITHOUT using List comprehensions input_list = [1, 2, 3, 4, 4, 5, 6, 7, 7] output_list = [] #Using loop for constructing output listfor var in input_list:

if var % 2 == 0:

output_list.append( var) print(“Output List using for loop:”, output_list) Output:

MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER Using List Comprehension:

# Using List comprehensions # for constructing output list input_list = [1, 2, 3, 4, 4, 5, 6, 7, 7] list_using_comp = [var for var in input_list if var % 2 ==

0] print("Output List using list comprehensions:",list_using_comp) Output:

a) Dictionary Comprehensions:

Extending the idea of list comprehensions, we can also create a dictionary using dictionary comprehensions. The basic structure of a dictionary comprehension looks like below.

output_dict = {key:value for (key, value) in iterable if (key, value satisfy this condition)} Example 1: Suppose we want to create an output dictionary which contains only the odd numbers that are present in the input list as keys and their cubes as values. Let’s see how to do this using for loops and dictionary comprehension.

Using Loop:

input_list = [1, 2, 3, 4, 5, 6, 7]output_dict = {} # Using loop for constructing output dictionaryfor var in input_list:

if var % 2 != 0:

output_dict[var] = var**3 print("Output Dictionary using for loop:",output_dict) Output:

MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER Using Dictionary Comprehension:

# Using Dictionary comprehensions # for constructing output dictionaryinput_list = [1,2,3,4,5,6,7] dict_using_comp = {var:var ** 3 for var in input_list if var % 2 != 0}

print("Output Dictionary using dictionary comprehensions:", dict_using_comp) Output:

Example 2: Given two lists containing the names of states and their corresponding capitals, construct a dictionary which maps the states with their respective capitals. Let’s see how to do this using for loops and dictionary comprehension.

Using Loop:

state = ['Gujarat', 'Maharashtra', 'Rajasthan']capital = ['Gandhinagar', 'Mumbai', 'Jaipur'] output_dict = {} # Using loop for constructing output dictionary

for (key, value) in zip(state, capital): output_dict[key] = value print("Output Dictionary using for loop:", output_dict) Output:

Using Dictionary Comprehension:

# Using Dictionary comprehensions # for constructing output dictionary state = ['Gujarat', 'Maharashtra', 'Rajasthan']capital = ['Gandhinagar', 'Mumbai', 'Jaipur']

dict_using_comp = {key:value for (key, value) in zip(state, capital)} print("Output Dictionary using dictionary comprehensions:",dict_using_comp) MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB

B TECH I YEAR II SEMESTER Output:

c) Set Comprehensions:

Set comprehensions are pretty similar to list comprehensions. The only difference between them is that set comprehensions use curly brackets { }. Let’s look at the following example to understand set comprehensions.

Example : Suppose we want to create an output set which contains only the even numbers that are present in the input list. Note that set will discard all the duplicate values. Let’s see how we can do this using for loops and set comprehension.

Using Loop:

input_list = [1, 2, 3, 4, 4, 5, 6, 6, 6, 7, 7] output_set = set() # Using loop for constructing output setfor var in input_list:

if var % 2 == 0:

output_set.add( var) print("Output Set using for loop:", output_set) Output:

Using Set Comprehension:

# Using Set comprehensions # for constructing output set input_list = [1, 2, 3, 4, 4, 5, 6, 6, 6, 7, 7] set_using_comp = {var for var in input_list if var % 2 == 0}print("Output Set using set

comprehensions:",set_using_comp) Output:

MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER d) Generator Comprehensions:

Generator Comprehensions are very similar to list comprehensions. One difference between them is that generator comprehensions use circular brackets whereas list comprehensions use square brackets. The major difference between them is that generators don’t allocate memory for the whole list. Instead, they generate each value one by one which is why they are memory efficient. Let’s look at the following example to understand

generator comprehension:

input_list = [1, 2, 3, 4, 4, 5, 6, 7, 7] output_gen = (var for var in input_list if var % 2 == 0) print("Output values using generator comprehensions:", end = ' ')for var in output_gen:

print(var, end = ' ') Output:

MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER Record Notes MRCET EAMCET CODE : MLRD www.mrcet.ac.in

DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER

PROGRAM-5 Date:

Aim:

Write a python program for Linear Search .

Linear Search Program:

def linearSearch(target, List):

position = 0 global iterations iterations = 0 while position < len(List):

iterations += 1 if target == List[position]:

return position position += 1 return -1 if name == ' main ':

List = [1, 2, 3, 4, 5, 6, 7, 8] target = 3 answer = linearSearch(target, List) if answer != -1:

print('Target found at index :', answer, 'in', iterations,'iterations') else:

print('Target not found in the list') Output:

Signature of the Faculty MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER b) Binary Search Program:

def binarySearch(target, List):

left = 0 right = len(List) - 1 global iterations iterations = 0 while left <= right:

iterations += 1 mid = (left + right) // 2 if target == List[mid]:

return mid elif target < List[mid]:

right = mid - 1 else:

left = mid + 1 return -1 if name == ' main ':

List = [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14] target = 12 answer = binarySearch(target, List) if(answer != -1):

print('Target',target,'found at position', answer, 'in', iterations,'iterations') else:

print('Target not found') Output:

Signature of the Faculty MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER Record Notes

MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB

B TECH I YEAR II SEMESTER PROGRAM-6 Date:

Aim:

Write a python program to implement Bubble Sort Bubble Sort Program:

def bubble_sort(alist):

for i in range(len(alist) - 1, 0, -1):

no_swap = True for j in range(0, i):

if alist[j + 1] < alist[j]:

alist[j], alist[j + 1] = alist[j + 1], alist[j] no_swap = False if no_swap:

return alist = input('Enter the list of numbers: ').split() alist = [int(x) for x in alist] bubble_sort(alist) print('Sorted list: ', alist)

Output:

b) Write a python program to implement Selection Sort Program:

def selection_sort(alist):

for i in range(0, len(alist) - 1):

smallest = i for j in range(i + 1, len(alist)):

if alist[j] < alist[smallest]:

smallest = j alist[i], alist[smallest] = alist[smallest], alist[i] alist = input('Enter the list of numbers: ').split() alist = [int(x) for x in alist] selection_sort(alist)

print('Sorted list: ', alist) Output:

Signature of the Faculty MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER Record Notes

MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB

B TECH I YEAR II SEMESTER PROGRAM-7 Date:

Aim:

a) Write a python program to implement Merge sort Merge Sort Program:

def merge_sort(alist, start, end):

'''Sorts the list from indexes start to end if end - start > 1:

mid = (start + end)//2 merge_sort(alist, start, mid) merge_sort(alist, mid, end) merge_list(alist, start, mid, end) def merge_list(alist, start, mid, end):

left = alist[start:mid] right = alist[mid:end] k = start i = 0 j = 0

while (start + i < mid and mid + j < end):

if (left[i] <= right[j]):

alist[k] = left[i] i = i + 1 else:

alist[k] = right[j] j = j + 1 k = k + 1 if start + i < mid:

while k < end:

alist[k] = left[i] i = i + 1 k = k + 1 - 1 inclusive.''' else:

while k < end:

alist[k] = right[j] j = j + 1 k = k + 1 alist = input('Enter the list of numbers: ').split() alist = [int(x) for x in alist]

merge_sort(alist, 0, len(alist)) print('Sorted list: ', alist) Output:

Signature of the Faculty MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER b) Write a python program to implement Quick Sort

Program def quicksort(alist, start, end):

'''Sorts the list from indexes start to end - 1 inclusive.''' if end - start > 1:

p = partition(alist, start, end) quicksort(alist, start, p) quicksort(alist, p + 1, end) def partition(alist, start, end):

pivot = alist[start] i = start + 1 j = end - 1 while True:

while (i <= j i = i + 1 while (i <= j j = j - 1 if i <= j: and alist[i] <= pivot):

and alist[j] >= pivot):

alist[i], alist[j] = alist[j], alist[i] else:

alist[start], alist[j] = alist[j], alist[start] return j alist = input('Enter the list of numbers: ').split() alist = [int(x) for x in alist] quicksort(alist, 0, len(alist))

print('Sorted list: ', alist) Output:

Signature of the Faculty MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER Record Notes

MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB

B TECH I YEAR II SEMESTER PROGRAM-8 Date:

Aim:

a) Write a python program to implement Stacks Stack Program:

# Custom stack implementation in Python class Stack:

# Constructor to initialize the stack def init (self, size):

self.arr = [None] * size self.capacity = size self.top = -1 # Function to add an element `x` to the stack def push(self, x):

if self.isFull():

print("Stack Overflow!! Calling exit()…") exit(1) print("Inserting", x, "into the stack…") self.top = self.top + 1 self.arr[self.top] = x

# Function to pop a top element from the def pop(self):

# check for stack underflow if self.isEmpty():

print("Stack Underflow!! Calling exit(1) stack exit()…") print("Removing", self.peek(), "from the stack") #decrease stack size by 1 and (optionally) return the popped element

top = self.arr[self.top] self.top = self.top - 1 return top # Function to return the top element of the stack def peek(self):

if self.isEmpty():

exit(1) return self.arr[self.top] # Function to return the size of the stack def size(self):

return self.top + 1 # Function to check if the stack is empty or not def isEmpty(self):

return self.size() == 0 MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER # Function to check if the stack is full or not

def isFull(self):

return self.size() == self.capacity if name == ' main ':

stack = Stack(3) stack.push(1) stack.push(2) stack.pop() stack.pop()

# Inserting 1 in the stack # Inserting 2 in the stack # removing the top element (2) # removing the top element (1) stack.push(3) # Inserting 3 in the stack

print("Top element is", stack.peek()) print("The stack size is", stack.size()) stack.pop() # removing the top element (3) # check if the stack if stack.isEmpty():

print("The stack else:

print("The stack is empty is empty") is not empty") Output:

Signature of the Faculty MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER b) Write a python program to implement Queue

Program:

# Custom queue implementation in Python class Queue:

# Initialize queue def init (self, size):

self.q = [None] * size # list to store queue elements self.capacity = size # maximum capacity of the queue self.front = 0 # front points to the front element in the queue self.rear = -1 # rear points to the last element in the queue self.count = 0 # current size of the queue

# Function to dequeue the front element def pop(self):

# check for queue underflow if self.isEmpty():

print("Queue Underflow!! Terminating process.") exit(1) print("Removing element…", self.q[self.front]) self.front = (self.front + 1) % self.capacity self.count = self.count - 1

# Function to add an element to the queue def append(self, value):

# check for queue overflow if self.isFull():

print("Overflow!! Terminating process.") exit(1) print("Inserting element…", value) self.rear = (self.rear + 1) % self.capacity self.q[self.rear] = value

self.count = self.count + 1 # Function to return the front element of the queue def peek(self):

if self.isEmpty():

print("Queue UnderFlow!! Terminating process.") exit(1) return self.q[self.front] # Function to return the size of the queue def size(self):

return self.count MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER # Function to check if the queue is empty or not

def isEmpty(self):

return self.size() == 0 # Function to check if the queue is full def isFull(self):

return self.size() == self.capacity or not if name == ' main ':

# create a queue of capacity 5 q = Queue(5) q.append(1) q.append(2) q.append(3)

print("The queue size is", q.size()) print("The front element is", q.peek()) q.pop() print("The front element is", q.peek()) q.pop()

q.pop() if q.isEmpty():

print("The queue is empty") else:

print("The queue is not empty") Output:

Signature of the Faculty MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER Record Notes

MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB

B TECH I YEAR II SEMESTER PROGRAM-9 Date:

Aim:

Write a program to implement Singly Linked List Program:

import os from typing import NewType class _Node:

''' Creates a Node with two fields:

1. element (accesed using ._element) 2. link (accesed using ._link) ''' slots = '_element', '_link' def init (self, element, link):

''' Initialses _element and _link with element and link respectively.

''' self._element = element self._link = link class LinkedList:

''' Consists of member funtions to perform different operations on the linked list.

''' def init (self):

''' Initialses head, tail and size with None, None and 0 respectively.

''' self._head = None self._tail = None self._size = 0 def len (self):

''' Returns length of linked list ''' return self._size def isempty(self):

''' Returns True if linked list is empty, otherwise False. ''' return self._size == 0 def addLast(self, e):

''' MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER Adds the passed element at the end of the linked list. '''

newest = _Node(e, None) if self.isempty():

self._head = newest else:

self._tail._link = newest self._tail = newest self._size += 1 def addFirst(self, e):

''' Adds the passed element at the beginning of the linked list.

''' newest = _Node(e, None) if self.isempty():

self._head = newest self._tail = newest else:

newest._link = self._head self._head = newest self._size += 1 def addAnywhere(self, e, index):

''' Adds the passed element at the passed index position of the linked list.

''' newest = _Node(e, None) i = index - 1 p = self._head if self.isempty():

self.addFirst(e) else:

for i in range(i):

p = p._link newest._link = p._link p._link = newest print(f"Added Item at index {index}! \n\n") self._size += 1

def removeFirst(self):

''' Removes element from the beginning of the linked list.

Returns the removed element.

''' if self.isempty():

print("List is Empty. Cannot perform deletion operation.") return MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB

B TECH I YEAR II SEMESTER e = self._head._element self._head = self._head._link self._size = self._size - 1 if self.isempty():

self._tail = None return e def removeLast(self):

''' Removes element from the end of the linked list.

Returns the removed element.

''' if self.isempty():

print("List is Empty. Cannot perform deletion operation.") return p = self._head if p._link == None:

e = p._element self._head = None else:

while p._link._link != None:

p = p._link e = p._link._element p._link = None self._tail = p self._size = self._size - 1

return e def removeAnywhere(self, index):

''' Removes element from the passed index position of the linked list.

Returns the removed element.

''' p = self._head i = index - 1 if index == 0:

return self.removeFirst() elif index == self._size - 1:

return self.removeLast() else:

for x in range(i):

p = p._link e = p._link._element p._link = p._link._link self._size -= 1 return e

def display(self):

''' MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER Utility function to display the linked list.

''' if self.isempty() == 0:

p = self._head while p:

print(p._element, end='-->') p = p._link print("NULL") else:

print("Empty") def search(self, key):

''' Searches for the passed element in the linked list.

Returns the index position if found, else -1.

''' p = self._head index = 0 while p:

if p._element == key:

return index p = p._link index += 1 return -1 ###################################################################

def options():

''' Prints Menu for operations ''' options_list = ['Add Last', 'Add First', 'Add Anywhere', 'Remove First', 'Remove Last', 'Remove Anywhere',

'Display List', 'Print Size', 'Search', 'Exit'] print("MENU") for i, option in enumerate(options_list):

print(f'{i + 1}. {option}') choice = int(input("Enter choice: ")) return choice def switch_case(choice):

''' Switch Case for operations ''' if choice == 1:

elem = int(input("Enter Item: ")) L.addLast(elem) print("Added Item at Last!\n\n") elif choice == 2:

elem = int(input("Enter Item: ")) L.addFirst(elem) print("Added Item at First!\n\n") MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB

B TECH I YEAR II SEMESTER elif choice == 3:

elem = int(input("Enter Item: ")) index = int(input("Enter Index: ")) L.addAnywhere(elem, index) elif choice == 4:

print("Removed Element from First:", L.removeFirst()) elif choice == 5:

print("Removed Element from last:", L.removeLast()) elif choice == 6:

index = int(input("Enter Index: ")) print(f"Removed Item: {L.removeAnywhere(index)} !\n\n") elif choice == 7:

print("List: ", end='') L.display() print("\n") elif choice == 8:

print("Size:", len(L)) print("\n") elif choice == 9:

key = int(input("Enter item to search: ")) if L.search(key) >= 0:

print(f"Item {key} found at index position {L.search(key)} \n\n") else:

print("Item not in the list\n\n") elif choice == 10:

import sys sys.exit() ################################################################### if name == ' main ':

L = LinkedList() while True:

choice = options() switch_case(choice) Output:

MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER Signature of the Faculty MRCET EAMCET CODE : MLRD www.mrcet.ac.in

DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER Record Notes MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB

B TECH I YEAR II SEMESTER MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER PROGRAM-10 Date:

Aim:

Write a program to implement Doubly Linked list Program:

import os class _Node:

''' Creates a Node with three fields:

1. element (accessed using ._element) 2. link (accessed using ._link) 3. prev (accessed using ._prev) ''' slots = '_element', '_link', '_prev'

def init (self, element, link, prev):

''' Initialses _element, _link and _prev with element, link and prev respectively.

''' self._element = element self._link = link self._prev = prev class DoublyLL:

''' Consists of member funtions to perform different operations on the doubly linked list.

''' def init (self):

''' Initialises head, tail and size with None, None and 0 respectively.

''' self._head = None self._tail = None self._size = 0 def len (self):

''' Returns length of linked list ''' return self._size def isempty(self):

''' Returns True if doubly linked list is empty, otherwise False.

''' return self._size == 0 def addLast(self, e):

'''Adds the passed element at the end of the doubly linked list.''' MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER newest = _Node(e, None, None)

if self.isempty():

self._head = newest else:

self._tail._link = newest newest._prev = self._tail self._tail = newest self._size += 1 def addFirst(self, e):

''' Adds the passed element at the beginning of the doubly linked list.

''' newest = _Node(e, None, None) if self.isempty():

self._head = newest self._tail = newest else:

newest._link = self._head self._head._prev = newest self._head = newest self._size += 1 def addAnywhere(self, e, index):

''' Adds the passed element at the passed index position of the doubly linked list.

''' if index >= self._size:

print(f'Index value out of range, it should be between 0 - {self._size - 1}') elif self.isempty():

print("List was empty, item will be added at the end") self.addLast(e) elif index == 0:

self.addFirst(e) elif index == self._size - 1:

self.addLast(e) else:

newest = _Node(e, None, None) p = self._head for _ in range(index - 1):

p = p._link newest._link = p._link p._link._prev = newest newest._prev = p p._link = newest

self._size += 1 def removeFirst(self):

''' Removes element from the beginning of the doubly linked list.

Returns the removed element.

''' MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER if self.isempty():

print('List is already empty') return e = self._head._element self._head = self._head._link self._size -= 1

if self.isempty():

self._tail = None else:

self._head._prev = None return e def removeLast(self):

''' Removes element from the end of the doubly linked list.

Returns the removed element.

''' if self.isempty():

print("List is already empty") return e = self._tail._element self._tail = self._tail._prev self._size -= 1

if self.isempty():

self._head = None else:

self._tail._link = None return e def removeAnywhere(self, index):

''' Removes element from the passed index position of the doubly linked list.

Returns the removed element.

''' if index >= self._size:

print(f'Index value out of range, it should be between 0 - {self._size - 1}') elif self.isempty():

print("List is empty") elif index == 0:

return self.removeFirst() elif index == self._size - 1:

return self.removeLast() else:

p = self._head for _ in range(index - 1):

p = p._link e = p._link._element p._link = p._link._link p._link._prev = p self._size -= 1

return e MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER def display(self):

''' Utility function to display the doubly linked list.

''' if self.isempty():

print("List is Empty") return p = self._head print("NULL< -->", end='') while p:

print(p._element, end="<-->") p = p._link print("NULL") print(f" \nHead : {self._head._element}, Tail :

{self._tail._element}") ################################################################### def options():

''' Prints Menu for operations ''' options_list = ['Add Last', 'Add First', 'Add Anywhere', 'Remove First', 'Remove Last', 'Remove Anywhere',

'Display List', 'Exit'] print("MENU") for i, option in enumerate(options_list):

print(f'{i + 1}. {option}') choice = int(input("Enter choice: ")) return choice def switch_case(choice):

''' Switch Case for operations ''' os.system('cls') if choice == 1:

elem = int(input("Enter Item: ")) DL.addLast(elem) print("Added Item at Last!\n\n") elif choice == 2:

elem = int(input("Enter Item: ")) DL.addFirst(elem) print("Added Item at First!\n\n") elif choice == 3:

elem = int(input("Enter Item: ")) index = int(input("Enter Index: ")) DL.addAnywhere(elem, index) MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB

B TECH I YEAR II SEMESTER elif choice == 4:

print("Removed Element from First:", DL.removeFirst()) elif choice == 5:

print("Removed Element from last:", DL.removeLast()) elif choice == 6:

index = int(input("Enter Index: ")) print(f"Removed Item: {DL.removeAnywhere(index)} !\n\n") elif choice == 7:

print("List:") DL.display() print("\n") elif choice == 8:

import sys sys.exit() ################################################################### if name == ' main ':

DL = DoublyLL() while True:

choice = options() switch_case( choice) Output:

MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER Signature of the Faculty MRCET EAMCET CODE : MLRD www.mrcet.ac.in

DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER Record Notes MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB

B TECH I YEAR II SEMESTER MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER PROGRAM-11 Date:

Aim:

Write a program to implement Breadth First Search Program:

# Program to print BFS traversal # from a given source vertex. BFS(int s) # traverses vertices reachable from s.

from collections import defaultdict # This class represents a directed graph # using adjacency list representation class Graph:

# Constructor def init (self):

# default dictionary to store graph self.graph = defaultdict(list) # function to add an edge to graph def addEdge(self,u,v):

self.graph[u].append(v) # Function to print a BFS of graph def BFS(self, s):

# Mark all the vertices as not visited visited = [False] * (max(self.graph) + 1) # Create a queue for BFS queue = [] # Mark the source node as

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

# Dequeue a vertex from # queue and print it s = queue.pop(0) print (s, end = " ") # Get all adjacent vertices of the

# dequeued vertex s. If a adjacent # has not been visited, then mark it # visited and enqueue it for i in self.graph[s]:

if visited[i] == False:

queue.append(i) visited[i] = True MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER

# Driver code # Create a graph given in # the above diagram g = Graph() g.addEdge(0, 1)

g.addEdge(0, 2) g.addEdge(1, 2) g.addEdge(2, 0) g.addEdge(2, 3) g.addEdge(3, 3)

print ("Following is Breadth First Traversal" " (starting from vertex 2)") g.BFS(2) Output:

Signature of the Faculty MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER Record Notes

MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB

B TECH I YEAR II SEMESTER PROGRAM-12 Date:

Aim:

Write a program to implement Depth First Search Program:

# Program to print DFS traversal # from a given given graph from collections import defaultdict # This class represents a directed graph using # adjacency list representation

class Graph:

# Constructor def init (self):

# default dictionary to store graph self.graph = defaultdict(list) # function to add an edge to graph def addEdge(self, u, v):

self.graph[u].append(v) # A function used by DFS def DFSUtil(self, v, visited):

# Mark the current node as visited # and print it visited.add(v) print(v, end=' ') # Recur for all the vertices

# adjacent to this vertex for neighbour in self.graph[v]:

if neighbour not in visited:

self.DFSUtil(neighbour, visited) # The function to do DFS traversal. It uses # recursive DFSUtil() def DFS(self, v):

# Create a set to store visited vertices visited = set() # Call the recursive helper function # to print DFS traversal self.DFSUtil(v, visited)

MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER # Driver code # Create a graph given

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

g.addEdge(2, 0) g.addEdge(2, 3) g.addEdge(3, 3) print("Following is DFS from (starting from vertex 2)") g.DFS(2)

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

g.addEdge(2, 0) g.addEdge(2, 3) g.addEdge(3, 3) print ("Following is Breadth First Traversal" " (starting from vertex 2)")

g.BFS(2) Output :

MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER Signature of the Faculty MRCET EAMCET CODE : MLRD www.mrcet.ac.in

DATA STRUCTURES AND its APPLICATIONS LAB B TECH I YEAR II SEMESTER Record Notes MRCET EAMCET CODE : MLRD www.mrcet.ac.in DATA STRUCTURES AND its APPLICATIONS LAB

B TECH I YEAR II SEMESTER