19CS303 – Fundamentals of Data Structures using Python

ANSWER KEY
PART A

PART C

*QC10 (a)
1 I) Create a Python program to find the sequences of one Lower case letter followed by Upper
case letters. (8 Marks)

Ans

import re
def text_match(text):
patterns = '[A-Z]+[a-z]+$'
if [Link](patterns, text):
return 'Found a match!'
else:
return('Not matched!')
print(text_match("AaBbGg"))
print(text_match("Python"))
print(text_match("python"))
print(text_match("PYTHON"))
print(text_match("aA"))
print(text_match("Aa"))

OUTPUT:
Found a match!
Found a match!
Not matched!
Not matched!
Not matched!
Found a match!

II) Design a Python program to check whether a number is an Armstrong number or not. (7
marks)

Ans:

def is_armstrong(number):
# Convert the number to string to get the number of digits
num_str = str(number)
num_digits = len(num_str)
1
 # Calculate the sum of digits raised to the power of the number of digits
total = sum(int(digit) ** num_digits for digit in num_str)

# Check if the sum is equal to the original number

return total == number

# Main function
def main():
# Accept number input
number = int(input("Enter a number: "))

# Check if it's Armstrong

if is_armstrong(number):
print(f"{number} is an Armstrong number.")
else:
print(f"{number} is not an Armstrong number.")

# Run the program

main()

Enter a number: 153

153 is an Armstrong number.

Enter a number: 123

123 is not an Armstrong number.
(b) Write a Python program that accepts a sentence from the user, and then:
1. Counts the number of vowels.
2. Reverses the sentence.
3. Counts how many words are in the sentence.
4. Converts every word's first letter to uppercase (title case).

# Function to count vowels in a sentence

def count_vowels(sentence):
vowels = "aeiouAEIOU"
count = 0
for char in sentence:
if char in vowels:
count += 1
return count
*QC10
1
# Function to reverse a sentence
def reverse_sentence(sentence):
return sentence[::-1]

# Function to count words

def count_words(sentence):
words = [Link]()
return len(words)

# Function to title-case each word

def title_case(sentence):
return [Link]()

# Main function
2
 def main():
sentence = input("Enter a sentence: ")

print("\n--- Results ---")

print("Original Sentence:", sentence)
print("Number of Vowels:", count_vowels(sentence))
print("Reversed Sentence:", reverse_sentence(sentence))
print("Number of Words:", count_words(sentence))
print("Title Case Sentence:", title_case(sentence))

# Run the program

main()

Output:

Enter a sentence:
hello how are you

--- Results ---

Original Sentence: hello how are you
Number of Vowels: 7
Reversed Sentence: uoy era woh olleh
Number of Words: 4
Title Case Sentence: Hello How Are You

(a) Write a Python program to Get the employee and patient details & display it using Hierarchical
inheritance.
Note: create a parent (base) class name Details and two child (derived) classes
named Employee and Patient.

# Base class
class Details:
def __init__(self, id, name, gender):
[Link] = id
[Link] = name
[Link] = gender

def display_details(self):
print(f"Id: {[Link]}")
*QC20 print(f"Name: {[Link]}")
1 print(f"Gender: {[Link]}")

# Derived class: Employee

class Employee(Details):
def __init__(self, id, name, gender, company, department):
super().__init__(id, name, gender)
[Link] = company
[Link] = department

def display_details(self):
print("Employee Object")
super().display_details()
print(f"Company: {[Link]}")
print(f"Department: {[Link]}")

3
# Derived class: Patient
class Patient(Details):
def __init__(self, id, name, gender, hospital, department):
super().__init__(id, name, gender)
[Link] = hospital
[Link] = department

def display_details(self):
print("Patient Object")
super().display_details()
print(f"Hospital: {[Link]}")
print(f"Department: {[Link]}")

# Main function
def main():
# Input for Employee
eid = int(input())
ename = input()
egender = input()
ecompany = input()
edepartment = input()

employee = Employee(eid, ename, egender, ecompany, edepartment)

# Input for Patient

pid = int(input())
pname = input()
pgender = input()
phospital = input()
pdepartment = input()

patient = Patient(pid, pname, pgender, phospital, pdepartment)

# Output
employee.display_details()
print()
patient.display_details()

