0% found this document useful (0 votes)

5 views44 pages

Lab Programs-2

The document contains multiple Python programs demonstrating data structures and algorithms, including implementations of stacks and queues using arrays, conversion of infix expressions to postfix, evaluation of postfix expressions, and checking balanced parentheses. It also includes recursive functions for calculating factorials, Fibonacci numbers, and GCD, as well as operations on singly and doubly linked lists such as insertion, deletion, searching, and sorting. Each section provides code snippets along with expected outputs.

Uploaded by

muskanmushu264

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

5 views44 pages

Lab Programs-2

Uploaded by

muskanmushu264

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

Lab Programs

1. Write a program to implement the following using an array

a) Full Implementations of Stack using Array

class myStack:

def init(self, cap):

[Link] = cap

[Link] = [0] * [Link]

[Link] = -1

def push(self, x):

if [Link] == [Link] - 1:

print("Stack Overflow")

return

[Link] += 1

[Link][[Link]] = x
def pop(self):

if [Link] == -1:

print("Stack Underflow")

return -1

val = [Link][[Link]]
[Link] -= 1

return val

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

print("Stack is Empty")

return -1

return [Link][[Link]]

def isEmpty(self):

return [Link] == -1

def isFull(self):
return [Link] == [Link] - 1

I SUBHASHINI [Link] in Computer Science Page 1

if __name__ == "__main__":

st = myStack(4)

[Link](1)

[Link](2)
[Link](3)

[Link](4)

print("Popped:", [Link]())

print("Top element:", [Link]())

print("Is stack empty: ", "Yes" if [Link]() else "No")

print("Is stack full: ", "Yes" if [Link]() else "No")

Output:

Popped: 4
Top element: 3

Is stack empty: No

Is stack full: No

b) Full Implementations of Queue using Array

class myQueue:

def init(self, capacity):

[Link] = capacity
[Link] = [0] * capacity

[Link] = 0

def isEmpty(self):

return [Link] == 0

def isFull(self):

return [Link] == [Link]

def enqueue(self, x):

if [Link]():

print("Queue is full!")
return

I SUBHASHINI [Link] in Computer Science Page 2

[Link][[Link]] = x

[Link] += 1

def dequeue(self):

if [Link]():
print("Queue is empty!")

return

for i in range(1, [Link]):

[Link][i - 1] = [Link][i]

[Link] -= 1

def getFront(self):

if [Link]():

print("Queue is empty!")
return -1

return [Link][0]

def getRear(self):

if [Link]():

print("Queue is empty!")

return -1

return [Link][[Link] - 1]
if __name__ == '__main__':

q = myQueue(3)

[Link](10)

[Link](20)

[Link](30)

print("Front:", [Link]())

[Link]()
print("Front:", [Link]())

print("Rear:", [Link]())
[Link](40)

I SUBHASHINI [Link] in Computer Science Page 3

Output:

Front: 10

Front: 20

Rear: 30

[Link] a program to convert the given infix expression to postfix expression using stack
def prec(c):
if c == '^':
return 3
elif c == '/' or c == '*':
return 2
elif c == '+' or c == '-':
return 1
else:
return -1
def isRightAssociative(c):
return c == '^'
def infixToPostfix(s):
st = []
res = []
for c in s:
if ('a' <= c <= 'z') or ('A' <= c <= 'Z') or ('0' <= c <= '9'):
[Link](c)
elif c == '(':
[Link]('(')
elif c == ')':
while st and st[-1] != '(':
[Link]([Link]())
[Link]()
else:
while st and st[-1] != '(' and \
(prec(st[-1]) > prec(c) or (prec(st[-1]) == prec(c) \
and not isRightAssociative(c))):
[Link]([Link]())
[Link](c)
while st:
[Link]([Link]())

return ''.join(res)
if __name__ == '__main__':
exp = "a*(b+c)/d"
print(infixToPostfix(exp))

I SUBHASHINI [Link] in Computer Science Page 4

Output
abc+*d/

3. write a program to evaluate a postfix expression using stack in python

import math

def evaluatePostfix(arr):

st = []
for token in arr:

if token[0].isdigit() or (len(token) > 1 and token[0] == '-'):

[Link](int(token))

else:

val1 = [Link]()

val2 = [Link]()

if token == '+':
[Link](val2 + val1)

elif token == '-':

[Link](val2 - val1)

elif token == '*':

[Link](val2 * val1)
elif token == '/':

[Link](val2 // val1)
elif token == '^':
[Link](int([Link](val2, val1)))

return [Link]()

if __name__ == '__main__':

arr = ["2", "3", "1", "*", "+", "9", "-"]

print(evaluatePostfix(arr))

Output
-4

I SUBHASHINI [Link] in Computer Science Page 5

4). Write a program to ensure the parentheses are nested correctly in an arithmetic
expression.

def is_balanced(expression):

"""

Checks if the parentheses in an arithmetic expression are correctly nested.

Supports '()', '{}', and '[]'.

"""
stack = []

