PRACTICALS
DSA
PYTHON PROGRAM FOR PYTHON DATA TYPES
#string data type
x = "Hello World"
#display x:
print(x)
#display the data type of x:
print(type(x))
#integer data type
x = 20
#display x:
print(x)
#display the data type of x:
print(type(x))
#float data type
x = 20.5
#display x:
print(x)
#display the data type of x:
print(type(x))
#complex data type
c = 2 + 4j
print("\nType of c: ", type(c))
#list data type
List = ['GeeksForGeeks']
print("\nList with the use of String: ")
print(List)
List = ["Welcome", "to", "SYDS"]
print(List[0])
print(List[2])
#tuple data type
cars = ('BMW', 'Tesla', 'Ford', 'Toyota')
# trying to modify a tuple
#cars[0] = 'Nissan' # error
print(cars)
Tuple1 = tuple('Geeks')
print("\nTuple with the use of function: ")
print(Tuple1)
print(type(Tuple1))
Tuple1 = (0, 1, 2, 3)
Tuple2 = ('python', 'geek')
Tuple3 = (Tuple1, Tuple2)
print("\nTuple with nested tuples: ")
print(Tuple3)
# Boolean data type
print(type(True))
print(type(False))
# set data type
set1 = set()
print("Initial blank Set: ")
print(set1)
set1 = set("GeeksForGeeks")
print("\nSet with the use of String: ")
print(set1)
set1 = set(["Geeks", "For", "Geeks"])
print("\nSet with the use of List: ")
print(set1)
set1 = set([1, 2, 'Geeks', 4, 'For', 6, 'Geeks'])
print("\nSet with the use of Mixed Values")
print(type(set1))
#Dictionary data type
Dict = {1: 'Geeks', 2: 'For', 3: 'Geeks'}
print("\nDictionary with the use of Integer Keys: ")
print(Dict)
print(type(Dict))PYTHON PROGRAM FOR CLASS OBJECTS,INHERITANCE AND ENCAPSULATION or OOPs concepts
Class Objects
# Base class
class Animal:
def __init__(self, name, species):
self._name = name # Encapsulated attribute
self._species = species # Encapsulated attribute
# Encapsulated method
def _get_details(self):
return f"Name: {self._name}, Species: {self._species}"
# Public method
def speak(self):
pass
Inheritance
# Derived class inheriting from Animal
class Dog(Animal):
def __init__(self, name, breed):
super().__init__(name, "Dog")
self._breed = breed # Encapsulated attribute
# Overriding the speak method
def speak(self):
return f"{self._name} says Woof!"
# Public method to get breed
def get_breed(self):
return self._breed
# Derived class inheriting from Animal
class Cat(Animal):
def __init__(self, name, color):
super().__init__(name, "Cat")
self._color = color # Encapsulated attribute
# Overriding the speak method
def speak(self):
return f"{self._name} says Meow!"
# Public method to get color
def get_color(self):
return self._color
Encapsulation
# Encapsulated attributes are indicated by a single underscore
# Encapsulated methods are also indicated by a single underscore
# Accessing encapsulated details using public methods
dog = Dog("Buddy", "Golden Retriever")
cat = Cat("Whiskers", "Gray")
print(dog.get_breed()) # Output: Golden Retriever
print(cat.get_color()) # Output: Gray
# Accessing encapsulated details using the base class method
print(dog._get_details()) # Output: Name: Buddy, Species: Dog
print(cat._get_details()) # Output: Name: Whiskers, Species: Cat
Complete Program
the complete program divided according to the concepts:
# Class Objects
class Animal:
def __init__(self, name, species):
self._name = name # Encapsulated attribute
self._species = species # Encapsulated attribute
# Encapsulated method
def _get_details(self):
return f"Name: {self._name}, Species: {self._species}"
# Public method
def speak(self):
pass
# Inheritance
class Dog(Animal):
def __init__(self, name, breed):
super().__init__(name, "Dog")
self._breed = breed # Encapsulated attribute
# Overriding the speak method
def speak(self):
return f"{self._name} says Woof!"
# Public method to get breed
def get_breed(self):
return self._breed
class Cat(Animal):
def __init__(self, name, color):
super().__init__(name, "Cat")
self._color = color # Encapsulated attribute
# Overriding the speak method
def speak(self):
return f"{self._name} says Meow!"
# Public method to get color
def get_color(self):
return self._color
# Encapsulation
dog = Dog("Buddy", "Golden Retriever")
cat = Cat("Whiskers", "Gray")
print(dog.speak()) # Output: Buddy says Woof!
print(cat.speak()) # Output: Whiskers says Meow!
# Accessing encapsulated details using public methods
print(dog.get_breed()) # Output: Golden Retriever
print(cat.get_color()) # Output: Gray
# Accessing encapsulated details using the base class method
print(dog._get_details()) # Output: Name: Buddy, Species: Dog
print(cat._get_details()) # Output: Name: Whiskers, Species: Cat
PYTHON PROGRAM TO FIND AREA OF CIRCLE OR RECTANGLE
class Circle:
def __init__(self, radius):
self.radius = radius
def area(self):
return 3.14 * self.radius ** 2
class Rectangle:
def __init__(self, width, height):
self.width = width
self.height = height
def area(self):
return self.width * self.height
# Example usage
circle = Circle(5) # radius = 5
rectangle = Rectangle(4, 6) # width = 4, height = 6
print(f"Area of the circle: {circle.area()}")
print(f"Area of the rectangle: {rectangle.area()}")PYTHON PROGRAM FOR SINLY LINKED LIST
class Node:
def __init__(self, data):
self.data = data
self.next = None
def insert_at_beginning(head, data):
new_node = Node(data)
new_node.next = head
return new_node
def traverse(head):
current = head
while current:
# Print the current node's data followed by an arrow
print(str(current.data) + " -> ", end="")
current = current.next
print("None") # At the end of the list, print None to indicate no further nodes
# Singly linked list creation and its head stored in a variable
head = None
head = insert_at_beginning(head, 4)
head = insert_at_beginning(head, 3)
head = insert_at_beginning(head, 2)
head = insert_at_beginning(head, 1)
# To traverse and print the nodes:
traverse(head)PYTHON PROGRAM FOR DOUBLY LINKED LIST
class Node:
def __init__(self, data):
#Initialize a new node with data, previous, and next
self.data = data
self.next = None
def tranverse(head):
#Traverse the doubly linked list and print its elements
current = head
while current:
#print current node's data
print(current.data,end='<->')
#move to the next node
current = current.next
print('None')
def insert_at_beginning(head,data):
#insert a new node at the beginning of the doubly linked
new_node = Node(data)
new_node.next = head
if head:
head.prev = new_node
return new_node
#driver code
head = None
head = insert_at_beginning(head,4)
head = insert_at_beginning(head,3)
head = insert_at_beginning(head,2)
head = insert_at_beginning(head,1)
#to traverse and print the nodes:
tranverse(head)PYTHON PROGRAM TO IMPLEMENT STACK
stack = []
#append() function to push
#element in the stack
stack.append('a')
stack.append('b')
stack.append('c')
print('Initial stack')
print(stack)
#pop() function to pop
#element from stack in
# LIFO order
print('\nElements poped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())
print('\nStack after elements are poped:')
print(stack)PYTHON PROGRAM FOR BRACKET MATCHING
def areBracketBalanced(expr):
stack = []
#Traversing the Expression
for char in expr:
if char in ["(", "{", "["]:
#Push the element in the stack
stack.append(char)
else:
#if current character is not opening
#bracket, then it must be closing.
#so stack cannot be empty at this point.
if not stack:
return False
current_char = stack.pop()
if current_char == '(':
if char != ')':
return False
if current_char == '{':
if char != '}':
return False
if current_char == '[':
if char != ']':
return False
#Check Empty Stack
if stack:
return False
return True
#Driver Code
if __name__ == "__main__":
expr = "{()}[}]"
if areBracketBalanced(expr):
print("Balanced")
else:
print("Not Balanced")
PYTHON PROGRAM TO IMPLEMENT QUEUE AND WITH HELP OF ENQUEU AND DEQUEU OR IMPLEMENT USING STACK
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)
# FIFO orderUSING STACK
class QueueUsingStacks:
def __init__(self):
self.stack1 = []
self.stack2 = []
def enqueue(self,item):
self.stack1.append(item)
def dequeue(self):
if not self.stack2:
while self.stack1:
self.stack2.append(self.stack1.pop())
if not self.stack2:
raise IndexError("Dequeue from empty queue")
return self.stack2.pop()
#Example usages:
queue = QueueUsingStacks()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue()) # Output: 1
print(queue.dequeue()) # Output: 2
print(queue.dequeue()) # Output: 3PYTHON PROGRAM FOR PREORDER, INORDER AND POSTORDER TRAVERSAL
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def preorder(root):
if root:
print(root.val, end=' ')
preorder(root.left)
preorder(root.right)
def inorder(root):
if root:
inorder(root.left)
print(root.val, end=' ')
inorder(root.right)
def postorder(root):
if root:
postorder(root.left)
postorder(root.right)
print(root.val, end=' ')
# Example usage
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("Preorder traversal:")
preorder(root) # Output: 1 2 4 5 3
print("\nInorder traversal:")
inorder(root) # Output: 4 2 5 1 3
print("\nPostorder traversal:")
postorder(root) # Output: 4 5 2 3 1PYTHON PROGRAM TO SHOW BFS TRAVERSAL
Node Class Definition
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
BFS Traversal Function
from collections import deque
def bfs_traversal(root):
if root is None:
return
# Create an empty queue for level order traversal
queue = deque()
# Enqueue root and initialize height
queue.append(root)
while queue:
# Print front of queue and remove it from queue
node = queue.popleft()
print(node.val, end=' ')
# Enqueue left child
if node.left:
queue.append(node.left)
# Enqueue right child
if node.right:
queue.append(node.right)
Example Usage
if __name__ == "__main__":
# Creating a sample binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("BFS traversal of binary tree is:")
bfs_traversal(root)
COMBINED
from collections import deque
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def bfs_traversal(root):
if root is None:
return
# Create an empty queue for level order traversal
queue = deque()
# Enqueue root and initialize height
queue.append(root)
while queue:
# Print front of queue and remove it from queue
node = queue.popleft()
print(node.val, end=' ')
# Enqueue left child
if node.left:
queue.append(node.left)
# Enqueue right child
if node.right:
queue.append(node.right)
if __name__ == "__main__":
# Creating a sample binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("BFS traversal of binary tree is:")
bfs_traversal(root)
BFS traversal of binary tree is:
1 2 3 4 5 6 7
PYTHON PROGRAM OT DEMOSTARTE THE MAXIMUM AND MINIMUM NODE IN A TREE
MAXIMUM NODE :
class newNode:
def __init__(self, data):
self.data = data
self.left = self.right = None
def Findmax(root):
if root is None:
return float('-inf')
lres = Findmax(root.left)
rres = Findmax(root.right)
res = root.data
if lres > res:
res = lres
if rres > res:
res = rres
return res
if __name__ == '__main__':
root = newNode(2)
root.left = newNode(7)
root.right = newNode(5)
root.left.right = newNode(6)
root.left.right.left = newNode(7)
root.left.right.right = newNode(11)
root.right.right = newNode(9)
root.right.right.left = newNode(4)
print('Maximum element is:', Findmax(root))
MINIMUM NODE:
class newNode:
def __init__(self, data):
self.data = data
self.left = self.right = None
def Findmin(root):
if root is None:
return float('inf')
lres = Findmin(root.left)
rres = Findmin(root.right)
res = root.data
if lres < res:
res = lres
if rres < res:
res = rres
return res
if __name__ == '__main__':
root = newNode(2)
root.left = newNode(7)
root.right = newNode(5)
root.left.right = newNode(6)
root.left.right.left = newNode(7)
root.left.right.right = newNode(11)
root.right.right = newNode(9)
root.right.right.left = newNode(4)
print('Minimum element is:', Findmin(root))
PYTHON PROGRAM TO SHOW BUBBLE SORT
def bubble_sort(arr):
n = len(arr)
# Traverse through all array elements
for i in range(n):
# Last i elements are already sorted
for j in range(0, n-i-1):
# Traverse the array from 0 to n-i-1
# Swap if the element found is greater
# than the next element
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
# Example usage:
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array is:", arr)
PYTHON PROGRAM TO IMPLEMENT BINARY SEARCH TREE
#python program to demonstrate
#insert operation in binary search tree
class Node:
def __init__(self,key):
self.left=None
self.right=None
self.val=key
def insert(root,key):
if root is None:
return Node(key)
if root.val == key:
return root
if root.val < key:
root.right = insert(root.right,key)
else:
root.left = insert(root.left,key)
return root
def inorder(root):
if root:
inorder(root.left)
print(root.val,end=" ")
inorder(root.right)
#creating the following BST
# 50
# / \
# 30 70
# / \ / \
# 20 40 60 80
r = Node(50)
r = insert(r,30)
r = insert(r,40)
r = insert(r,20)
r = insert(r,50)
r = insert(r,60)
r = insert(r,70)
r = insert(r,80)
print("inorder traversal of the given tree")
inorder(r)PYTHON PROGRAM TO SHOW WHETHER THE TREE IS BALANCED OR NOT
class Node:
def __init__(self,data):
self.data = data
self.left = self.right = None
class Height:
def __init__(self):
self.height = 0
def isHeightBalanced(root,height):
left_height = Height()
right_height = Height()
if root is None:
return True
l = isHeightBalanced(root.left,left_height)
r = isHeightBalanced(root.right,right_height)
height.height = max(left_height.height,right_height.height) + 1
if abs(left_height.height - right_height.height) <=1:
return l and r
return False
height = Height()
root = Node(1)
root.left= Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
if isHeightBalanced(root,height):
print("The tree is height-balanced")
else:
print("The tree is not height-balanced")PYTHON PROGRAM FOR SELECTION SORT
# Selection sort in Python
# time complexity O(n*n)
#sorting by finding min_index
def selection_Sort(array, size):
for ind in range(size):
min_index = ind
for j in range(ind + 1, size):
# select the minimum element in every iteration
if array[j] < array[min_index]:
min_index = j
# swapping the elements to sort the array
(array[ind], array[min_index]) = (array[min_index], array[ind])
arr = [-2, 45, 0, 11, -9,88,-97,-202,747]
size = len(arr)
selection_Sort(arr, size)
print('The array after sorting in Ascending Order by selection sort is:')
print(arr)PYTHON PROGRAM FOR INSERTION SORT
def insertion_sort(arr):
n=len(arr)
if n<=1:
return
for i in range (1,n):
key = arr[i]
j=i-1
while j>=0 and key < arr[j]:
arr[j+1] = arr[j]
j-=1
arr[j+1]=key
arr=[12,11,13,5,6]
insertion_sort(arr)
print(arr)PYTHON PROGRAM FOR LINEAR SEARCH
def linear_search(list1 , n, key):
for i in range(0,n):
if (list1[i] == key):
return i
return -1
list1 = [1,3,5,4,7,9]
key = 7
n = len(list1)
result = linear_search(list1,n,key)
if result == -1:
print('element not found')
else:
print('element found at index',result)PYTHON PROGRAM TO SHOW THE USE OF HASHING
import hashlib
def compute_sha256_hash(input_string):
hash_obj = hashlib.sha256()
hash_obj.update(input_string.encode('utf-8'))
return hash_obj.hexdigest()
def main():
# example string to hash
string = [
"hello,world!",
"python hashing",
"openAi chatgpt",
"1234567890"
]
# compute and print the hash for each string
for s in string:
hash_value = compute_sha256_hash(s)
print(f"original string: {s}")
print(f"SHA-256 Hash: {hash_value}")
print('_'*40)
if __name__ == "__main__":
main()
PYTHON PROGRAM TO SHOW USE OF SIMPLE SYMBOL TABLE
class SymbolTable:
def __init__(self):
self.table = {}
def add_symbol(self, symbol, value):
self.table[symbol] = value
print(f"Symbol '{symbol}' added with value {value}")
def get_symbol(self, symbol):
return self.table.get(symbol, None)
def remove_symbol(self, symbol):
if symbol in self.table:
del self.table[symbol]
print(f"Symbol '{symbol}' removed")
else:
print(f"Symbol '{symbol}' not found")
def display(self):
print("Symbol Table:")
for symbol, value in self.table.items():
print(f"{symbol}: {value}")
# Example usage
if __name__ == "__main__":
st = SymbolTable()
# Adding symbols
st.add_symbol('x', 10)
st.add_symbol('y', 20)
st.add_symbol('z', 30)
# Displaying the symbol table
st.display()
# Retrieving a symbol
value = st.get_symbol('y')
print(f"Value of 'y': {value}")
# Removing a symbol
st.remove_symbol('x')
# Displaying the symbol table after removalDSA PRACTICAL - Google Drive
https://drive.google.com/drive/folders/1F-6lG3sompnBtZwgsrPT7OhYDxHdxIl-?usp=drive_link