# Run the program

main()

OUTPUT:

121
Srini
Male
AMS
EEE
201
Raj
Male
AIMS
Ear
Employee Object
4
 Id: 121
Name: Srini
Gender: Male
Company: AMS
Department: EEE

Patient Object
Id: 201
Name: Raj
Gender: Male
Hospital: AIMS
Department: Ear
(b) Design a python code to implement a parameterized constructor that will initialize the
employee_name, employee_id , basic pay, da, hra, cca, pf, ded of an employee and print
the details using user defined function.

class Employee:
def __init__(self, employee_name, employee_id, basic_pay, da, hra, cca, pf, ded):
# Parameterized constructor
self.employee_name = employee_name
self.employee_id = employee_id
self.basic_pay = basic_pay
[Link] = da
[Link] = hra
[Link] = cca
[Link] = pf
[Link] = ded

def display_details(self):
# User-defined function to print details
print(f"\nEmployee Details:")
print(f"Name : {self.employee_name}")
*QC20 print(f"Employee ID : {self.employee_id}")
1 print(f"Basic Pay : {self.basic_pay}")
print(f"DA : {[Link]}")
print(f"HRA : {[Link]}")
print(f"CCA : {[Link]}")
print(f"PF : {[Link]}")
print(f"Deductions : {[Link]}")

gross_pay = self.basic_pay + [Link] + [Link] + [Link]

net_pay = gross_pay - [Link] - [Link]
print(f"Gross Pay : {gross_pay}")
print(f"Net Pay : {net_pay}")

# Example usage:
emp1 = Employee(
employee_name="Alice Smith",
employee_id="EMP123",
basic_pay=30000,
da=5000,
hra=8000,
cca=1000,
5
 pf=2000,
ded=1500
)

emp1.display_details()

OUTPUT:

Employee Details:
Name : Alice Smith
Employee ID : EMP123
Basic Pay : 30000
DA : 5000
HRA : 8000
CCA : 1000
PF : 2000
Deductions : 1500
Gross Pay : 44000
Net Pay : 40500

(a) I) Create a Python function to delete a float element from and insert a float element into the
circular queue.

Ans

class CircularQueue:
def __init__(self, size):
[Link] = size
[Link] = [None] * size # Initialize empty queue
[Link] = -1
[Link] = -1

def enqueue(self, value):

if not isinstance(value, float):
print("Only float values are allowed.")
return
QC301
# Check if queue is full
if ([Link] + 1) % [Link] == [Link]:
print("Queue is full. Cannot insert.")
return

# First element to be inserted

if [Link] == -1:
[Link] = 0
[Link] = 0
else:
[Link] = ([Link] + 1) % [Link]

[Link][[Link]] = value
print(f"Inserted: {value}")

def dequeue(self):
if [Link] == -1:

6
 print("Queue is empty. Cannot delete.")
return None

removed = [Link][[Link]]
[Link][[Link]] = None

# If the queue becomes empty after deletion

if [Link] == [Link]:
[Link] = -1
[Link] = -1
else:
[Link] = ([Link] + 1) % [Link]

print(f"Deleted: {removed}")
return removed

def display(self):
if [Link] == -1:
print("Queue is empty.")
return

print("Queue elements:")
i = [Link]
while True:
print([Link][i], end=" ")
if i == [Link]:
break
i = (i + 1) % [Link]
print()

# Example usage
cq = CircularQueue(5)
[Link](1.1)
[Link](2.2)
[Link](3.3)
[Link]()
[Link]()
[Link]()
[Link](4.4)
[Link](5.5)
[Link](6.6) # This may fill the queue
[Link]()
[Link](7.7) # Should print "Queue is full"

OUTPUT:
Inserted: 1.1
Inserted: 2.2
Inserted: 3.3
Queue elements:
1.1 2.2 3.3
Deleted: 1.1
Queue elements:
2.2 3.3
Inserted: 4.4
Inserted: 5.5
7
 Inserted: 6.6
Queue elements:
2.2 3.3 4.4 5.5 6.6
Queue is full.

(b) i)Write a Python program to insert 14, 15 at FRONT END of deque using collection built-in
function. (8 marks)
For example:
Input Result

11 The deque after appending is :