pairs = {

')': '(',

'}': '{',

']': '['

for char in expression:

if char in '([{':

[Link](char)

elif char in ')]}':

if not stack:

return False
if stack[-1] == pairs[char]:

[Link]()
else:
return False

return len(stack) == 0

expr1 = "(3 + 4 * {1 + [2]})"

if is_balanced(expr1):

print(f"The expression '{expr1}' is balanced.")

else:
print(f"The expression '{expr1}' is not balanced.")

I SUBHASHINI [Link] in Computer Science Page 6

expr2 = "((a + b) * c"

if is_balanced(expr2):

print(f"The expression '{expr2}' is balanced.")

else:
print(f"The expression '{expr2}' is not balanced.")

expr3 = "([)]"

if is_balanced(expr3):

print(f"The expression '{expr3}' is balanced.")

else:

print(f"The expression '{expr3}' is not balanced.")

expr4 = "{[()()]}"

if is_balanced(expr4):
print(f"The expression '{expr4}' is balanced.")

else:

print(f"The expression '{expr4}' is not balanced.")

Output:
The expression '(3 + 4 * {1 + [2]})' is balanced.

The expression '((a + b) * c' is not balanced.

The expression '([)]' is not balanced.

The expression '{[()()]}' is balanced.

5) Write aprogram to find following using Recursion

a). Factorial of +ve integer

def factorial(n):
if (n==1 or n==0):

return 1

else:

return (n * factorial(n - 1))

num = 5;

I SUBHASHINI [Link] in Computer Science Page 7

print("number : ",num)

print("Factorial : ",factorial(num))

Output
number : 5
Factorial : 120
b) nth term of the Fibonacci Sequence
def Fibonacci(n):

if n<= 0:
print("Incorrect input")

elif n == 1:

return 0

elif n == 2:

return 1

else:

return Fibonacci(n-1)+Fibonacci(n-2)
print(Fibonacci(10))

Output:
34

c). GCD of two positive intergers

def gcd(a,b):
if(b==0):
return a
else:
return gcd(b,a%b)
a=int(input("Enter first number:"))
b=int(input("Enter second number:"))
GCD=gcd(a,b)
print("GCD is: ")
print(GCD)
Output:
Enter first number:10

Enter second number:20

GCD is:

6).Write a program to create a single linked list and write functions to implement the
following operations.

I SUBHASHINI [Link] in Computer Science Page 8

a) Insert an element at a specified position
class Node:

def init(self, x):

[Link] = x
[Link] = None

def insertPos(head, pos, val):

if pos < 1:

return head

if pos == 1:

newNode = Node(val)

[Link] = head

return newNode
curr = head

for i in range(1, pos - 1):

if curr is None:

return head

curr = [Link]

if curr is None:

return head
newNode = Node(val)

[Link] = [Link]

[Link] = newNode

return head

def printList(head):

curr = head

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

if [Link]:
print(" -> ", end="")

I SUBHASHINI [Link] in Computer Science Page 9

curr = [Link]

print()

if __name__ == "__main__":

head = Node(1)
[Link] = Node(2)

[Link] = Node(4)

val, pos = 3, 3

head = insertPos(head, pos, val)

printList(head)

Output:

Output
1 -> 2 -> 3 -> 4
b) Delete a specified element in the list
class Node:

def init(self, data):

[Link] = data

[Link] = None

class LinkedList:

def __init__(self):

[Link] = None

def push(self, new_data):

new_node = Node(new_data)

new_node.next = [Link]

[Link] = new_node

def deleteNode(self, key):

temp = [Link]

if (temp is not None):

if ([Link] == key):
[Link] = [Link]
temp = None

I SUBHASHINI [Link] in Computer Science Page 10

return

while(temp is not None):

if [Link] == key:

break
prev = temp

temp = [Link]

if(temp == None):

return

[Link] = [Link]

temp = None

def printList(self):

temp = [Link]
while(temp):

print (" %d" %([Link])),

temp = [Link]

llist = LinkedList()

[Link](7)

[Link](1)

[Link](3)
[Link](2)

print ("Created Linked List: ")

[Link]()

[Link](1)

print ("Linked List after Deletion of 1:")

[Link]()

Output
Created Linked List:
2
3
1
7
Linked List after Deletion of 1:

I SUBHASHINI [Link] in Computer Science Page 11

2
3
7
C). Search for an element and find its position in the list
class Node:

def init(self, data):

[Link] = data
[Link] = None

class LinkedList:

def __init__(self):

[Link] = None

def push(self, new_data):

new_node = Node(new_data)

new_node.next = [Link]
[Link] = new_node

def search(self, x):

current = [Link]

while current != None:

if [Link] == x:

return True

current = [Link]

return False
if __name__ == '__main__':

llist = LinkedList()

[Link](10);

[Link](30);

[Link](11);

[Link](21);

[Link](14);

I SUBHASHINI [Link] in Computer Science Page 12

if [Link](21):

print("Yes")

else:

print("No")

Output:

Yes
D). Sort the elements in the list ascending order
class Node:

def init(self, data=None):

[Link] = data

[Link] = None
class SinglyLinkedList:

def __init__(self):

[Link] = None

def append(self, data):

new_node = Node(data)

if [Link] is None:

[Link] = new_node
return

last_node = [Link]

while last_node.next:

last_node = last_node.next

last_node.next = new_node

def display(self):

elements = []
current = [Link]

while current:
[Link]([Link])

I SUBHASHINI [Link] in Computer Science Page 13

current = [Link]

print(elements)

def sort_ascending(self):

"""Sorts the linked list elements in ascending order."""

values = []

current = [Link]

while current:

[Link]([Link])

current = [Link]

[Link]()

current = [Link]

for value in values:

if current:

[Link] = value

current = [Link]

else:

break

my_list = SinglyLinkedList()

my_list.append(34)
my_list.append(1)

my_list.append(9)

my_list.append(5)

my_list.append(22)

print("Original list:")

my_list.display()

my_list.sort_ascending()
print("Sorted list (ascending):")

my_list.display()

Output:

