19CS303 – Fundamentals of Data Structures using Python

ANSWER KEY

PART B

*QB101 (a) (i) Develop a python program to get the details from the user such as student name, age,
address and CGPA and display them.
7 Marks

Ans :

# Get student details from the user

name = input("Enter student name: ")

age = int(input("Enter student age: "))

address = input("Enter student address: ")

cgpa = float(input("Enter student CGPA: "))

# Display the collected details

print("\nStudent Details:")

print(f"Name: {name}")

print(f"Age: {age}")

print(f"Address: {address}")

print(f"CGPA: {cgpa:.2f}")

(ii) Build a python program to get the principal, rate and time from the user and find the
simple interest for it.
6 Marks

Ans:

# Get the principal, rate, and time from the user

principal = float(input("Enter the principal amount: "))

rate = float(input("Enter the rate of interest (as a percentage): "))

time = float(input("Enter the time period (in years): "))

# Calculate the simple interest

1
 simple_interest = (principal * rate * time) / 100

# Display the simple interest

print(f"Simple Interest: {simple_interest:.2f}")

QB101 (b) (i) Write a python program to read two integers and perform simple arithmetic
calculation.(+,-,*,/,//,%,**)
7 Marks

Ans:

def arithmetic_operations(a, b):

"""Perform arithmetic operations on two integers."""

operations = {

"Addition": a + b,

"Subtraction": a - b,

"Multiplication": a * b,

"Division": a / b if b != 0 else "Undefined (division by zero)",

"Floor Division": a // b if b != 0 else "Undefined (division by zero)",

"Modulus": a % b if b != 0 else "Undefined (division by zero)",

"Exponentiation": a ** b

return operations

# Input from the user

num1 = int(input("Enter the first integer: "))

num2 = int(input("Enter the second integer: "))

# Perform arithmetic operations

results = arithmetic_operations(num1, num2)

# Display the results

for operation, result in [Link]():

print(f"{operation}: {result}")

(ii) Write a python program to find maximum between three integer numbers using
conditional Expression(Ternary)

6 Marks
Ans:

2
 # Function to find the maximum of three numbers using ternary operator
def max_of_three(a, b, c):
return a if (a > b and a > c) else (b if b > c else c)
a = int(input("Enter first number: "))
b = int(input("Enter second number: "))
c = int(input("Enter third number: "))
print(f"The maximum number is: {max_of_three(a, b, c)}")

QB102 (a) (i) Write a python program to display the sum of all even numbers in the given range.
6 Marks

start = int(input())
end = int(input())
sum=0
for num in range(start, end + 1):
if num % 2 == 0:
sum=sum+num
print("Sum is :",sum)

(ii) Write a program to print the given pattern.

*
**
***
****
7 Marks
Ans:
n = int(input()
# Enter the number of rows:
for i in range(1, n + 1):
for j in range(1,i+1):
print("* ",end=”)
print()
QB102 (b) (i) Write a Python program to check whether a number is a palindrome or not using
functions.
7 Marks

Ans:

def is_palindrome(number):

"""Function to check if a number is a palindrome."""

# Convert the number to a string

num_str = str(number)

# Reverse the string

reversed_str = num_str[::-1]

# Check if the original string is equal to the reversed string

return num_str == reversed_str

# Prompt the user for input

input_number = int(input("Enter a number to check if it is a palindrome: "))

3
 # Check if the number is a palindrome

if is_palindrome(input_number):

print(f"{input_number} is a palindrome.")

else:

print(f"{input_number} is not a palindrome.")

(ii) Write a program to gather individual's details such as name, age, and monthly income,
and determine if the person is eligible for a housing loan. Eligibility criteria: age between 25
to 50 years and monthly income more than 30000. 6
Marks

Ans:

# Gather individual's details

name = input("Enter your name: ")

age = int(input("Enter your age: "))

monthly_income = float(input("Enter your monthly income: "))

# Define eligibility criteria

min_age = 25

max_age = 50

min_income = 30000

# Check eligibility for housing loan

if min_age <= age <= max_age and monthly_income > min_income:

print(f"{name}, you are eligible for a housing loan.")

else:

print(f"{name}, you are not eligible for a housing loan.")

QB104 (a)
Create a Python program to perform basic geometric calculations using the following user-
defined functions:
calculate_circle_area(radius) to compute the area of a circle.
calculate_rectangle_area(length, width) to compute the area of a rectangle.
calculate_triangle_area(base, height) to compute the area of a triangle.
calculate_square_area(side) to compute the area of a square.
15 Marks

Ans:

import math
4
def calculate_circle_area(radius):

"""Compute the area of a circle given its radius."""

return [Link] * (radius ** 2)

def calculate_rectangle_area(length, width):

"""Compute the area of a rectangle given its length and width."""

return length * width

def calculate_triangle_area(base, height):

"""Compute the area of a triangle given its base and height."""

return 0.5 * base * height

def calculate_square_area(side):

"""Compute the area of a square given its side length."""

return side ** 2

# Circle

radius = float(input("Enter the radius of the circle: "))

circle_area = calculate_circle_area(radius)

print(f"Area of the circle: {circle_area:.2f}")

# Rectangle

length = float(input("Enter the length of the rectangle: "))

width = float(input("Enter the width of the rectangle: "))

rectangle_area = calculate_rectangle_area(length, width)

print(f"Area of the rectangle: {rectangle_area:.2f}")

# Triangle

base = float(input("Enter the base of the triangle: "))

5
 height = float(input("Enter the height of the triangle: "))

triangle_area = calculate_triangle_area(base, height)

print(f"Area of the triangle: {triangle_area:.2f}")

# Square

side = float(input("Enter the side length of the square: "))

square_area = calculate_square_area(side)
print(f"Area of the square: {square_area:.2f}")
*QB104 (b) (i)To write a Python Program to check if a number is a Perfect number using the concept of
functions.
7 Marks

Ans:
def perfectnumber(n):
factor_sum=0
for i in range(1,n//2+1):
if(n%i==0):
factor_sum+=i
if(n==factor_sum):
print("The number is a Perfect number!")
else:
print("The number is not a Perfect number!")
num=int(input())
perfectnumber(num)

ii) Write a program in Python to find the sum of series (1+(1*2)+(1*2*3)+...till N). 8
Marks

Ans:
n=int(input())
sum_series=0
i=1
while(i<=n):
multiply=1
for j in range(1,i+1):
multiply*=j
sum_series+=multiply
i+=1
print("The sum of the series = ",sum_series)
QB201 (a) What is Set? Explain Python Set in detail with its operations and methods.

Ans

Set is one of 4 built-in data types in Python used to store collections of data, the other 3 are
List, Tuple, and Dictionary, all with different qualities and usage. A set is a collection which
is unordered, unchangeable*, and unindexed. * Note: Set items are unchangeable, but you
can remove items and add new items.

6
Python Sets – Operations and Examples

A set is a mutable, unordered group of elements, where the elements themselves are
[Link] characteristic of a set is that it may include elements of different types.
This means you can have a group of numbers, strings, and even tuples, all in the same set!

How to Create a Set

The most common way of creating a set in Python is by using the built-in set() function.

>>> first_set = set(("Connor", 32, (1, 2, 3)))

>>> first_set
{32, 'Connor', (1, 2, 3)}
>>>
>>> second_set = set("Connor")
>>> second_set
{'n', 'C', 'r', 'o'}

You can also create sets using the curly brace {} syntax:

>>> third_set = {"Apples", ("Bananas", "Oranges")}

>>> type(third_set)
<class 'set'>

The set() function takes in an iterable and yields a list of objects which will be inserted into
the set. The {} syntax places the objects themselves into the set.

>>> incorrect_set = {"Apples", ["Bananas", "Oranges"]}

Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

How to Add or Remove Elements in a Set

We already know that sets are mutable. This means you can add/remove elements in a set.

Here's an example of adding elements to a set using the update() function.

>>> add_set = set((1, 2, 3, 4))

>>> add_set
{1, 2, 3, 4}
>>>
>>> add_set.update((1,))
>>> add_set
{1, 2, 3, 4}
>>> add_set.update(("cello", "violin"))
>>> add_set
{1, 2, 3, 4, 'violin', 'cello'}
But notice how nothing changes when we try to add "cello" to the set again:

>>> add_set.update(("cello",))
>>> add_Set
{1, 2, 3, 4, 'violin', 'cello'}

7
 This is because sets in Python cannot contain duplicates. So, when we tried to add "cello"
again to the set, Python recognized we were trying to add a duplicate element and didn't
update the set. This is one caveat that differentiates sets from lists.

Here's how you would remove elements from a set:

>>> sub_set = add_set

>>> sub_set.remove("violin")
>>> sub_set
{1, 2, 3, 4, 'cello'}

The remove(x) function removes the element x from a set. It returns a KeyError if x is not
part of the set:

>>> sub_set.remove("guitar")
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
KeyError: 'guitar'
There are a couple of other ways to remove an element(s) from a set:

the discard(x) method removes x from the set, but doesn't raise any error if x is not present in
the set.
the pop() method removes and returns a random element from the set.
the clear() method removes all elements from a set

Here are some examples to illustrate:

>>> m_set = set((1, 2, 3, 4))

>>>
>>> m_set.discard(5) # no error raised even though '5' is not present in the set
>>>
>>> m_set.pop()
4
>>> m_set
{1, 2, 3}
>>>
>>> m_set.clear()
>>> m_set
set()
(b)
i) Write a python program to add two matrices using nested lists.

7
marks

Ans:
QB201 def add_matrices(matrix1, matrix2):

"""Add two matrices using nested lists."""

return [[matrix1[i][j] + matrix2[i][j] for j in range(len(matrix1[0]))] for i in

range(len(matrix1))]

# Example matrices

8
 matrix1 = [

[1, 2, 3],

[4, 5, 6],

[7, 8, 9]

matrix2 = [

[9, 8, 7],

[6, 5, 4],

[3, 2, 1]

# Add the two matrices

result_matrix = add_matrices(matrix1, matrix2)

# Print the result

print("Resultant Matrix:")

for row in result_matrix:

print(row)

ii) Write a python program to create a list of numbers in the range 1 to 10. Then delete all
the even numbers from the list and print the list with odd numbers.

6 marks

Ans:

# Create a list of numbers from 1 to 10

numbers = list(range(1, 11))

# Remove even numbers from the list

odd_numbers = [num for num in numbers if num % 2 != 0]

# Print the list with odd numbers

print("List of odd numbers:", odd_numbers)

QB202 (a) Explain classes and objects in Python with an example? Also explain self-keyword
associated the classes.

Class

9
 A class in Python is a blueprint for creating objects. It defines attributes (variables) and
methods (functions) that the created objects will have.
Think of a class like a template for a car – it defines the structure, but not the actual car.
Each car built from that blueprint is an object.

Object
An object is an instance of a class. It is a real-world entity with specific values assigned to
its attributes.

The self Keyword

• self is a reference to the current instance of the class.
• It's used to access instance variables and methods within the class.
• It must be the first parameter of instance methods.

Example:
class Employee:
def __init__(self, name, emp_id):
[Link] = name # '[Link]' is instance variable
self.emp_id = emp_id # 'self.emp_id' is also instance variable

def display_info(self):
print(f"Employee Name: {[Link]}")
print(f"Employee ID : {self.emp_id}")

# Creating objects (instances of the class)

emp1 = Employee("Alice", "EMP001")
emp2 = Employee("Bob", "EMP002")

# Accessing methods and attributes

emp1.display_info()
emp2.display_info()

Output:
Employee Name: Alice
Employee ID : EMP001
Employee Name: Bob
Employee ID : EMP002

(b) Write a python code to implement a class Dress with the parameterised constructor ,that
accepts the cloth,cloth-type and quantity , and print the details.

# Define the Dress class

class Dress:
def __init__(self, cloth, cloth_type, quantity):
[Link] = cloth
self.cloth_type = cloth_type
*QB202 [Link] = quantity

def display_details(self):
print("Dress Details")
print(f"Cloth : {[Link]}")
print(f"Cloth Type : {self.cloth_type}")
print(f"Quantity : {[Link]}")

# Main function to get input and create object

10
 def main():
cloth = input("Enter cloth material: ")
cloth_type = input("Enter cloth type: ")
quantity = input("Enter quantity: ")

# Create Dress object

dress = Dress(cloth, cloth_type, quantity)

# Display details
dress.display_details()

# Run the program

main()

OUTPUT:
Enter cloth material: Cotton
Enter cloth type: Shirt
Enter quantity: 5
Dress Details
Cloth : Cotton
Cloth Type : Shirt
Quantity : 5
(a)
i) Write a python program to replace last value of tuples in a list.

Sample input:[(10,20,40),(40,50,60),(70,80,90)]

Sample output:[(10,20,100),(40,50,100),(70,80,100)]
7 Marks

Ans:

def replace_last_value(tuples_list, new_value):

"""Replace the last value of each tuple in the list with the specified new value."""

# Create a new list with modified tuples

modified_list = [t[:-1] + (new_value,) for t in tuples_list]

*QB204
return modified_list

# Sample input

tuples_list = [(10, 20, 40), (40, 50, 60), (70, 80, 90)]

# Replace the last value in each tuple with 100

new_value = 100

result = replace_last_value(tuples_list, new_value)

# Print the result

print("Modified list of tuples:", result)

11
 ii) Write a python program to return only negative values from the tuples of positive and
negative numbers.
6 Marks

Ans:

def extract_negative_values(tuples_list):

"""Extract and return only the negative values from a list of tuples."""

# Create a new list of tuples containing only negative values

negative_values = [tuple(num for num in t if num < 0) for t in tuples_list]

return negative_values

# Sample input: list of tuples with positive and negative numbers

tuples_list = [(10, -20, 30), (-40, 50, -60), (70, -80, 90), (-10, -30, 40)]

# Extract negative values

result = extract_negative_values(tuples_list)

# Print the result

print("Tuples with only negative values:", result)

(b) Explain the basic List Operations and list slices in details with necessary programs.

Ans:
Basic List Operations

1. Creating a List

You can create a list using square brackets `[]` with comma-separated elements.

# Creating a list
fruits = ['apple', 'banana', 'cherry']
print(fruits)

QB204 2. Accessing and Modifying Elements

Lists use zero-based indexing to access and modify elements.

# Accessing elements
print(fruits[0]) # 'apple'
print(fruits[-1]) # 'cherry'

# Modifying elements
fruits[1] = 'blueberry'
print(fruits) # ['apple', 'blueberry', 'cherry']

3. Adding Elements

12
-append(): Adds an element to the end.
- insert(): Inserts an element at a specified position.
- extend(): Adds elements from another list.

[Link]('date')
[Link](1, 'fig')
[Link](['grape', 'honeydew'])
print(fruits) # ['apple', 'fig', 'blueberry', 'cherry', 'date', 'grape', 'honeydew']

4. Removing Elements

- remove(): Removes the first occurrence of a value.

- pop(): Removes and returns an element at a specified index.
- del: Deletes an element or slice.
- clear(): Removes all elements.

[Link]('fig')
popped = [Link](2)
del fruits[0]
[Link]()
print(fruits) # []

5. List Membership

Check if an element is in the list using `in` and `not in`.

fruits = ['apple', 'banana', 'cherry']

print('apple' in fruits) # True
print('fig' not in fruits) # True

6. List Concatenation and Repetition

- Concatenation: Combines lists using `+`.

- Repetition: Repeats elements using `*`.

list1 = [1, 2, 3]
list2 = [4, 5, 6]
combined = list1 + list2
repeated = list1 * 2
print(combined) # [1, 2, 3, 4, 5, 6]
print(repeated) # [1, 2, 3, 1, 2, 3]

List Slicing

Slicing allows you to create a new list by extracting a portion of an existing list using the
syntax `list[start:end:step]`.

Examples

numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# Slice from index 2 to 5

print(numbers[2:6]) # [2, 3, 4, 5]

# Slice with a step

13
 print(numbers[1:8:2]) # [1, 3, 5, 7]

# Slice from the beginning to a position

print(numbers[:4]) # [0, 1, 2, 3]

# Slice from a position to the end

print(numbers[5:]) # [5, 6, 7, 8, 9]

# Reverse a list
print(numbers[::-1]) # [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

These operations and slicing techniques are fundamental to working with lists in Python,
enabling you to effectively manage and manipulate collections of data.
(a) Create a Python program to implement stack using List and its built-in methods (append()
and pop() ) in Python. Get five items from the user and save them in stack, then pop three
items from stack and display the stack before and after popped.

Ans

stack=[]
[Link]("One")
[Link]("Two")
[Link]("Three")
QB301
[Link]("Four")
[Link]("Five")
print("Stack - Before Popping")
print(stack)
[Link]()
[Link]()
[Link]()
print("Stack - After Popping")
print(stack)

(b) What is Stack ADT? Explain the operations performed in a stack with examples

Ans

A stack is an ADT in which elements add added and removed from only one end (i.e.,at the
top of the stack). • A stack is a LIFO “last in, first out” structure

• push(n)– This is a user-defined stack method used for inserting an element into the stack. ...
• pop()– We need this method to remove the topmost element from the stack.
isempty()– We need this method to check whether the stack is empty or not.
QB301
Program:
stack = []

# push operations
[Link](10)
[Link](20)
[Link](30)

print("Stack:", stack) # [10, 20, 30]

14
 # pop operation
top_element = [Link]()
print("Popped:", top_element) # 30
print("Stack after pop:", stack) # [10, 20]

# peek operation
print("Top element (peek):", stack[-1]) # 20

# check if empty
print("Is stack empty?", len(stack) == 0) # False

# size
print("Stack size:", len(stack)) # 2
(a) Build a Python program to convert given Infix expression to Postfix expression by
following the precedence and associative rule.

The input expression contains only ^ and * . Use dictionary to set the priority for operators.
Use set to hold the operators used in the given expression. Also in the same program
incorporate evaluation for the operands given in an expression

Ans

Operators = set(['+', '-', '*', '/', '(', ')', '^']) # collection of Operators
Priority = {'+':1, '-':1, '*':2, '/':2, '^':3} # dictionary having priorities of Operators

def infixToPostfix(expression):

stack = [] # initialization of empty stack

output = ''

for character in expression:

if character not in Operators: # if an operand append in postfix expression
QB302
output+= character
elif character=='(': # else Operators push onto stack
[Link]('(')
elif character==')':
while stack and stack[-1]!= '(':
output+=[Link]()
[Link]()
else:
while stack and stack[-1]!='(' and Priority[character]<=Priority[stack[-1]]:
output+=[Link]()
[Link](character)

while stack:
output+=[Link]()

return output

expression = input('Enter infix expression ')

print('infix notation: ',expression)
print('postfix notation: ',infixToPostfix(expression))
15
 (b) Write a Python Program to implement Priority Queue.
Ans

The priority queue allows efficient management of tasks based on their priorities, ensuring
that higher priority tasks are executed first. This application can be found in operating
systems, real-time systems, and job schedulers. Huffman coding is a popular data
compression algorithm used to compress data efficiently

# A simple implementation of Priority Queue

# using Queue.
class PriorityQueue(object):
def __init__(self):
[Link] = []

def __str__(self):
return ' '.join([str(i) for i in [Link]])

# for checking if the queue is empty

def isEmpty(self):
return len([Link]) == 0

# for inserting an element in the queue

def insert(self, data):
[Link](data)
*QB302
# for popping an element based on Priority
def delete(self):
try:
max_val = 0
for i in range(len([Link])):
if [Link][i] > [Link][max_val]:
max_val = i
item = [Link][max_val]
del [Link][max_val]
return item
except IndexError:
print()
exit()

if __name__ == '__main__':
myQueue = PriorityQueue()
[Link](12)
[Link](1)
[Link](14)
[Link](7)
print(myQueue)
while not [Link]():
print([Link]())

QB303

QB304 (a) Discuss in detail about the Linked List and its Variations with neat examples.

16
Ans

A linked list is a linear data structure, in which the elements are not stored at contiguous
memory locations. The elements in a linked list are linked using pointers. In simple words,
a linked list consists of nodes where each node contains a data field and a reference(link) to
the next node in the list.
Types Of Linked List:

1. Singly Linked List

The node contains a pointer to the next node means that the node stores the address of the
next node in the sequence. A single linked list allows the traversal of data only in one way.
Below is the image for the same:

2. Doubly Linked List

A doubly linked list or a two-way linked list is a more complex type of linked list that
contains a pointer to the next as well as the previous node in sequence.

Therefore, it contains three parts of data, a pointer to the next node, and a pointer to the
previous node. This would enable us to traverse the list in the backward direction as well.
Below is the image for the same:

3. Circular Linked List

A circular linked list is that in which the last node contains the pointer to the first node of
the list.
While traversing a circular linked list, we can begin at any node and traverse the list in any
direction forward and backward until we reach the same node we started. Thus, a circular
linked list has no beginning and no end. Below is the image for the same:

17
 (b) Write a Python Program to Insert Strings into a Circular Queue.

class CircularQueue:
def __init__(self, size):
[Link] = size
[Link] = [None] * size # Fixed-size list
[Link] = -1
[Link] = -1

def enqueue(self, value):

# Check if queue is full
if (([Link] + 1) % [Link] == [Link]):
print("Queue is full! Cannot insert:", value)
elif [Link] == -1: # First element
[Link] = 0
[Link] = 0
[Link][[Link]] = value
else:
[Link] = ([Link] + 1) % [Link]
[Link][[Link]] = value

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

print("Circular Queue contents:")

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

# Main function
def main():
n = int(input("Enter size of Circular Queue: "))
cq = CircularQueue(n)

print("Enter string values to insert into the queue:")

for _ in range(n):
val = input("Enter value: ")
[Link](val)
18
 [Link]()

# Run the program

main()

Output:

Enter size of Circular Queue: 3

Enter string values to insert into the queue:
Enter value: apple
Enter value: banana
Enter value: cherry
Circular Queue contents:
apple banana cherry

(a) Create a Python function def heaptree(L): to build a tree and find out whether the tree is
max heap and a complete tree, also print the height of the tree. Use appropriate module to
build a binary tree.

Python Code

from binarytree import build

import math

def is_max_heap_tree(node):
if node is None:
return True

# Check max-heap condition

left = [Link]
right = [Link]

if left and [Link] < [Link]:

return False
*QB401 if right and [Link] < [Link]:
return False

return is_max_heap_tree(left) and is_max_heap_tree(right)

def is_complete_tree_bt(root):
if root is None:
return True

queue = [root]
end = False

while queue:
current = [Link](0)

if [Link]:
if end:
return False
[Link]([Link])
else:
19
 end = True

if [Link]:
if end:
return False
[Link]([Link])
else:
end = True

return True

def tree_height_bt(root):
return [Link] if root else 0

def heaptree(L):
print("Building Binary Tree from list:", L)
tree = build(L)
print("\nConstructed Binary Tree:")
print(tree)

is_max = is_max_heap_tree(tree)
is_complete = is_complete_tree_bt(tree)
height = tree_height_bt(tree)

print("Is Max Heap :", "Yes" if is_max else "No")

print("Is Complete Tree :", "Yes" if is_complete else "No")
print("Height of Tree :", height)

Example Usage:
heaptree([100, 90, 80, 70, 60, 50])

Output:
Building Binary Tree from list: [100, 90, 80, 70, 60, 50]

Constructed Binary Tree:

___100
/ \
90 80
/ \ /
70 60 50

Is Max Heap : Yes

Is Complete Tree : Yes
Height of Tree : 2

(b) Write a python code to traverse binary Tree in inorder, preorder and postorder .

In Order Code
QB401
class TreeNode:
def __init__(self, val):
20
 [Link] = val
[Link] = None
[Link] = None

def inorderTraversal(root):
answer = []

inorderTraversalUtil(root, answer)
return answer

def inorderTraversalUtil(root, answer):

if root is None:
return

inorderTraversalUtil([Link], answer)
[Link]([Link])
inorderTraversalUtil([Link], answer)
return

root = TreeNode(1)
[Link] = TreeNode(2)
[Link] = TreeNode(3)
[Link] = TreeNode(4)
[Link] = TreeNode(5)
print(inorderTraversal(root))

Preorder Code

class TreeNode:

def __init__(self,val):
[Link] = val
[Link] = None
[Link] = None

def preorderTraversal(root):
answer = []

preorderTraversalUtil(root, answer)
return answer

def preorderTraversalUtil(root, answer):

if root is None:
return

[Link]([Link])

preorderTraversalUtil([Link], answer)

preorderTraversalUtil([Link], answer)

return

21
 root = TreeNode(1)
[Link] = TreeNode(2)
[Link] = TreeNode(3)
[Link] = TreeNode(4)
[Link] = TreeNode(5)

print(preorderTraversal(root))

Postorder Code

class TreeNode:

def __init__(self, val):

[Link] = val
[Link] = None
[Link] = None

def postorderTraversal(root):
answer = []

postorderTraversalUtil(root, answer)
return answer

def postorderTraversalUtil(root, answer):

if root is None:
return

postorderTraversalUtil([Link], answer)

postorderTraversalUtil([Link], answer)

[Link]([Link])

return

root = TreeNode(1)
[Link] = TreeNode(2)
[Link] = TreeNode(3)
[Link] = TreeNode(4)
[Link] = TreeNode(5)
print(postorderTraversal(root))

(a) Explain in detail about the creation of binary search tree with example.

Ans

QB402
A binary search tree follows some order to arrange the elements. In a Binary search tree, the
value of left node must be smaller than the parent node, and the value of right node must be
greater than the parent node. This rule is applied recursively to the left and right subtrees of
the root.

22
Let's understand the concept of Binary search tree with an example.

In the above figure, we can observe that the root node is 40, and all the nodes of the left
subtree are smaller than the root node, and all the nodes of the right subtree are greater than
the root node.

Similarly, we can see the left child of root node is greater than its left child and smaller than
its right child. So, it also satisfies the property of binary search tree. Therefore, we can say
that the tree in the above image is a binary search tree.

Suppose if we change the value of node 35 to 55 in the above tree, check whether the tree
will be binary search tree or not.

In the above tree, the value of root node is 40, which is greater than its left child 30 but smaller
than right child of 30, i.e., 55. So, the above tree does not satisfy the property of Binary search
tree. Therefore, the above tree is not a binary search tree.

Advantages of Binary search tree

o Searching an element in the Binary search tree is easy as we always have a hint that
which subtree has the desired element.
o As compared to array and linked lists, insertion and deletion operations are faster in
BST.

Example of creating a binary search tree

Now, let's see the creation of binary search tree using an example.

23
Suppose the data elements are - 45, 15, 79, 90, 10, 55, 12, 20, 50

o First, we have to insert 45 into the tree as the root of the tree.
o Then, read the next element; if it is smaller than the root node, insert it as the root of
the left subtree, and move to the next element.
o Otherwise, if the element is larger than the root node, then insert it as the root of the
right subtree.

Now, let's see the process of creating the Binary search tree using the given data element. The
process of creating the BST is shown below -

Step 1 - Insert 45.

Step 2 - Insert 15.

As 15 is smaller than 45, so insert it as the root node of the left subtree.

Step 3 - Insert 79.

As 79 is greater than 45, so insert it as the root node of the right subtree.

Step 4 - Insert 90.

90 is greater than 45 and 79, so it will be inserted as the right subtree of 79.

24
Step 5 - Insert 10.

10 is smaller than 45 and 15, so it will be inserted as a left subtree of 15.

Step 6 - Insert 55.

55 is larger than 45 and smaller than 79, so it will be inserted as the left subtree of 79.

Step 7 - Insert 12.

12 is smaller than 45 and 15 but greater than 10, so it will be inserted as the right subtree of
10.

25
Step 8 - Insert 20.

20 is smaller than 45 but greater than 15, so it will be inserted as the right subtree of 15.

Step 9 - Insert 50.

50 is greater than 45 but smaller than 79 and 55. So, it will be inserted as a left subtree of 55.

26
Now, the creation of binary search tree is completed. After that, let's move towards the
operations that can be performed on Binary search tree.

We can perform insert, delete and search operations on the binary search tree.

Let's understand how a search is performed on a binary search tree.

Searching in Binary search tree

Searching means to find or locate a specific element or node in a data structure. In Binary
search tree, searching a node is easy because elements in BST are stored in a specific order.
The steps of searching a node in Binary Search tree are listed as follows -

1. First, compare the element to be searched with the root element of the tree.
2. If root is matched with the target element, then return the node's location.
3. If it is not matched, then check whether the item is less than the root element, if it is
smaller than the root element, then move to the left subtree.
4. If it is larger than the root element, then move to the right subtree.
5. Repeat the above procedure recursively until the match is found.
6. If the element is not found or not present in the tree, then return NULL.

Now, let's understand the searching in binary tree using an example. We are taking the binary
search tree formed above. Suppose we have to find node 20 from the below tree.

Step1:

Step2:

27
 Step3:

Now, let's see the algorithm to search an element in the Binary search tree.

Algorithm to search an element in Binary search tree

1. Search (root, item)

2. Step 1 - if (item = root → data) or (root = NULL)
3. return root
4. else if (item < root → data)
5. return Search(root → left, item)
6. else
7. return Search(root → right, item)
8. END if
9. Step 2 - END

Now let's understand how the deletion is performed on a binary search tree. We will also see
an example to delete an element from the given tree.

Deletion in Binary Search tree

28
In a binary search tree, we must delete a node from the tree by keeping in mind that the
property of BST is not violated. To delete a node from BST, there are three possible situations
occur -

o The node to be deleted is the leaf node, or,

o The node to be deleted has only one child, and,
o The node to be deleted has two children

We will understand the situations listed above in detail.

When the node to be deleted is the leaf node

It is the simplest case to delete a node in BST. Here, we have to replace the leaf node with
NULL and simply free the allocated space.

We can see the process to delete a leaf node from BST in the below image. In below image,
suppose we have to delete node 90, as the node to be deleted is a leaf node, so it will be
replaced with NULL, and the allocated space will free.

When the node to be deleted has only one child

In this case, we have to replace the target node with its child, and then delete the child node.
It means that after replacing the target node with its child node, the child node will now
contain the value to be deleted. So, we simply have to replace the child node with NULL and
free up the allocated space.

We can see the process of deleting a node with one child from BST in the below image. In
the below image, suppose we have to delete the node 79, as the node to be deleted has only
one child, so it will be replaced with its child 55.

So, the replaced node 79 will now be a leaf node that can be easily deleted.

29
When the node to be deleted has two children

This case of deleting a node in BST is a bit complex among other two cases. In such a case,
the steps to be followed are listed as follows -

o First, find the inorder successor of the node to be deleted.

o After that, replace that node with the inorder successor until the target node is placed
at the leaf of tree.
o And at last, replace the node with NULL and free up the allocated space.

The inorder successor is required when the right child of the node is not empty. We can obtain
the inorder successor by finding the minimum element in the right child of the node.

We can see the process of deleting a node with two children from BST in the below image.
In the below image, suppose we have to delete node 45 that is the root node, as the node to
be deleted has two children, so it will be replaced with its inorder successor. Now, node 45
will be at the leaf of the tree so that it can be deleted easily.

Now let's understand how insertion is performed on a binary search tree.

Insertion in Binary Search tree

A new key in BST is always inserted at the leaf. To insert an element in BST, we have to start
searching from the root node; if the node to be inserted is less than the root node, then search
for an empty location in the left subtree. Else, search for the empty location in the right subtree
and insert the data. Insert in BST is similar to searching, as we always have to maintain the
rule that the left subtree is smaller than the root, and right subtree is larger than the root.

Now, let's see the process of inserting a node into BST using an example.

30
 (b) Construct a Python function to build a Binary tree.

1. Use appropriate Package and build module to build a tree

2. Define def buildtree(L): to build a binary tree

3. Print the leaves and leaf count and sum of the leaves of the binary tree.

Ans

class Node:
cnt=0
sum=0

def __init__(self, data):

[Link] = None
QB402
[Link] = None
[Link] = data
# Insert Node
def buildtree(self, data):
if [Link]:
if data < [Link]:
if [Link] is None:
[Link] = Node(data)
else:
[Link](data)
elif data > [Link]:
if [Link] is None:
[Link] = Node(data)
else:
[Link](data)
else:
31
 [Link] = data
# Print the Tree

def PrintTree(self, root):

res = []
if root:
if [Link] is None and [Link] is None:
print([Link])
[Link]=[Link]+1
[Link]=[Link]+[Link]
[Link]([Link])
res = res + [Link]([Link])
res = res + [Link]([Link])
return res
root = Node(27)
[Link](14)
[Link](35)
[Link](10)
[Link](19)
[Link](31)
[Link](42)
[Link](root)
print("No. of Leaf Nodes : ",[Link])
print("Sum of Leaf Nodes : ",[Link])
(a) Explain in detail about Red-Black tree with an example.

A Red-Black Tree is a type of self-balancing binary search tree (BST). It ensures that the
tree remains approximately balanced during insertions and deletions, maintaining O(log n)
time complexity for search, insertion, and deletion.

Key Properties of a Red-Black Tree:

1. Node Color: Every node is either Red or Black.
2. Root Property: The root is always Black.
3. Leaf Property: All leaves (NIL or null pointers) are considered Black.
4. Red Property: If a node is Red, its children must be Black (no two Reds in a row).
5. Black-Height Property: From any node, every path to its descendant NIL nodes has
the same number of Black nodes.
These rules ensure that the longest path is no more than twice as long as the shortest path,
keeping the tree balanced.
*QB404
Example
Let’s insert these values into a Red-Black Tree:
10, 20, 30, 15, 25, 5
Step-by-step Insertions:
1. Insert 10
o It's the root → color it Black.
2. Insert 20
o 20 > 10 → goes to the right.
o Parent (10) is Black → OK.
o 20 is colored Red.
3. Insert 30
o 30 > 20 → right of 20.
o Parent is Red → Violation!
o Uncle is NIL (Black) → Recoloring and Rotation.

32
 o Left rotation on 10, recolor → 20 becomes new root.
4. Insert 15
o Goes to the left of 20, then left of 20.
o Recoloring or rotation may happen depending on tree shape and uncle's
color.
5. Insert 25
o Inserted as Red; check for parent/uncle color → rebalance as needed.
6. Insert 5
o Inserted as Red; no violations.

Final Tree Shape (Conceptual)

20 (Black)
/ \
10(R) 30(R)
/ \ /
5(B) 15(B) 25(B)

Python Code (Basic Structure)

class Node:
def __init__(self, data, color='R'):
[Link] = data
[Link] = color # 'R' for Red, 'B' for Black
[Link] = None
[Link] = None
[Link] = None

class RedBlackTree:
def __init__(self):
[Link] = Node(None, 'B')
[Link] = [Link]

def insert(self, data):

# Implement standard BST insert, then fix the tree using rotations and recoloring
pass

def rotate_left(self, node):

# Left rotate around node
pass

def rotate_right(self, node):

# Right rotate around node
pass

def fix_insert(self, node):

# Fix violations after insert
pass

(b) Explain in detail about Splay tree with an example.

A Splay Tree is a self-adjusting binary search tree. After every access operation (insert,
*QB404
delete, or search), the accessed node is "splayed" to the root using tree rotations. This makes
frequently accessed elements quicker to reach.

33
The most recently accessed node is moved to the root through a process called splaying,
improving access time for future operations involving that node.

Advantages:
• No explicit balancing required.
• Frequently accessed nodes are quicker to reach.
• All standard BST operations (search, insert, delete) are O(log n) amortized time.

Splaying Operations (Rotation Patterns)

Let’s say x is the node we want to splay.
1. Zig (single rotation)
o x is a child of the root.
o Use a single rotation (left or right).
2. Zig-Zig (double rotation)
o x and its parent are both left or both right children.
o Rotate parent up, then x up again.
3. Zig-Zag (double rotation)
o x is a left child and its parent is a right child, or vice versa.
o Rotate x up twice in opposite directions.

Example: Insert Sequence 10, 20, 30

Let’s insert these into a Splay Tree:
Step 1: Insert 10
• Tree: 10 (no splaying needed)
Step 2: Insert 20
• Tree:

10
\
20
•Splay 20 to root (Zig rotation):
CopyEdit
20
/
10

#### Step 3: Insert 30

- Inserted as right child of 20:
20
/
10 30

- Splay 30 to root:
- Zig-Zig (20 and 30 are both right children)
- Rotate 20 up, then 30 up:

30
/
20
/
10

Now 30 is at the root — recently used nodes bubble to the top!

34
```python
class Node:
def __init__(self, key):
[Link] = key
[Link] = None
[Link] = None
[Link] = None

class SplayTree:
def __init__(self):
[Link] = None

def right_rotate(self, x):

y = [Link]
[Link] = [Link]
if [Link]:
[Link] = x
[Link] = [Link]
if not [Link]:
[Link] = y
elif x == [Link]:
[Link] = y
else:
[Link] = y
[Link] = x
[Link] = y

def left_rotate(self, x):

y = [Link]
[Link] = [Link]
if [Link]:
[Link] = x
[Link] = [Link]
if not [Link]:
[Link] = y
elif x == [Link]:
[Link] = y
else:
[Link] = y
[Link] = x
[Link] = y

def splay(self, x):

while [Link]:
if not [Link]:
if x == [Link]:
self.right_rotate([Link])
else:
self.left_rotate([Link])
elif x == [Link] and [Link] == [Link]:
self.right_rotate([Link])
self.right_rotate([Link])
elif x == [Link] and [Link] == [Link]:
self.left_rotate([Link])
self.left_rotate([Link])
35
 elif x == [Link] and [Link] == [Link]:
self.left_rotate([Link])
self.right_rotate([Link])
else:
self.right_rotate([Link])
self.left_rotate([Link])

(a) Describe in detail about Quick sort with example

Ans

Quick Sort Algorithm

Sorting is a way of arranging items in a systematic manner. Quicksort is the widely used
sorting algorithm that makes n log n comparisons in average case for sorting an array of n
elements. It is a faster and highly efficient sorting algorithm. This algorithm follows the divide
and conquer approach. Divide and conquer is a technique of breaking down the algorithms
into subproblems, then solving the subproblems, and combining the results back together to
solve the original problem.

Divide: In Divide, first pick a pivot element. After that, partition or rearrange the array into
two sub-arrays such that each element in the left sub-array is less than or equal to the pivot
element and each element in the right sub-array is larger than the pivot element.

Conquer: Recursively, sort two subarrays with Quicksort.

Combine: Combine the already sorted array.

Quicksort picks an element as pivot, and then it partitions the given array around the picked
pivot element. In quick sort, a large array is divided into two arrays in which one holds values
QB501
that are smaller than the specified value (Pivot), and another array holds the values that are
greater than the pivot.

After that, left and right sub-arrays are also partitioned using the same approach. It will
continue until the single element remains in the sub-array.

Choosing the pivot

Picking a good pivot is necessary for the fast implementation of quicksort. However, it is
typical to determine a good pivot. Some of the ways of choosing a pivot are as follows -

o Pivot can be random, i.e. select the random pivot from the given array.
o Pivot can either be the rightmost element of the leftmost element of the given array.
36
 o Select median as the pivot element.

Algorithm

Algorithm:

1. QUICKSORT (array A, start, end)

2. {
3. 1 if (start < end)
4. 2{
5. 3 p = partition(A, start, end)
6. 4 QUICKSORT (A, start, p - 1)
7. 5 QUICKSORT (A, p + 1, end)
8. 6 }
9. }

Partition Algorithm:

The partition algorithm rearranges the sub-arrays in a place.

1. PARTITION (array A, start, end)

2. {
3. 1 pivot ? A[end]
4. 2 i ? start-1
5. 3 for j ? start to end -1 {
6. 4 do if (A[j] < pivot) {
7. 5 then i ? i + 1
8. 6 swap A[i] with A[j]
9. 7 }}
10. 8 swap A[i+1] with A[end]
11. 9 return i+1
12. }

Working of Quick Sort Algorithm

Now, let's see the working of the Quicksort Algorithm.

To understand the working of quick sort, let's take an unsorted array. It will make the concept
more clear and understandable.

Let the elements of array are -

37
In the given array, we consider the leftmost element as pivot. So, in this case, a[left] = 24,
a[right] = 27 and a[pivot] = 24.

Since, pivot is at left, so algorithm starts from right and move towards left.

Now, a[pivot] < a[right], so algorithm moves forward one position towards left, i.e. -

Now, a[left] = 24, a[right] = 19, and a[pivot] = 24.

Because, a[pivot] > a[right], so, algorithm will swap a[pivot] with a[right], and pivot moves
to right, as -

Now, a[left] = 19, a[right] = 24, and a[pivot] = 24. Since, pivot is at right, so algorithm starts
from left and moves to right.

As a[pivot] > a[left], so algorithm moves one position to right as -

38
Now, a[left] = 9, a[right] = 24, and a[pivot] = 24. As a[pivot] > a[left], so algorithm moves
one position to right as -

Now, a[left] = 29, a[right] = 24, and a[pivot] = 24. As a[pivot] < a[left], so, swap a[pivot] and
a[left], now pivot is at left, i.e. -

Since, pivot is at left, so algorithm starts from right, and move to left. Now, a[left] = 24,
a[right] = 29, and a[pivot] = 24. As a[pivot] < a[right], so algorithm moves one position to
left, as -

Now, a[pivot] = 24, a[left] = 24, and a[right] = 14. As a[pivot] > a[right], so, swap a[pivot]
and a[right], now pivot is at right, i.e. -

Now, a[pivot] = 24, a[left] = 14, and a[right] = 24. Pivot is at right, so the algorithm starts
from left and move to right.

39
 Now, a[pivot] = 24, a[left] = 24, and a[right] = 24. So, pivot, left and right are pointing the
same element. It represents the termination of procedure.

Element 24, which is the pivot element is placed at its exact position.

Elements that are right side of element 24 are greater than it, and the elements that are left
side of element 24 are smaller than it.

Now, in a similar manner, quick sort algorithm is separately applied to the left and right sub-
arrays. After sorting gets done, the array will be -

(b) Explain in detail about linear search with an example.

Linear Search (or Sequential Search) is the simplest searching algorithm. It works by
scanning each element of a list one by one until the desired value is found or the list ends.

Characteristics:
• Works on unsorted or sorted data.
• Simple to implement.
• Time complexity:
o Best Case: O(1) → Element is at the beginning.
o Worst Case: O(n) → Element is at the end or not present.
*QB501
o Average Case: O(n)

Working:
1. Start from the first element.
2. Compare each element with the target.
3. If match is found, return the index.
4. If the end of the list is reached without finding it, return a failure message (e.g., -1 or
"Not Found").

Example:
Let's search for the number 25 in the list:

40
 arr = [10, 15, 20, 25, 30]
target = 25
Step-by-step:
• Compare 10 with 25 → No match
• Compare 15 with 25 → No match
• Compare 20 with 25 → No match
• Compare 25 with 25 → Match found at index 3

Python Code Example:

def linear_search(arr, target):

for index, value in enumerate(arr):
if value == target:
return index # Target found
return -1 # Target not found

# Example usage:
arr = [10, 15, 20, 25, 30]
target = 25
result = linear_search(arr, target)

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

Output:
Element found at index 3

Advantages:
1) Simplicity
• Very easy to implement and understand.
• Requires minimal programming logic.
2)No Sorting Required
• Works efficiently on unsorted data, unlike algorithms like binary search that require
sorting first.
3)Versatile
• Works on arrays, linked lists, strings, and other iterable data structures.

(a)
Describe in detail about Binary Search with an example.

Ans

What is Search?
Search is a utility that enables its user to find documents, files, media, or any other type of
QB502 data held inside a database. Search works on the simple principle of matching the criteria
with the records and displaying it to the user. In this way, the most basic search function
works.

What is Binary Search?

A binary search is an advanced type of search algorithm that finds and fetches data from a
sorted list of items. Its core working principle involves dividing the data in the list to half

41
until the required value is located and displayed to the user in the search result. Binary
search is commonly known as a half-interval search or a logarithmic search.

How Binary Search Works?

The binary search works in the following manner:

• The search process initiates by locating the middle element of the sorted array of
data
• After that, the key value is compared with the element
• If the key value is smaller than the middle element, then searches analyses the upper
values to the middle element for comparison and matching
• In case the key value is greater than the middle element then searches analyses the
lower values to the middle element for comparison and matching

Example Binary Search

Let us look at the example of a dictionary. If you need to find a certain word, no one goes
through each word in a sequential manner but randomly locates the nearest words to search
for the required word.

The above image illustrates the following:

A. You have an array of 10 digits, and the element 59 needs to be found.

B. All the elements are marked with the index from 0 – 9. Now, the middle of the array
is calculated. To do so, you take the left and rightmost values of the index and divide
them by 2. The result is 4.5, but we take the floor value. Hence the middle is 4.
C. The algorithm drops all the elements from the middle (4) to the lowest bound
because 59 is greater than 24, and now the array is left with 5 elements only.
D. Now, 59 is greater than 45 and less than 63. The middle is 7. Hence the right index
value becomes middle – 1, which equals 6, and the left index value remains the same
as before, which is 5.
E. At this point, you know that 59 comes after 45. Hence, the left index, which is 5,
becomes mid as well.

42
 F. These iterations continue until the array is reduced to only one element, or the item
to be found becomes the middle of the array.

Example 2
Let’s look at the following example to understand the binary search working

A. You have an array of sorted values ranging from 2 to 20 and need to locate 18.
B. The average of the lower and upper limits is (l + r) / 2 = 4. The value being searched
is greater than the mid which is 4.
C. The array values less than the mid are dropped from search and values greater than
the mid-value 4 are searched.
D. This is a recurrent dividing process until the actual item to be s.

(b) write a Python program for Dijkstra's single source shortest path algorithm.

import sys

class Graph():
def __init__(self, vertices):
self.V = vertices
[Link] = [[0 for column in range(vertices)] for row in range(vertices)]

QB502 def printSolution(self, dist):

print("Vertex Distance from Source")
for node in range(self.V):
print(node, "\t", dist[node])

def minDistance(self, dist, sptSet):

min_val = [Link]
min_index = -1
for u in range(self.V):
if dist[u] < min_val and not sptSet[u]:
43
 min_val = dist[u]
min_index = u
return min_index

def dijkstra(self, src):

dist = [[Link]] * self.V
dist[src] = 0
sptSet = [False] * self.V

for cout in range(self.V):

x = [Link](dist, sptSet)
sptSet[x] = True
for y in range(self.V):
if ([Link][x][y] > 0 and not sptSet[y] and
dist[y] > dist[x] + [Link][x][y]):
dist[y] = dist[x] + [Link][x][y]

[Link](dist)

# Driver code
g = Graph(9)
[Link] = [
[0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]
]
[Link](0)

OUTPUT:

(a) What is Graph? Explain the terms and types and applications of Graph with examples.

What is a Graph?

QB504 A graph is a non-linear data structure made up of nodes (also called vertices) and edges
(also called arcs) that connect these nodes. Graphs are widely used to represent networks,
such as social networks, computer networks, or transportation systems.

Basic Terminology in Graphs:

44
 1. Vertex (Node): A point in the graph that represents an entity (e.g., a person in a
social network, a city in a map, etc.).
2. Edge (Arc): A connection between two vertices that represents a relationship or path
between them (e.g., a road connecting two cities, a friendship between two people,
etc.).
3. Degree of a Vertex: The number of edges connected to a vertex.
4. In-degree: Number of edges directed towards the vertex.
5. Out-degree: Number of edges directed away from the vertex.
6. Path: A sequence of vertices where each vertex is connected to the next by an edge.
7. Cycle: A path that starts and ends at the same vertex.
8. Adjacent Vertices: Two vertices are adjacent if they are connected by an edge.
9. Connected Graph: A graph is connected if there is a path between every pair of
vertices.
10. Disconnected Graph: A graph is disconnected if it is not connected; i.e., some
vertices are isolated.
11. Weighted Graph: A graph where each edge has a weight (cost, distance, etc.).
12. Unweighted Graph: A graph where edges do not have weights.

Applications of Graphs:
13. Social Networks: Graphs are used to model social connections, where vertices
represent people, and edges represent friendships.
14. Web Page Linkage: The structure of the World Wide Web can be represented as a
graph, where pages are vertices, and hyperlinks between them are edges.
15. Transportation Networks: Cities or locations can be modeled as vertices, and roads
or transportation routes between them as edges.
16. Computer Networks: Devices in a network are represented as vertices, and
communication links between them are represented as edges.
17. Recommendation Systems: Graphs are used in recommendation systems, where
items are vertices, and edges represent relationships (e.g., user likes item or user
bought item).
18. Dependency Resolution: In project management or compilation, tasks and their
dependencies can be represented as a directed acyclic graph (DAG).

Write a python code to implement prim’s algorithm.

Prim's Algorithm for Minimum Spanning Tree (MST)

Prim's algorithm is a greedy algorithm that finds the minimum spanning tree (MST) of a
weighted undirected graph. The algorithm starts with an arbitrary vertex and grows the
MST by repeatedly adding the smallest edge that connects a vertex inside the MST to a
vertex outside the MST.

Steps of Prim's Algorithm:

1. Start with any vertex in the graph and include it in the MST.
2. Find the edge with the minimum weight that connects a vertex inside the MST to a
1
vertex outside the MST.
3. Include this edge and vertex in the MST.
4. Repeat the process until all vertices are included in the MST.

import heapq
import sys # Library for INT_MAX

class Graph:
def __init__(self, vertices):
self.V = vertices
[Link] = [[0 for column in range(vertices)]
45
 for row in range(vertices)]

# A utility function to print the constructed MST stored in parent[]

def printMST(self, parent):
print("Edge \tWeight")
for i in range(1, self.V):
print(parent[i], "-", i, "\t", [Link][i][parent[i]])

# A utility function to find the vertex with minimum key value

def minKey(self, key, mstSet):
min_val = [Link]
min_index = -1

for v in range(self.V):
if key[v] < min_val and mstSet[v] is False:
min_val = key[v]
min_index = v

return min_index
# Function to construct and print MST for a graph
def primMST(self):
key = [[Link]] * self.V
parent = [None] * self.V # Array to store constructed MST
key[0] = 0 # Make key 0 so that this vertex is picked first
mstSet = [False] * self.V
parent[0] = -1 # First node is always the root

for _ in range(self.V):
u = [Link](key, mstSet)
mstSet[u] = True

for v in range(self.V):
if [Link][u][v] > 0 and mstSet[v] is False and key[v] >
[Link][u][v]:
key[v] = [Link][u][v]
parent[v] = u

[Link](parent)

# Example usage:
g = Graph(5)
[Link] = [
[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]
]

[Link]()

Output:

46
47