12 deque([15, 14, 11, 12, 13])
13

from collections import deque

# Create an empty deque

d = deque()

# Take 3 user inputs and append to the deque

for _ in range(3):
num = int(input())
[Link](num)

# Insert 15 and 14 at the front end

[Link](14)
[Link](15)

# Display the final deque

*QC30
print("The deque after appending is :")
1
print(d)

Output:
11
12
13
The deque after appending is :
deque([15, 14, 11, 12, 13])

ii)Write a Python program to delete element at REAR END of deque using collection built-in
function. (7 marks)

For example:
Input Result

p The deque after deleting at right is :

y deque(['p', 'y'])
t

from collections import deque

# Create an empty deque

d = deque()
8
 # Take 3 character inputs
for _ in range(3):
ch = input()
[Link](ch)

# Delete from rear (right side)

[Link]()

# Display the final deque

print("The deque after deleting at right is :")
print(d)

Output:

p
y
t
The deque after deleting at right is :
deque(['p', 'y'])
[Link]() removes the last element from the deque (i.e., from the right/rear).
(a) Write a python function def insert(self, k): to insert the nodes in a B+ Tree.

PROGRAM
class Node(object):

def __init__(self, order):

[Link] = order
[Link] = []
[Link] = []
[Link] = True

def add(self, key, value):

if not [Link]:
[Link](key)
*QC40 [Link]([value])
1 return None

for i, item in enumerate([Link]):

if key == item:
[Link][i].append(value)
break

elif key < item:

[Link] = [Link][:i] + [key] + [Link][i:]
[Link] = [Link][:i] + [[value]] + [Link][i:]
break

elif i + 1 == len([Link]):
[Link](key)
9
 [Link]([value])

def split(self):

left = Node([Link])
right = Node([Link])
mid = [Link] // 2

[Link] = [Link][:mid]
[Link] = [Link][:mid]

[Link] = [Link][mid:]
[Link] = [Link][mid:]

[Link] = [[Link][0]]
[Link] = [left, right]
[Link] = False

def is_full(self):

return len([Link]) == [Link]

def show(self, counter=0):

print(counter, str([Link]))

if not [Link]:
for item in [Link]:
[Link](counter + 1)

class BPlusTree(object):

def __init__(self, order=8):

[Link] = Node(order)

def _find(self, node, key):

for i, item in enumerate([Link]):

if key < item:
return [Link][i], i
return [Link][i + 1], i + 1

def _merge(self, parent, child, index):

[Link](index)
pivot = [Link][0]

for i, item in enumerate([Link]):

if pivot < item:
[Link] = [Link][:i] + [pivot] + [Link][i:]
[Link] = [Link][:i] + [Link] + [Link][i:]
break

10
 elif i + 1 == len([Link]):
[Link] += [pivot]
[Link] += [Link]
break

def insert(self, key, value):

parent = None
child = [Link]

while not [Link]:

parent = child
child, index = self._find(child, key)

[Link](key, value)

if child.is_full():
[Link]()

if parent and not parent.is_full():

self._merge(parent, child, index)

def retrieve(self, key):

child = [Link]

while not [Link]:

child, index = self._find(child, key)

for i, item in enumerate([Link]):

if key == item:
return [Link][i]

return None
def show(self):

[Link]()

def demo_node():
node = Node(order=4)
[Link]('a', 'alpha')
[Link]('b', 'bravo')
[Link]('c', 'charlie')
[Link]('d', 'delta')
[Link]()

print('\nSplitting node...')
[Link]()
[Link]()

def demo_bplustree():
print('B+ tree...')

11
 bplustree = BPlusTree(order=4)
x=’f’
y=’ab’
[Link]('a', 'alpha')
[Link]('b', 'bravo')
[Link]('c', 'charlie')
[Link]('d', 'delta')
[Link]('e', 'echo')
[Link](x,y)
[Link]()

if __name__ == '__main__':
demo_node()
print('\n')
demo_bplustree()

(b) Explain Set Operations such as a) UNION b) FIND c) INTERSECTION using TREE Data
Structure?

Ans

Union Find

A Union-Find/Disjoint set data structure is used to maintain a set of elements partitioned into a

number of mutually non-overlapping subsets.