I SUBHASHINI [Link] in Computer Science Page 14

Original list:
[34, 1, 9, 5, 22]
Sorted list (ascending):
[1, 5, 9, 22, 34]
7. Write a program to create a double linked list and write functions to implement the
following operations

a) Insert an element at a specified position

class Node:

def init(self, new_data):

[Link] = new_data
[Link] = None

[Link] = None

def insertAtPos(head, pos, new_data):

new_node = Node(new_data)

if pos == 1:

new_node.next = head

if head is not None:

[Link] = new_node
head = new_node

return head

curr = head

for i in range(1, pos - 1):

if curr is None:

break

curr = [Link]
if curr is None:

return head

new_node.prev = curr

new_node.next = [Link]

[Link] = new_node
if new_node.next is not None:

I SUBHASHINI [Link] in Computer Science Page 15

new_node.[Link] = new_node

return head

def printList(head):

curr = head
while curr is not None:

print([Link], end="")

if [Link] is not None:

print(" <-> ", end="")

curr = [Link]

print()

if __name__ == "__main__":

head = Node(1)
[Link] = Node(2)

[Link] = head

[Link] = Node(4)

[Link] = [Link]

data = 3

pos = 3

head = insertAtPos(head, pos, data)

printList(head)

Output:

1 <-> 2 <-> 3 <-> 4

b) Delete a specified element in the list

# Python Program to delete node at a specific position

# in Doubly Linked List

class Node:

def init(self, data):

[Link] = data
[Link] = None

I SUBHASHINI [Link] in Computer Science Page 16

[Link] = None

def del_pos(head, pos):

if head is None:

return head
curr = head

for i in range(1, pos):

if curr is None:

return head

curr = [Link]

if curr is None:

return head

if [Link] is not None:

[Link] = [Link]

if [Link] is not None:

[Link] = [Link]

if head == curr:

head = [Link]

return head

def print_list(head):
curr = head

while curr is not None:

print([Link], end=" ")

curr = [Link]

print()

if __name__ == "__main__":

head = Node(1)
[Link] = Node(2)

[Link] = head
[Link] = Node(3)

I SUBHASHINI [Link] in Computer Science Page 17

[Link] = [Link]

head = del_pos(head, 2)

print_list(head)

Output:

c).Search for an element and find its position in the list

# Python Code for Searching in Doubly Linked List

class Node:

def init(self, data):

[Link] = data
[Link] = None

[Link] = None

def search(head, x):

curr = head

pos = 0

while curr is not None and [Link] != x:

pos += 1
curr = [Link]
if curr is None or [Link] != x:

return -1

return pos + 1

if __name__ == '__main__':

head = None

x=8

head = Node(18)
[Link] = Node(15)

[Link] = head

[Link] = Node(8)
[Link] = [Link]

I SUBHASHINI [Link] in Computer Science Page 18

[Link] = Node(9)

[Link] = [Link]

[Link] = Node(14)

[Link] = [Link]
print(search(head, x))

Output:

d). Sort the elements in the list ascending order

class Node:

"""Class to create a new node for the doubly linked list."""

def __init__(self, data):

[Link] = data

[Link] = None

class DoublyLinkedList:

"""Class to represent the doubly linked list and its operations."""

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

"""Adds a new node to the end of the list."""

new_node = Node(data)

if not [Link]:

[Link] = new_node

return

last = [Link]
while [Link]:

last = [Link]

[Link] = new_node
new_node.prev = last

I SUBHASHINI [Link] in Computer Science Page 19

def bubble_sort(self):

"""Sorts the doubly linked list in ascending order using bubble sort."""

if not [Link]:

return
i = [Link]

while i:

j = [Link]

while [Link]:

if [Link] > [Link]:

[Link], [Link] = [Link], [Link]

j = [Link]

i = [Link]
def display(self):

"""Prints the data in the list from head to tail."""

current = [Link]

elements = []

while current:

[Link](str([Link]))

current = [Link]
print(" -> ".join(elements))

dll = DoublyLinkedList()

[Link](45)

[Link](12)

[Link](83)

[Link](6)

[Link](24)
print("Original list:")

[Link]() # Output: Original list: 45 -> 12 -> 83 -> 6 -> 24

dll.bubble_sort()

I SUBHASHINI [Link] in Computer Science Page 20

print("Sorted list (ascending):")

[Link]() # Output: Sorted list (ascending): 6 -> 12 -> 24 -> 45 -> 83

Output:

Original list:

45 -> 12 -> 83 -> 6 -> 24

Sorted list (ascending):

6 -> 12 -> 24 -> 45 -> 83

8). Write a program to create single circular linked lists and function to implement the
following operations.

a) Insert an element at a specified position

class Node:

def init(self, value):

[Link] = value

[Link] = None

def insertAtPosition(last, data, pos):

if last is None:

if pos != 1:

print("Invalid position!")

return last

new_node = Node(data)
last = new_node

[Link] = last

return last

new_node = Node(data)

curr = [Link]

if pos == 1:

new_node.next = curr
[Link] = new_node
return last

I SUBHASHINI [Link] in Computer Science Page 21

for i in range(1, pos - 1):

curr = [Link]

if curr == [Link]:

print("Invalid position!")
return last

new_node.next = [Link]

[Link] = new_node

if curr == last:

last = new_node

return last

def print_list(last):

if last is None:
return

head = [Link]

while True:

print([Link], end=" ")

head = [Link]

if head == [Link]:

break
print()

if __name__ == "__main__":

# Create circular linked list: 2, 3, 4

