20 A.
Write a Python code to implement single source shortest
path algorithm.
ALGORITHM:
1. Initialize distances[] with ∞, set distances[start] = 0
2. Initialize priority queue PQ, add (0, start) to PQ
3. While PQ is not empty:
a. Extract the node u with the smallest distance from PQ
b. For each neighbor v of u:
i. Calculate new distance to v: dist[v] = dist[u] + weight(u, v)
ii. If new distance to v is smaller than current dist[v], update dist[v]
and push (dist[v], v) into PQ
4. Return distances[] (or the shortest path from start to each node)
PROGRAM:
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
pq = [(0, start)]
while pq:
curr_dist, node = [Link](pq)
if curr_dist > distances[node]:
continue
for neighbor, weight in graph[node]:
dist = curr_dist + weight
if dist < distances[neighbor]:
distances[neighbor] = dist
[Link](pq, (dist, neighbor))
return distances
graph = {
'A': [('B', 1), ('C', 4)],
'B': [('A', 1), ('C', 2), ('D', 5)],
'C': [('A', 4), ('B', 2), ('D', 1)],
'D': [('B', 5), ('C', 1)],
}
result = dijkstra(graph, 'A')
print(result)
OUTPUT:
{'A': 0, 'B': 1, 'C': 3, 'D': 4}
B. Write a Python code to find the Factorial value of given number
N using recursive function.
ALGORITHM:
[Link] function factorial(n) calls itself with n-1 until it reaches 1.
[Link] n reaches 1, the base case is triggered, returning 1.
[Link], the recursive calls start returning and multiplying the results together.
PROGRAM:
def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n - 1)
N = int(input("Enter a number: "))
result = factorial(N)
print(f"The factorial of {N} is {result}")
OUTPUT:
Enter a number: 5
The factorial of 5 is 120
19 A. Write a Python code to implement minimum spanning tree by
anyone algorithm.
ALGORITHM:
[Link] an array key[] with infinity for all nodes except the starting node
(set it to 0).
[Link] a priority queue (min-heap) to efficiently fetch the node with the
smallest key value.
[Link] the parent of each node to store the edges of the MST.
PROGRAM:
def prim(graph, start=0):
n = len(graph)
in_mst = [False] * n
key = [float('inf')] * n
key[start] = 0
mst_weight = 0
for _ in range(n):
u = min((key[v], v) for v in range(n) if not in_mst[v])[1]
in_mst[u] = True
mst_weight += key[u]
for v in range(n):
if graph[u][v] and not in_mst[v] and graph[u][v] < key[v]:
key[v] = graph[u][v]
return mst_weight
graph = [
[0, 2, 0, 6, 0],
[2, 0, 3, 8, 5],
[0, 3, 0, 0, 7],
[6, 8, 0, 0, 9],
[0, 5, 7, 9, 0]
]
print("Total weight of MST:", prim(graph))
OUTPUT:
Total weight of MST: 16
B. Write a Python code to sort the N elements using bubble sort.
ALGORITHM:
[Link] adjacent elements.
[Link] them if they are in the wrong order (i.e., the left element is larger than
the right one).
[Link] the process for each element, progressively reducing the number of
elements to compare, as the largest elements "bubble up" to the end .
PROGRAM:
def bubble_sort(arr):
for i in range(len(arr)):
for j in range(0, len(arr) - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
arr = [int(x) for x in input("Enter numbers separated by spaces: ").split()]
bubble_sort(arr)
print("Sorted array:", arr)
OUTPUT:
Enter numbers separated by spaces: 64 34 25 12 22 11 90
Sorted array: [11, 12, 22, 25, 34, 64, 90]
18 A. Write a Python code for Graph representation and Traverse it
by anyone algorithm.
PROGRAM:
class Graph:
def __init__(self):
[Link] = {}
def add_edge(self, u, v):
if u not in [Link]:
[Link][u] = []
if v not in [Link]:
[Link][v] = []
[Link][u].append(v)
[Link][v].append(u)
def dfs(self, start, visited=None):
if visited is None:
visited = set()
[Link](start)
print(start, end=" ")
for neighbor in [Link][start]:
if neighbor not in visited:
[Link](neighbor, visited)
def bfs(self, start):
visited = set()
queue = [start]
[Link](start)
while queue:
node = [Link](0)
print(node, end=" ")
for neighbor in [Link][node]:
if neighbor not in visited:
[Link](neighbor)
[Link](neighbor)
if __name__ == "__main__":
# Create a graph
g = Graph()
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(3, 5)
g.add_edge(4, 6)
print("DFS Traversal starting from node 1:")
[Link](1)
print("\n")
print("BFS Traversal starting from node 1:")
[Link](1)
OUTPUT:
DFS Traversal starting from node 1:
124635
BFS Traversal starting from node 1:
123456
[Link] a Python code to sort the N elements using selection sort.
PROGRAM:
def selection_sort(arr):
for i in range(len(arr)):
min_index = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
if __name__ == "__main__":
# Sample array to sort
arr = [64, 25, 12, 22, 11]
print("Original array:", arr)
selection_sort(arr)
print("Sorted array:", arr)
OUTPUT:
Original array: [64, 25, 12, 22, 11]
Sorted array: [11, 12, 22, 25, 64]
17 A. Write a Python code to implement Heap.
PROGRAM:
class MinHeap:
def __init__(self):
[Link] = []
def insert(self, value):
[Link](value)
self._heapify_up(len([Link]) - 1)
def _heapify_up(self, index):
while index > 0 and [Link][index] < [Link][(index - 1) // 2]:
[Link][index], [Link][(index - 1) // 2] = [Link][(index - 1) // 2],
[Link][index]
index = (index - 1) // 2
def extract_min(self):
if len([Link]) == 0:
return None
min_val = [Link][0]
[Link][0] = [Link]()
self._heapify_down(0)
return min_val
def _heapify_down(self, index):
smallest = index
left, right = 2 * index + 1, 2 * index + 2
if left < len([Link]) and [Link][left] < [Link][smallest]:
smallest = left
if right < len([Link]) and [Link][right] < [Link][smallest]:
smallest = right
if smallest != index:
[Link][index], [Link][smallest] = [Link][smallest],
[Link][index]
self._heapify_down(smallest)
heap = MinHeap()
[Link](10)
[Link](5)
[Link](20)
[Link](3)
print("Extracted min:", heap.extract_min())
OUTPUT:
Extracted min: 3
16. A. Write a Python code to implement Binary Search Trees by
satisfying its properties.
PROGRAM:
class Node:
def __init__(self, key):
[Link] = None
[Link] = None
[Link] = key
class BinarySearchTree:
def __init__(self):
[Link] = None
def insert(self, key):
if not [Link]:
[Link] = Node(key)
else:
self._insert([Link], key)
def _insert(self, node, key):
if key < [Link]:
if [Link] is None:
[Link] = Node(key)
else:
self._insert([Link], key)
elif key > [Link]:
if [Link] is None:
[Link] = Node(key)
else:
self._insert([Link], key)
def search(self, key):
return self._search([Link], key)
def _search(self, node, key):
if node is None or [Link] == key:
return node
if key < [Link]:
return self._search([Link], key)
return self._search([Link], key)
bst = BinarySearchTree()
[Link](50)
[Link](30)
[Link](70)
result = [Link](30)
print("Found" if result else "Not Found")
OUTPUT:
Found
15. A. Write a Python code for Tree representation and traverse by
Inorder.
PROGRAM:
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None
class BinaryTree:
def __init__(self):
[Link] = None
def inorder_traversal(self, root):
if root:
self.inorder_traversal([Link])
print([Link], end=" ")
self.inorder_traversal([Link])
if __name__ == "__main__":
root = Node(1)
[Link] = Node(2)
[Link] = Node(3)
[Link] = Node(4)
[Link] = Node(5)
[Link] = Node(6)
[Link] = Node(7)
tree = BinaryTree()
[Link] = root
print("Inorder Traversal: ")
tree.inorder_traversal([Link])
OUTPUT:
Inorder Traversal:
4251637
B. Write a Python code to find the Fibonacci value of N using
recursive function.
PROGRAM:
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
if __name__ == "__main__":
N = int(input("Enter a number N to find the Fibonacci value: "))
result = fibonacci(N)
print(f"Fibonacci value of {N} is: {result}")
OUTPUT:
Enter a number N to find the Fibonacci value: 9
Fibonacci value of 9 is: 34
12. A. Write a Python code to implement Hash table.
PROGRAM:
class HashTable:
def __init__(self, size):
[Link] = size
[Link] = [[] for _ in range(size)]
def _hash(self, key):
return hash(key) % [Link]
def insert(self, key, value):
index = self._hash(key)
for pair in [Link][index]:
if pair[0] == key:
pair[1] = value
return
[Link][index].append([key, value])
def search(self, key):
index = self._hash(key)
for pair in [Link][index]:
if pair[0] == key:
return pair[1]
return None
def display(self):
for i, pairs in enumerate([Link]):
print(f"Index {i}: {pairs}")
ht = HashTable(5)
[Link]("name", "Alice")
[Link]("age", 30)
[Link]("city", "New York")
print("Hash Table:")
[Link]()
print("Search for 'age':", [Link]("age"))
print("Search for 'country':", [Link]("country"))
OUTPUT:
Hash Table:
Index 0: []
Index 1: [['city', 'New York']]
Index 2: []
Index 3: [['name', 'Alice']]
Index 4: [['age', 30]]
Search for 'age': 30
Search for 'country': None
[Link] a Python code to implement the operations of List ADT
using linked list and perform the following
i. Create a Linked list with the elements 11,22,44,55
ii. Insert 33 after 22
iii. Delete the element 22 from the list
iv. Display the elements.
PROGRAM:
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
class LinkedList:
def __init__(self):
[Link] = None
def insert(self, data):
new_node = Node(data)
if not [Link]:
[Link] = new_node
else:
last = [Link]
while [Link]:
last = [Link]
[Link] = new_node
def insert_after(self, target, data):
current = [Link]
while current:
if [Link] == target:
new_node = Node(data)
new_node.next = [Link]
[Link] = new_node
return
current = [Link]
def delete(self, target):
current = [Link]
if current and [Link] == target:
[Link] = [Link]
current = None
return
prev = None
while current:
if [Link] == target:
[Link] = [Link]
current = None
return
prev = current
current = [Link]
def display(self):
current = [Link]
if not current:
print("List is empty.")
return
while current:
print([Link], end=" -> ")
current = [Link]
print("None")
if __name__ == "__main__":
linked_list = LinkedList()
linked_list.insert(11)
linked_list.insert(22)
linked_list.insert(44)
linked_list.insert(55)
print("List after creation:")
linked_list.display()
linked_list.insert_after(22, 33)
print("\nList after inserting 33 after 22:")
linked_list.display()
linked_list.delete(22)
print("\nList after deleting 22:")
linked_list.display()
OUTPUT:
List after creation:
11 -> 22 -> 44 -> 55 -> None
List after inserting 33 after 22:
11 -> 22 -> 33 -> 44 -> 55 -> NonE
List after deleting 22:
11 -> 33 -> 44 -> 55 -> None
10. A. Write a Python code to implement FIFO structure.
PROGRAM:
class Queue:
def __init__(self):
[Link] = []
def enqueue(self, item):
[Link](item)
def dequeue(self):
if not self.is_empty():
return [Link](0)
else:
return "Queue is empty"
def peek(self):
if not self.is_empty():
return [Link][0]
else:
return "Queue is empty"
def is_empty(self):
return len([Link]) == 0
def size(self):
return len([Link])
def display(self):
print("Queue:", [Link])
if __name__ == "__main__":
fifo_queue = Queue()
fifo_queue.enqueue(10)
fifo_queue.enqueue(20)
fifo_queue.enqueue(30)
fifo_queue.enqueue(40)
fifo_queue.display()
print("Dequeued element:", fifo_queue.dequeue())
print("Front element:", fifo_queue.peek())
fifo_queue.display()
print("Size of the queue:", fifo_queue.size())
print("Is the queue empty?", fifo_queue.is_empty())
fifo_queue.dequeue()
fifo_queue.dequeue()
fifo_queue.dequeue()
fifo_queue.dequeue()
print("Is the queue empty after clearing?", fifo_queue.is_empty())
OUTPUT:
Queue: [10, 20, 30, 40]
Dequeued element: 10
Front element: 20
Queue: [20, 30, 40]
Size of the queue: 3
Is the queue empty? False
Is the queue empty after clearing? True
9. A. Write a Python code to implement LIFO structure.
PROGRAM:
class Stack:
def __init__(self):
[Link] = []
def push(self, item):
[Link](item)
def pop(self):
if not self.is_empty():
return [Link]()
else:
return "Stack is empty"
def peek(self):
if not self.is_empty():
return [Link][-1]
else:
return "Stack is empty"
def is_empty(self):
return len([Link]) == 0
def size(self):
return len([Link])
def display(self):
print("Stack:", [Link])
if __name__ == "__main__":
lifo_stack = Stack()
lifo_stack.push(10)
lifo_stack.push(20)
lifo_stack.push(30)
lifo_stack.push(40)
lifo_stack.display()
print("Popped element:", lifo_stack.pop())
print("Top element:", lifo_stack.peek())
lifo_stack.display()
print("Size of the stack:", lifo_stack.size())
print("Is the stack empty?", lifo_stack.is_empty())
lifo_stack.pop()
lifo_stack.pop()
lifo_stack.pop()
lifo_stack.pop()
print("Is the stack empty after clearing?", lifo_stack.is_empty())
OUTPUT:
Stack: [10, 20, 30, 40]
Popped element: 40
Top element: 30
Stack: [10, 20, 30]
Size of the stack: 3
Is the stack empty? False
Is the stack empty after clearing? True
B. Write a Python code to find the element in a list by sequential
order.
PROGRAM:
def linear_search(arr, target):
for index, element in enumerate(arr):
if element == target:
return index
return -1
if __name__ == "__main__":
my_list = [5, 10, 15, 20, 25, 30]
target = 20
result = linear_search(my_list, target)
if result != -1:
print(f"Element {target} found at index {result}.")
else:
print(f"Element {target} not found in the list.")
OUTPUT:
Element 20 found at index 3.
8. A. Write a Python code to implement Queue using ADTs.
PROGRAM:
class Queue:
def __init__(self):
[Link] = []
def enqueue(self, item):
"""Add an item to the rear of the queue"""
[Link](item)
def dequeue(self):
"""Remove and return the front item of the queue"""
if self.is_empty():
raise IndexError("dequeue from empty queue")
return [Link](0)
def front(self):
"""Return the front item of the queue without removing it"""
if self.is_empty():
raise IndexError("front from empty queue")
return [Link][0]
def is_empty(self):
"""Check if the queue is empty"""
return len([Link]) == 0
def size(self):
"""Return the number of items in the queue"""
return len([Link])
def __str__(self):
"""String representation of the queue"""
return str([Link])
if __name__ == "__main__":
q = Queue()
[Link](10)
[Link](20)
[Link](30)
print("Queue after enqueuing 10, 20, 30:", q)
print("Front item:", [Link]())
print("Queue size:", [Link]())
print("Dequeue:", [Link]())
print("Queue after dequeuing:", q)
print("Is the queue empty?", q.is_empty())
print("Dequeue:", [Link]())
print("Dequeue:", [Link]())
print("Is the queue empty?", q.is_empty())
OUTPUT:
Queue after enqueuing 10, 20, 30: [10, 20, 30]
Front item: 10
Queue size: 3
Dequeue: 10
Queue after dequeuing: [20, 30]
Is the queue empty? False
Dequeue: 20
Dequeue: 30
Is the queue empty? True
B. Write a Python code to sort the N elements using merge sort.
PROGRAM:
def merge_sort(arr):
"""Main function to sort an array using merge sort."""
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
merge_sort(left_half)
merge_sort(right_half)
i=j=k=0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
if __name__ == "__main__":
arr = [38, 27, 43, 3, 9, 82, 10]
print("Original array:", arr)
merge_sort(arr)
print("Sorted array:", arr)
OUTPUT:
Original array: [38, 27, 43, 3, 9, 82, 10]
Sorted array: [3, 9, 10, 27, 38, 43, 82]
7. A. Write a Python code to implement Stack using ADTs.
PROGRAM:
class Stack:
def __init__(self):
[Link] = []
def push(self, item):
"""Add an item to the top of the stack"""
[Link](item)
def pop(self):
"""Remove and return the top item of the stack"""
if self.is_empty():
raise IndexError("pop from empty stack")
return [Link]()
def peek(self):
"""Return the top item of the stack without removing it"""
if self.is_empty():
raise IndexError("peek from empty stack")
return [Link][-1]
def is_empty(self):
"""Check if the stack is empty"""
return len([Link]) == 0
def size(self):
"""Return the number of items in the stack"""
return len([Link])
def __str__(self):
"""String representation of the stack"""
return str([Link])
if __name__ == "__main__":
s = Stack()
[Link](10)
[Link](20)
[Link](30)
print("Stack after pushing 10, 20, 30:", s)
print("Top item (peek):", [Link]())
print("Stack size:", [Link]())
print("Pop:", [Link]())
print("Stack after popping:", s)
print("Is the stack empty?", s.is_empty())
print("Pop:", [Link]())
print("Pop:", [Link]())
print("Is the stack empty?", s.is_empty())
OUTPUT:
Stack after pushing 10, 20, 30: [10, 20, 30]
Top item (peek): 30
Stack size: 3
Pop: 30
Stack after popping: [10, 20]
Is the stack empty? False
Pop: 20
Pop: 10
Is the stack empty? True
B. Write a Python code to search an element using Binary search.
PROGRAM:
def binary_search(arr, target):
"""Perform binary search to find the target element in the sorted array."""
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
if __name__ == "__main__":
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21]
target = 13
result = binary_search(arr, target)
if result != -1:
print(f"Element {target} found at index {result}.")
else:
print(f"Element {target} not found in the array.")
OUTPUT:
Element 13 found at index 6.
6. A. Write a Python code to implement List using linked list.
PROGRAM:
class Node:
def __init__(self, data):
"""Create a new node with given data."""
[Link] = data
[Link] = None
class LinkedList:
def __init__(self):
"""Initialize an empty linked list."""
[Link] = None
def insert(self, data):
"""Insert a new node at the end of the list."""
new_node = Node(data)
if not [Link]:
[Link] = new_node
else:
current = [Link]
while [Link]:
current = [Link]
[Link] = new_node
def print_list(self):
"""Print all elements of the list."""
current = [Link]
while current:
print([Link], end=" -> ")
current = [Link]
print("None")
if __name__ == "__main__":
linked_list = LinkedList()
linked_list.insert(10)
linked_list.insert(20)
linked_list.insert(30)
linked_list.print_list()
OUTPUT:
10 -> 20 -> 30 -> None
B. Write a Python code to search an element using linear search.
PROGRAM:
def linear_search(arr, target):
"""Perform linear search to find the target element in the list."""
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
if __name__ == "__main__":
arr = [10, 20, 30, 40, 50]
target = 30
result = linear_search(arr, target)
if result != -1:
print(f"Element {target} found at index {result}.")
else:
print(f"Element {target} not found in the list.")
OUTPUT:
Element 30 found at index 2.
5. A. Write a Python code to implement Queue using ADTs.
PROGRAM:
class Queue:
def __init__(self):
[Link] = []
def enqueue(self, item):
[Link](item)
def dequeue(self):
if not self.is_empty():
return [Link](0)
return "Queue is empty"
def peek(self):
if not self.is_empty():
return [Link][0]
return "Queue is empty"
def is_empty(self):
return len([Link]) == 0
q = Queue()
[Link](10)
[Link](20)
[Link](30)
print("Front element (peek):", [Link]())
print("Dequeued element:", [Link]())
print("Front element after dequeue (peek):", [Link]())
OUTPUT:
Front element (peek): 10
Dequeued element: 10
Front element after dequeue (peek): 20
4.B. Write a Python code to sort the N elements using quick sort.
PROGRAM:
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quick_sort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi - 1)
quick_sort(arr, pi + 1, high)
def sort_array(arr):
quick_sort(arr, 0, len(arr) - 1)
return arr
arr = [10, 7, 8, 9, 1, 5]
sorted_arr = sort_array(arr)
print("Sorted array:", sorted_arr)
OUTPUT:
Sorted array: [1, 5, 7, 8, 9, 10]
2. A. Implement List ADT to store the elements 10, 20,30,40,50 and
find any element and delete 30 from the list and display the
elements after deletion using Python arrays.
PROGRAM:
class ListADT:
def __init__(self):
[Link] = []
def insert(self, element):
[Link](element)
def find(self, element):
return element in [Link]
def delete(self, element):
if element in [Link]:
[Link](element)
def display(self):
return [Link]
list_adt = ListADT()
for num in [10, 20, 30, 40, 50]:
list_adt.insert(num)
print("Before deletion:", list_adt.display())
print("Found 30:", list_adt.find(30))
list_adt.delete(30)
print("After deletion:", list_adt.display())
OUTPUT:
Before deletion: [10, 20, 30, 40, 50]
Found 30: True
After deletion: [10, 20, 40, 50]
B. Write a Python code to sort the N elements using insertion sort.
PROGRAM:
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j=i-1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("Sorted array:", arr)
OUTPUT:
Sorted array: [5, 6, 11, 12, 13]
1. Write a Python code 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
retrieving the value of each type using ADTs.
PROGRAM:
class Flower:
def __init__(self, name: str, petals: int, price: float):
[Link] = name
[Link] = petals
[Link] = price
def set_name(self, name: str):
[Link] = name
def set_petals(self, petals: int):
[Link] = petals
def set_price(self, price: float):
[Link] = price
def get_name(self) -> str:
return [Link]
def get_petals(self) -> int:
return [Link]
def get_price(self) -> float:
return [Link]
flower1 = Flower("Rose", 15, 5.99)
print(f"Flower Name: {flower1.get_name()}")
print(f"Number of Petals: {flower1.get_petals()}")
print(f"Price: ${flower1.get_price()}")
flower1.set_name("Tulip")
flower1.set_petals(10)
flower1.set_price(3.49)
print("\nUpdated Flower Details:")
print(f"Flower Name: {flower1.get_name()}")
print(f"Number of Petals: {flower1.get_petals()}")
print(f"Price: ${flower1.get_price()}")
OUTPUT:
Flower Name: Rose
Number of Petals: 15
Price: $5.99
Updated Flower Details:
Flower Name: Tulip
Number of Petals: 10
Price: $3.49