Disjoint Set —A disjoint set is a group of sets where no item can be in more than one set. In other

words, if we take any two sets from the Disjoint set then their intersection will result in an empty set.

QC401 In even simpler terms a disjoint set is a data structure where similar elements are kept in a single

group.

There are two main operations DSU performs on sets:

12
Find — Tells us an element/node belongs to which subset.

Union — Join two subsets, if they share a common attribute

In this approach, we represent the nodes using an array, and the value of the item at that index tells

which set that node belongs to. Depending upon the strategy used the value may represent its

parent or the reference to the representative of the set.

Quick Find

class QuickFind():
def __init__(self,N):
self._parents = list(range(0, N))def find(self, p):
return(self._parents[p])

def union(self, p, q):

root_p, root_q = self._parents[p], self._parents[q]
for i in range(0, len(self._parents)):
if(self._parents[i] == root_p):
self._parents[i] = root_q def connected(self,p,q):
return self._parents[p] == self._parents[q]

Quick Union

class QuickUnion():
def __init__(self,N):
self._parents = list(range(0,N))

13
 def find(self, p):
while(p != self._parents[p]):
p = self._parents[p]
return p

def union(self, p, q):

root_p, root_q = [Link](p), [Link](q)
self._parents[i] = root_q def connected(self, p, q):
return [Link](p)==[Link](q)

Optimized Disjoint Set

We can significantly improve the implementation of the disjoint set by using two techniques:

Union By Rank — Union by rank always attaches the shorter tree to the root of the taller tree.

Path Compression — By making every other node in the path point to its grandparent's node, we

can constantly flatten the tree by altering the parent node to the root node and halving the path

length.

Weighted Quick Union with optimization

class DisJointSets():
def __init__(self,N):
# Initially, all elements are single element subsets
self._parents = [node for node in range(N)]
self._ranks = [1 for _ in range(N)]

def find(self, u):

while u != self._parents[u]:
# path compression technique
self._parents[u] = self._parents[self._parents[u]]
u = self._parents[u]
return u

def connected(self, u, v):

14
 return [Link](u) == [Link](v)

def union(self, u, v):

# Union by rank optimization
root_u, root_v = [Link](u), [Link](v)
if root_u == root_v:
return True
if self._ranks[root_u] > self._ranks[root_v]:
self._parents[root_v] = root_u
elif self._ranks[root_v] > self._ranks[root_u]:
self._parents[root_u] = root_v
else:
self._parents[root_u] = root_v
self._ranks[root_v] += 1
return False

Time Complexity

Find — log(N)

Union — log(N)

Problem 1

N students applied for admission to ABC Academy. An array of integers B is given representing

the strengths of N people i.e. B[i] represents the strength of the ith student. Among the N students,

some of them knew each other. A matrix C of size M x 2 is given which represents relations where

ith relations depict that C[i][0] and C[i][1] knew each other. All students who know each other are

placed in one batch. The strength of a batch is equal to the sum of the strength of all the students in

it. ABC sets criteria for selection: All those batches having a strength of at least D are selected.

Find the number of batches selected.

Example:

N=7
B = [1, 6, 7, 2, 9, 4, 5]
C = [[1, 2], [2, 3], [5, 6], [5, 7]]
D = 12Ans: 2
Initial Batches :
Batch 1 = {1, 2, 3} Batch Strength = 1 + 6 + 7 = 14
Batch 2 = {4} Batch Strength = 2
Batch 3 = {5, 6, 7} Batch Strength = 9 + 4 + 5 = 18
Selected Batches are Batch 1 and Batch 2.

15
 We have to create subsets where only students who are friends are in a single subset. Disjoint Sets

will be the right choice here.

Code Implementation

def solve(N, B, C, D):

parent = list(range(N))
def find(x):
if x != parent[x]:
parent[x] = find(parent[x])
return parent[x]

def union(x, y):

parent_x = find(x)
parent_y = find(y)
if parent_x != parent_y:
parent[parent_y] = parent_x

for x, y in C:
union(x-1, y-1)

from collections import defaultdict

dict_pair = defaultdict(list)
for idx, val in enumerate(parent):
dict_pair[find(val)].append(B[idx])

res = 0
for v in dict_pair.values():
if sum(v) >= D:
res += 1
return res