first = Node(2)

[Link] = Node(3)

[Link] = Node(4)

last = [Link]
[Link] = first

print("Original list: ", end="")

print_list(last)

I SUBHASHINI [Link] in Computer Science Page 22

data = 5

pos = 2

last = insertAtPosition(last, data, pos)

print("List after insertions: ", end="")

print_list(last)

Output:

Original list: 2 3 4

List after insertions: 2 5 3 4

b) Delete a specified element in the list

class Node:
def __init__(self, data):
[Link] = data
[Link] = None
class LinkedList:
def __init__(self):
[Link] = None
def push(self, new_data):
new_node = Node(new_data)
new_node.next = [Link]
[Link] = new_node
def deleteNode(self, key):
temp = [Link]
if (temp is not None):
if ([Link] == key):
[Link] = [Link]
temp = None
return
while(temp is not None):
if [Link] == key:
break
prev = temp
temp = [Link]
if(temp == None):
return
[Link] = [Link]
temp = None
def printList(self):
temp = [Link]
while(temp):

Output
Created Linked List:
2
3
1
7
Linked List after Deletion of 1:
2
3
7
c).Search for an element and find its position in the list
class Node:

def init(self, x):

[Link] = x

[Link] = None

def search_key(head, key):

curr = head
while curr is not None:

if [Link] == key:

return True

curr = [Link]
return False

I SUBHASHINI [Link] in Computer Science Page 24

if __name__ == "__main__":

head = Node(1)

[Link] = Node(2)

[Link] = Node(3)
[Link] = Node(4)

[Link] = Node(5)

key = 5

if search_key(head, key):

print("true")

else:

print("false")

Output
true
9) Write a program to implement the following using a single linked list:

a) Stack ADT
class Node:

def init(self, data):

[Link] = data

[Link] = None

class Stack:

def __init__(self):

[Link] = None
def isempty(self):

if [Link] == None:

return True

else:

return False

def push(self, data):

if [Link] == None:

I SUBHASHINI [Link] in Computer Science Page 25

[Link] = Node(data)

else:

newnode = Node(data)

[Link] = [Link]
[Link] = newnode

def pop(self):

if [Link]():

return None

else:

poppednode = [Link]

[Link] = [Link]

[Link] = None
return [Link]

def peek(self):

if [Link]():

return None

else:

return [Link]

def display(self):
iternode = [Link]

if [Link]():

print("Stack Underflow")

else:

while(iternode != None):

print([Link], end="")

iternode = [Link]
if(iternode != None):

print(" -> ", end="")

return

I SUBHASHINI [Link] in Computer Science Page 26

stack = Stack()

[Link](10)

[Link](20)

[Link](30)
[Link]()

print("\nTop element:", [Link]())

print("Popped element:", [Link]())

[Link]()

Output
30 -> 20 -> 10
Top element: 30
Popped element: 30
Popped element: 20
10
b).Queue ADT
class Node:

def init(self, key):

[Link] = key
[Link] = None

class MyQueue:

def __init__(self):

[Link] = None

[Link] = 0

def enqueue(self, x):

temp = Node(x)
if [Link] is None:

[Link] = temp
[Link] = temp

I SUBHASHINI [Link] in Computer Science Page 27

else:

[Link] = temp

[Link] += 1
def dequeue(self):

if [Link] is None:

return None

res = [Link]

[Link] = [Link]

if [Link] is None:

[Link] = None

[Link] -= 1
return res

def getFront(self):

if [Link] is None:

return None

return [Link]

def getRear(self):

if [Link] is None:
return None

return [Link]

def isEmpty(self):

return [Link] is None

def getSize(self):

return [Link]

if __name__ == "__main__":
queue = MyQueue()

[Link](10)
[Link](20)

I SUBHASHINI [Link] in Computer Science Page 28

[Link](30)

print([Link]())

print([Link]())
print([Link]())

print([Link]())

Output
10
20
30
False
2
20
30
True
10).Write a program to implement Binary search technique using Iterative method and
Recursive methods.
a).Iterative method
def binary_search(arr, x):

low = 0

high = len(arr) - 1

while low <= high:

mid = low + (high - low) // 2

if arr[mid] < x:
low = mid + 1

elif arr[mid] > x:

high = mid - 1
else:

I SUBHASHINI [Link] in Computer Science Page 29

return mid

return -1

arr = [2, 3, 4, 10, 40]

x = 10
result = binary_search(arr, x)

if result != -1:

print("Element is present at index", result)

else:

print("Element is not present in array")

Output
Element is present at index 3
b) . Recursive methods.

def binary_search(arr, low, high, x):

if high >= low:

mid = low + (high - low) // 2

if arr[mid] == x:

return mid

elif arr[mid] > x:

return binary_search(arr, low, mid - 1, x)

else:

return binary_search(arr, mid + 1, high, x)

else:
return -1

arr = [2, 3, 4, 10, 40]

x = 10

result = binary_search(arr, 0, len(arr) - 1, x)

if result != -1:

print("Element is present at index", result)

else:

I SUBHASHINI [Link] in Computer Science Page 30

print("Element is not present in array")

Output
Element is present at index 3
11). Write a program for sorting the given list numbers in ascending order using the
following technique:

a).Bubble sort
def bubbleSort(arr):

n = len(arr)

for i in range(n):

swapped = False
for j in range(0, n - i - 1):

if arr[j] > arr[j + 1]:

arr[j], arr[j + 1] = arr[j + 1], arr[j]

swapped = True

if not swapped:

break

arr = [64, 34, 25, 12, 22, 11, 90]

bubbleSort(arr)

print(arr)

Output
[11, 12, 22, 25, 34, 64, 90]
b).Selection sort
def selectionSort(array, size):

for ind in range(size):

min_index = ind

for j in range(ind + 1, size):

if array[j] < array[min_index]:

min_index = j

array[ind], array[min_index] = array[min_index], array[ind]

arr = [-2, 45, 0, 11, -9, 88, -97, -202, 747]

I SUBHASHINI [Link] in Computer Science Page 31

size = len(arr)

selectionSort(arr, size)

print(arr)

Output
[-202, -97, -9, -2, 0, 11, 45, 88, 747]
12).Write a program for sorting the given list numbers in ascending order using the
following technique:

a).Insertion sort
def insertionSort(arr):

n = len(arr)
if n <= 1:

return

for i in range(1, n):

key = arr[i]

j=i-1

while j >= 0 and key < arr[j]:

arr[j + 1] = arr[j]
j -= 1

arr[j + 1] = key

arr = [12, 11, 13, 5, -1]

insertionSort(arr)

print(arr)

Output
[-1, 5, 11, 12, 13]
b).Quick Sort
def partition(arr, low, high):

pivot = arr[high]
i = low - 1

for j in range(low, high):

if arr[j] <= pivot:

I SUBHASHINI [Link] in Computer Science Page 32

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:

p = partition(arr, low, high)

quick_sort(arr, low, p - 1)

quick_sort(arr, p + 1, high)

arr = [1, 7, 4, 1, 10, 9, -2]

quick_sort(arr, 0, len(arr) - 1)

print(arr)

Output
[-2, 1, 1, 4, 7, 9, 10]
13).Write a program for sorting the given list numbers in ascending order using the
following technique:

a).Merge sort
def merge(arr, l, m, r):

n1 = m - l + 1

n2 = r - m

L = [0] * n1

R = [0] * n2
for i in range(n1):

L[i] = arr[l + i]
for j in range(n2):

R[j] = arr[m + 1 + j]

i=j=0

k=l

while i < n1 and j < n2:

if L[i] <= R[j]:

I SUBHASHINI [Link] in Computer Science Page 33

arr[k] = L[i]

i += 1

else:

arr[k] = R[j]
j += 1

k += 1

while i < n1:

arr[k] = L[i]

i += 1

k += 1

while j < n2:

arr[k] = R[j]
j += 1

k += 1

def mergeSort(arr, l, r):

if l < r:

m = l + (r - l) // 2

mergeSort(arr, l, m)

mergeSort(arr, m + 1, r)
merge(arr, l, m, r)

arr = [12, 11, 13, 5, 6, 7]

print("Given array is:", arr)

mergeSort(arr, 0, len(arr) - 1)

print("Sorted array is:", arr)

Output
Given array is: [12, 11, 13, 5, 6, 7]
Sorted array is: [5, 6, 7, 11, 12, 13]
b).Heapsort
def heapify(arr, n, i):
largest = i

I SUBHASHINI [Link] in Computer Science Page 34

l=2*i+1

r=2*i+2

if l < n and arr[l] > arr[largest]:

largest = l
if r < n and arr[r] > arr[largest]:

largest = r

if largest != i:

arr[i], arr[largest] = arr[largest], arr[i]

heapify(arr, n, largest)

def heapSort(arr):

n = len(arr)

for i in range(n // 2 - 1, -1, -1):

heapify(arr, n, i)

for i in range(n - 1, 0, -1):

arr[i], arr[0] = arr[0], arr[i] # Swap max to end

heapify(arr, i, 0)

arr = [12, 11, 13, 5, 6, 7]

heapSort(arr)

print("Sorted array is:", arr)

Output
('Sorted array is:', [5, 6, 7, 11, 12, 13])
14) Write a program to traverse a binary tree in following way
a).Pre-order
class Node:

def init(self, data):

[Link] = data

[Link] = None

[Link] = None
def preOrder(node, res):

I SUBHASHINI [Link] in Computer Science Page 35

if not node:

return

[Link]([Link])

preOrder([Link], res)
preOrder([Link], res)

if __name__ == "__main__":

# Create binary tree

# 1

# / \

# 2 3

# /\ \

# 4 5 6
root = Node(1)

[Link] = Node(2)

[Link] = Node(3)

[Link] = Node(4)

[Link] = Node(5)

[Link] = Node(6)

result = []
preOrder(root, result)

print(*result)

Output
1 2 4 5 3 6
b) In-order
class Node:

def init(self, x):

[Link] = x

[Link] = None
[Link] = None

I SUBHASHINI [Link] in Computer Science Page 36

def inOrder(node, res):

if node is None:

return

inOrder([Link], res)
[Link]([Link])

inOrder([Link], res)

if __name__ == "__main__":

# Create binary tree

# 1

# / \

# 2 3

# /\ \
# 4 5 6

root = Node(1)

[Link] = Node(2)

[Link] = Node(3)

[Link] = Node(4)

[Link] = Node(5)

[Link] = Node(6)
res = []

inOrder(root, res)

for node in res:

print(node, end=" ")

Output
4 2 5 1 3 6
c) Post-order
class Node:

def init(self, v):

[Link] = v

I SUBHASHINI [Link] in Computer Science Page 37

[Link] = None

def postOrder(node, res):

if node is None:
return

postOrder([Link], res)

[Link]([Link])

if __name__ == "__main__":

#Represent Tree

# 1

# /\
# 2 3

# /\ \

# 4 5 6