(a) Write a Python program to implement BFS and DFS traversal from a given source vertex.

from collections import deque, defaultdict

class Graph:
def __init__(self):
[Link] = defaultdict(list)

*QC50 def add_edge(self, u, v):

1 [Link][u].append(v)
# Uncomment the next line if the graph is
undirected:
# [Link][v].append(u)

def bfs(self, start):

visited = set()
queue = deque([start])
[Link](start)

16
 print("BFS Traversal:", end=" ")

while queue:
vertex = [Link]()
print(vertex, end=" ")

for neighbor in [Link][vertex]:

if neighbor not in visited:
[Link](neighbor)
[Link](neighbor)

print()

def dfs_util(self, vertex, visited):

[Link](vertex)
print(vertex, end=" ")

for neighbor in [Link][vertex]:

if neighbor not in visited:
self.dfs_util(neighbor, visited)

def dfs(self, start):

visited = set()
print("DFS Traversal:", end=" ")
self.dfs_util(start, visited)
print()

# Main program
if __name__ == "__main__":
g = Graph()

n = int(input("Enter number of edges: "))

print("Enter edges in the format 'u v':")
for _ in range(n):
u, v = input().split()
g.add_edge(u, v)

source = input("Enter source vertex for

traversal:”)

[Link](source)
[Link](source)

Output:
Enter number of edges: 5
Enter edges in the format 'u v':
AB
AC
BD
CD
DE
Enter source vertex for traversal: A

BFS Traversal: A B C D E
DFS Traversal: A B D E C
17
 (b) Explain Kruskal’s algorithm in detail. Write a Python program for the same to find the
Minimum Spanning Tree of a given connected, undirected and weighted graph.

Kruskal's Algorithm for Minimum Spanning Tree (MST)

Kruskal’s Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of
a connected, undirected, and weighted graph.

Key Concepts

A Spanning Tree is a subgraph that includes all the vertices of the original graph and is a single
connected tree.

A Minimum Spanning Tree (MST) is a spanning tree with the least total edge weight.

Kruskal’s algorithm selects edges in increasing order of weight and adds them to the MST only
if they don’t form a cycle.

Steps of Kruskal’s Algorithm

Sort all edges in the graph by their weights in ascending order.

Initialize the MST as an empty set.

QC501 Use a Disjoint Set Union (DSU) or Union-Find structure to keep track of connected
components.

Iterate through the sorted edges and for each edge:

If the vertices it connects are in different sets, include the edge in the MST and merge the sets.

If they are in the same set, skip it (to avoid a cycle).

Repeat until MST contains (V - 1) edges, where V is the number of vertices.

Python Implementation

class DisjointSet:

def __init__(self, vertices):

[Link] = {v: v for v in vertices}

[Link] = {v: 0 for v in vertices}

def find(self, v):

if [Link][v] != v:

18
 [Link][v] = [Link]([Link][v]) # Path compression

return [Link][v]

def union(self, u, v):

root_u = [Link](u)

root_v = [Link](v)

if root_u != root_v:

# Union by rank

if [Link][root_u] > [Link][root_v]:

[Link][root_v] = root_u

elif [Link][root_u] < [Link][root_v]:

[Link][root_u] = root_v

else:

[Link][root_v] = root_u

[Link][root_u] += 1

return True

return False

def kruskal(vertices, edges):

ds = DisjointSet(vertices)

mst = []

total_weight = 0

# Sort edges by weight

[Link](key=lambda edge: edge[2])

for u, v, weight in edges:

if [Link](u, v):

19
 [Link]((u, v, weight))

total_weight += weight

return mst, total_weight

# Example usage

vertices = ['A', 'B', 'C', 'D', 'E']

edges = [

('A', 'B', 1),

('A', 'C', 3),

('B', 'C', 1),

('B', 'D', 6),

('C', 'D', 4),

('C', 'E', 2),

('D', 'E', 5)

mst, weight = kruskal(vertices, edges)

print("Edges in MST:")

for u, v, w in mst:

print(f"{u} - {v}: {w}")

print(f"Total Weight of MST: {weight}")

Output

Edges in MST:

A - B: 1

B - C: 1

C - E: 2

C - D: 4

Total Weight of MST: 8

20
21