root = Node(1)

[Link] = Node(2)

[Link] = Node(3)

[Link] = Node(4)
[Link] = Node(5)

[Link] = Node(6)

result = []

postOrder(root, result)

for val in result:

print(val, end=" ")

Output:
4 5 2 6 3 1

15). Write a program to the implementation graph traversals

a). BFS

I SUBHASHINI [Link] in Computer Science Page 38

from collections import defaultdict

class Graph:

def __init__(self):

[Link] = defaultdict(list)
def addEdge(self, u, v):

[Link][u].append(v)

def BFS(self, s):

visited = [False] * (max([Link]) + 1)

queue = []

[Link](s)

visited[s] = True

while queue:
s = [Link](0)

print(s, end=" ")

for i in [Link][s]:

if not visited[i]:

[Link](i)

visited[i] = True

if __name__ == '__main__':
g = Graph()

[Link](0, 1)

[Link](0, 2)

[Link](1, 2)

[Link](2, 0)

[Link](2, 3)

[Link](3, 3)
print("Following is Breadth First Traversal"

" (starting from vertex 2)")

[Link](2)

I SUBHASHINI [Link] in Computer Science Page 39

Output
Following is Breadth First Traversal (starting from vertex 2)
2 0 3 1
b). DFS
from collections import defaultdict

class Graph:

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

def addEdge(self, u, v):

[Link][u].append(v)

def DFSUtil(self, v, visited):

[Link](v)

print(v, end=' ')

for neighbour in [Link][v]:

if neighbour not in visited:

[Link](neighbour, visited)

def DFS(self, v):

visited = set()

[Link](v, visited)
if __name__ == "__main__":

g = Graph()
[Link](0, 1)

[Link](0, 2)

[Link](1, 2)

[Link](2, 0)

[Link](2, 3)

[Link](3, 3)

print("Following is Depth First Traversal (starting from vertex 2)")

[Link](2)

Output
I SUBHASHINI [Link] in Computer Science Page 40
Following is Depth First Traversal (starting from vertex 2):
2 0 1 3
16). Write a program to find the minimum spanning tree for a weighted graph using
a). Prim’s Algorithm

import sys

class Graph():

def init(self, vertices):

self.V = vertices

[Link] = [[0 for column in range(vertices)]

for row in range(vertices)]

def printMST(self, parent):

print("Edge \tWeight")

for i in range(1, self.V):

print(parent[i], "-", i, "\t", [Link][parent[i]][i])

def minKey(self, key, mstSet):

min = [Link]

for v in range(self.V):

if key[v] < min and mstSet[v] == False:

min = key[v]

min_index = v

return min_index

def primMST(self):

key = [[Link]] * self.V

parent = [None] * self.V # Array to store constructed MST

key[0] = 0
mstSet = [False] * self.V

parent[0] = -1 # First node is always the root of

for cout in range(self.V):

u = [Link](key, mstSet)

I SUBHASHINI [Link] in Computer Science Page 41

mstSet[u] = True

for v in range(self.V):

if [Link][u][v] > 0 and mstSet[v] == False \

and key[v] > [Link][u][v]:

key[v] = [Link][u][v]

parent[v] = u

[Link](parent)

if __name__ == '__main__':

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
Edge Weight
0 - 1 2
1 - 2 3
0 - 3 6
1 - 4 5
b). Kruskal’s Algorithm
class Graph:

def init(self, vertices):

self.V = vertices

[Link] = []
def addEdge(self, u, v, w):

[Link]([u, v, w])
def find(self, parent, i):

I SUBHASHINI [Link] in Computer Science Page 42

if parent[i] != i:

parent[i] = [Link](parent, parent[i])

return parent[i]

def union(self, parent, rank, x, y):

if rank[x] < rank[y]:

parent[x] = y

elif rank[x] > rank[y]:

parent[y] = x

else:

parent[y] = x

rank[x] += 1

def KruskalMST(self):
result = []

i=0

e=0

[Link] = sorted([Link],

key=lambda item: item[2])

parent = []

rank = []
for node in range(self.V):

[Link](node)

[Link](0)

while e < self.V - 1:

u, v, w = [Link][i]

i=i+1

x = [Link](parent, u)
y = [Link](parent, v)

if x != y:
e=e+1

I SUBHASHINI [Link] in Computer Science Page 43

[Link]([u, v, w])

[Link](parent, rank, x, y)

minimumCost = 0

print("Edges in the constructed MST")

for u, v, weight in result:

minimumCost += weight

print("%d -- %d == %d" % (u, v, weight))

print("Minimum Spanning Tree", minimumCost)

if __name__ == '__main__':

g = Graph(4)

[Link](0, 1, 10)

[Link](0, 2, 6)
[Link](0, 3, 5)

[Link](1, 3, 15)

[Link](2, 3, 4)

[Link]()

Output
Edges in the constructed MST
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
Minimum Spanning Tree 19

I SUBHASHINI [Link] in Computer Science Page 44

Lab Programs-1
No ratings yet
Lab Programs-1
44 pages
Lab Programs
No ratings yet
Lab Programs
42 pages
Python ADTs: Stack, Queue, List Implementations
No ratings yet
Python ADTs: Stack, Queue, List Implementations
58 pages
Python Data Structures Implementation
No ratings yet
Python Data Structures Implementation
13 pages
Data Structures in Python: Lab Exercises
No ratings yet
Data Structures in Python: Lab Exercises
71 pages
Stack Data Structure in Python
No ratings yet
Stack Data Structure in Python
7 pages
Data Structures in Python: Lists, Stacks, Queues
No ratings yet
Data Structures in Python: Lists, Stacks, Queues
7 pages
Python ADTs: Stacks, Queues, Lists
No ratings yet
Python ADTs: Stacks, Queues, Lists
27 pages
Fycs Daa Lab
No ratings yet
Fycs Daa Lab
21 pages
Python Data Structures and Algorithms
No ratings yet
Python Data Structures and Algorithms
83 pages
Unit 2 (Stack)
No ratings yet
Unit 2 (Stack)
35 pages
Implement ADTs and Algorithms in Python
No ratings yet
Implement ADTs and Algorithms in Python
44 pages
DSA Lab Program
No ratings yet
DSA Lab Program
42 pages
Stack Data Structure and Functions
No ratings yet
Stack Data Structure and Functions
2 pages
Searching and Data Structure Algorithms
No ratings yet
Searching and Data Structure Algorithms
60 pages
Inbound 5495530359191823007
No ratings yet
Inbound 5495530359191823007
6 pages
Stack Operations and Implementations Lab Report
No ratings yet
Stack Operations and Implementations Lab Report
13 pages
Python Stack Implementation Guide
No ratings yet
Python Stack Implementation Guide
5 pages
Python ADTs: Stack, Queue, List Implementation
No ratings yet
Python ADTs: Stack, Queue, List Implementation
51 pages
Understanding Stack Data Structure
No ratings yet
Understanding Stack Data Structure
10 pages
Dsa
No ratings yet
Dsa
5 pages
Wa0001.
No ratings yet
Wa0001.
6 pages
Stack 2026
No ratings yet
Stack 2026
7 pages
Stack Implementation with Python Arrays
No ratings yet
Stack Implementation with Python Arrays
50 pages
AD3271 Data Structures Lab Manual
0% (1)
AD3271 Data Structures Lab Manual
39 pages
Data Structures & Algorithms Cheat Sheet
No ratings yet
Data Structures & Algorithms Cheat Sheet
4 pages
Implementing ADTs and Algorithms in Python
No ratings yet
Implementing ADTs and Algorithms in Python
49 pages
Python Stack Data Structure Guide
No ratings yet
Python Stack Data Structure Guide
38 pages
DSPP Lab Manual
No ratings yet
DSPP Lab Manual
72 pages
IE2108 Data Structures Tutorial 4
No ratings yet
IE2108 Data Structures Tutorial 4
5 pages
Understanding Data Structures and Types
No ratings yet
Understanding Data Structures and Types
22 pages
Python Programs for Data Structures
No ratings yet
Python Programs for Data Structures
29 pages
DSA Practical: Stacks and Queues
No ratings yet
DSA Practical: Stacks and Queues
2 pages
Stack, Queue, and List Operations in Python
No ratings yet
Stack, Queue, and List Operations in Python
57 pages
Python ADTs: Stacks, Queues, and Lists
No ratings yet
Python ADTs: Stacks, Queues, and Lists
37 pages
30 Advanced Python Case Studies
No ratings yet
30 Advanced Python Case Studies
16 pages
Python Sorting and Searching Algorithms
No ratings yet
Python Sorting and Searching Algorithms
22 pages
Stack Applications in Programming
No ratings yet
Stack Applications in Programming
5 pages
DS Practicals (1) - 2
No ratings yet
DS Practicals (1) - 2
24 pages
Class 12 Stack Programs Overview
No ratings yet
Class 12 Stack Programs Overview
8 pages
Implementing ADTs in Python Classes
No ratings yet
Implementing ADTs in Python Classes
39 pages
Class XII Computer Science Preboard Exam
No ratings yet
Class XII Computer Science Preboard Exam
13 pages
Understanding Stacks in Data Structures
No ratings yet
Understanding Stacks in Data Structures
7 pages
CBSE DS Notes
No ratings yet
CBSE DS Notes
15 pages
Python Stacks Notes for CBSE Class XII
No ratings yet
Python Stacks Notes for CBSE Class XII
14 pages
Data Structures and Algorithms Examples
No ratings yet
Data Structures and Algorithms Examples
10 pages
Python Algorithms and Data Structures
No ratings yet
Python Algorithms and Data Structures
4 pages
DSA Lab
No ratings yet
DSA Lab
34 pages
Python Programs for Data Structures
No ratings yet
Python Programs for Data Structures
18 pages
CS1010S Python Cheat Sheet
No ratings yet
CS1010S Python Cheat Sheet
3 pages
CD3281 Data Structures Lab Manual
No ratings yet
CD3281 Data Structures Lab Manual
60 pages
Python Array and List Operations
No ratings yet
Python Array and List Operations
76 pages
Doubly Linked List Operations in C
No ratings yet
Doubly Linked List Operations in C
14 pages
C Structs in Data Structures Lab
No ratings yet
C Structs in Data Structures Lab
55 pages
C Programming: Linked List Operations
No ratings yet
C Programming: Linked List Operations
13 pages
Linked List Operations and Structures
No ratings yet
Linked List Operations and Structures
29 pages
Understanding Data Structures Basics
No ratings yet
Understanding Data Structures Basics
38 pages
Linked List Operations and Complexity
No ratings yet
Linked List Operations and Complexity
25 pages
Data Structures: Arrays & Linked Lists
No ratings yet
Data Structures: Arrays & Linked Lists
21 pages
Circular Doubly Linked List Operations
No ratings yet
Circular Doubly Linked List Operations
5 pages
Disadvantages and Advantages of Linked Lists
No ratings yet
Disadvantages and Advantages of Linked Lists
72 pages
Linked List Fundamentals MCQs
No ratings yet
Linked List Fundamentals MCQs
16 pages
Types of Linked Lists Explained
No ratings yet
Types of Linked Lists Explained
9 pages
Linked List Complexity Overview
No ratings yet
Linked List Complexity Overview
72 pages
Web Browser History Management in C
No ratings yet
Web Browser History Management in C
13 pages
Data Structures MCQs with Answers
No ratings yet
Data Structures MCQs with Answers
37 pages
DS Module1 LinearDataStructures Detailed Notes
No ratings yet
DS Module1 LinearDataStructures Detailed Notes
30 pages
Data Structure Lab Manual Overview
No ratings yet
Data Structure Lab Manual Overview
79 pages
Understanding Linked List Data Structure
No ratings yet
Understanding Linked List Data Structure
17 pages
Questions Unit 2 Simple
No ratings yet
Questions Unit 2 Simple
7 pages
Data Structure Workbook for CS/IT GATE
No ratings yet
Data Structure Workbook for CS/IT GATE
58 pages
Stacks and Queues: Concepts and Operations
No ratings yet
Stacks and Queues: Concepts and Operations
247 pages
Linked List Operations Overview
No ratings yet
Linked List Operations Overview
8 pages
Data Structures Design Question Bank
No ratings yet
Data Structures Design Question Bank
6 pages
Sorting and Searching Assignments Guide
No ratings yet
Sorting and Searching Assignments Guide
8 pages
Singly Linked Lists in Python
No ratings yet
Singly Linked Lists in Python
10 pages
SLL vs DLL: Key Differences Explained
100% (3)
SLL vs DLL: Key Differences Explained
26 pages
Doubly Linked List Operations in C
No ratings yet
Doubly Linked List Operations in C
7 pages
C Algorithm for Doubly Linked List
No ratings yet
C Algorithm for Doubly Linked List
3 pages
Understanding Linked Lists in Data Structures
No ratings yet
Understanding Linked Lists in Data Structures
18 pages

Lab Programs-2

Uploaded by

Lab Programs-2

Uploaded by

Lab Programs

1. Write a program to implement the following using an array

def __init__(self, cap):

[Link] = [0] * [Link]

def push(self, x):

I SUBHASHINI [Link] in Computer Science Page 1

print("Top element:", [Link]())

print("Is stack empty: ", "Yes" if [Link]() else "No")

print("Is stack full: ", "Yes" if [Link]() else "No")

b) Full Implementations of Queue using Array

def __init__(self, capacity):

return [Link] == [Link]

def enqueue(self, x):

I SUBHASHINI [Link] in Computer Science Page 2

for i in range(1, [Link]):

I SUBHASHINI [Link] in Computer Science Page 3

I SUBHASHINI [Link] in Computer Science Page 4

3. write a program to evaluate a postfix expression using stack in python

if token[0].isdigit() or (len(token) > 1 and token[0] == '-'):

elif token == '-':

elif token == '*':

arr = ["2", "3", "1", "*", "+", "9", "-"]

I SUBHASHINI [Link] in Computer Science Page 5

Checks if the parentheses in an arithmetic expression are correctly nested.

Supports '()', '{}', and '[]'.

for char in expression:

elif char in ')]}':

expr1 = "(3 + 4 * {1 + [2]})"

print(f"The expression '{expr1}' is balanced.")

I SUBHASHINI [Link] in Computer Science Page 6

print(f"The expression '{expr2}' is balanced.")

print(f"The expression '{expr3}' is balanced.")

print(f"The expression '{expr3}' is not balanced.")

print(f"The expression '{expr4}' is not balanced.")

The expression '((a + b) * c' is not balanced.

The expression '([)]' is not balanced.

5) Write aprogram to find following using Recursion

a). Factorial of +ve integer

return (n * factorial(n - 1))

I SUBHASHINI [Link] in Computer Science Page 7

c). GCD of two positive intergers

Enter second number:20

I SUBHASHINI [Link] in Computer Science Page 8

def __init__(self, x):

def insertPos(head, pos, val):

for i in range(1, pos - 1):

I SUBHASHINI [Link] in Computer Science Page 9

head = insertPos(head, pos, val)

def __init__(self, data):

def push(self, new_data):

def deleteNode(self, key):

if (temp is not None):

I SUBHASHINI [Link] in Computer Science Page 10

while(temp is not None):

print (" %d" %([Link])),

print ("Created Linked List: ")

print ("Linked List after Deletion of 1:")

I SUBHASHINI [Link] in Computer Science Page 11

def __init__(self, data):

def push(self, new_data):

def search(self, x):

while current != None:

I SUBHASHINI [Link] in Computer Science Page 12

def __init__(self, data=None):

def append(self, data):

I SUBHASHINI [Link] in Computer Science Page 13

"""Sorts the linked list elements in ascending order."""

for value in values:

I SUBHASHINI [Link] in Computer Science Page 14

a) Insert an element at a specified position

def __init__(self, new_data):

def insertAtPos(head, pos, new_data):

if head is not None:

for i in range(1, pos - 1):

I SUBHASHINI [Link] in Computer Science Page 15

if [Link] is not None:

def init(self, cap):

def init(self, capacity):

def init(self, x):

def init(self, data):

def init(self, data):

def init(self, data=None):

def init(self, new_data):

def init(self, data):

def init(self, data):

def init(self, value):

def init(self, x):

def init(self, data):

def init(self, key):