MANAV RACHNA UNIVERSITY
SCHOOL OF ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE & TECHNOLOGY
"PRACTICE 29AUG”
SEMESTER 3RD NAME: M.SATYA SAI
COURSE NAME Analysis and Design of COURSE CODE CSH204B-P
Algorithms
PROGRAM B.Tech CSTI ROLL NO: 2K24CSUN01325
QUESTIONS
CO BLOOM'S
Q.NO.
ADDRESSED LEVEL
Write a Program to Sort a given set of
elements using bubble sort method and
determine the time required to sort the
elements.
Derive the time complexity of Bubble Sort
in the following cases:
o Best case (already sorted
list).
1 CO1 BT3
o Worst case (list sorted in
reverse order).
o Average case.
Measure Execution Time
o A sorted array.
o A reverse-sorted array.
o A randomly shuffled array.
ANS:
CODE:
import time
import random
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False # Optimization for best case
*******
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
def measure_time(arr, label):
start = time.time()
bubble_sort(arr.copy()) # Use copy to preserve original
end = time.time()
print(f"{label} - Time taken: {end - start:.6f} seconds")
size = 1000 # You can increase this for deeper analysis
sorted_array = list(range(size))
reverse_sorted_array = list(range(size, 0, -1))
random_array = sorted_array.copy()
random.shuffle(random_array)
print(" Measuring Bubble Sort Execution Time:\n")
measure_time(sorted_array, " Sorted Array")
measure_time(reverse_sorted_array, "Reverse-Sorted Array")
measure_time(random_array, "Random Array")
OUTPUT:
CO BLOOM'S
Q.NO. QUESTIONS
ADDRESSED LEVEL
Write recursive and iterative
implementations of computing the n-th
Fibonacci number.
Compare their execution times for
1 CO1 BT3
n=10,20,30,40
Discuss which implementation is more
efficient and why.
Ans:
INPUT:
import time
# Recursive implementation of Fibonacci
def fib_recursive(n):
*******
if n <= 1:
return n
return fib_recursive(n - 1) + fib_recursive(n - 2)
def fib_iterative(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
def main():
test_cases = [10, 20, 30, 40]
print("Comparing Recursive and Iterative Fibonacci Implementations:\n")
for n in test_cases:
print(f"n = {n}:")
start_rec = time.perf_counter()
rec_result = fib_recursive(n)
end_rec = time.perf_counter()
duration_rec = end_rec - start_rec
start_itr = time.perf_counter()
itr_result = fib_iterative(n)
end_itr = time.perf_counter()
duration_itr = end_itr - start_itr
print(f" Recursive: {rec_result}, Time: {duration_rec:.6f} seconds")
print(f" Iterative: {itr_result}, Time: {duration_itr:.6f} seconds\n")
print("Discussion:")
print("The iterative implementation is significantly more efficient than the recursive one.")
print("The recursive approach has exponential time complexity (O(2^n)),")
print("because it recomputes the same subproblems many times.")
print("The iterative approach has linear time complexity (O(n)),")
print("as it computes each Fibonacci number only once in a loop.")
print("For large n, the recursive method becomes impractically slow, while the iterative
remains fast.")
if __name__ == "__main__":
main()
OUTPUT:
*******
Manav Rachna University
Lab Assignment 04
Subject: Analysis and Design of Algorithms Subject Code: CSH326
Semester: 3
Learning Objective: The objective is to gain a practical understanding of recursion's applicability
to linked lists.
Learning Outcome: Students will explore and implement recursive algorithms for common linked
list operations, including traversing, searching, modifying, and creating linked lists.
All programs should be using recursion
1.Program to Print Linked List Forward and Reverse using recursion
2.Program to Insert a Node at the Beginning and End .
3.Program to merge two sorted list .
4.Program to find nth node from the end in a linked list.
Q1:
INPUT:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def print_forward(node):
if node is None:
return
print(node.data, end=' ')
print_forward(node.next)
def print_reverse(node):
if node is None:
return
print_reverse(node.next)
print(node.data, end=' ')
*******
# Example usage:
if __name__ == "__main__":
# Create linked list: 1 -> 2 -> 3 -> 4 -> 5
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
print("Linked List Forward:")
print_forward(head)
print("\nLinked List Reverse:")
print_reverse(head)
print()
OUTPUT:
Q2:
INPUT:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert_at_beginning(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def insert_at_end(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
last = self.head
while last.next:
last = last.next
last.next = new_node
def print_list(self):
*******
current = self.head
while current:
print(current.data, end=' ')
current = current.next
print()
if __name__ == "__main__":
ll = LinkedList()
ll.insert_at_end(3)
ll.insert_at_beginning(2)
ll.insert_at_beginning(1)
ll.insert_at_end(4)
ll.insert_at_end(5)
print("Linked List after insertions:")
ll.print_list()
OUTPUT:
Q3:
INPUT:
# Program to merge two sorted lists
def merge_sorted_lists(list1, list2):
merged = []
i, j = 0, 0
# Traverse both lists and append smaller element to merged
while i < len(list1) and j < len(list2):
if list1[i] < list2[j]:
merged.append(list1[i])
i += 1
else:
merged.append(list2[j])
j += 1
# Append remaining elements (if any)
while i < len(list1):
merged.append(list1[i])
i += 1
while j < len(list2):
merged.append(list2[j])
j += 1
return merged
# Example usage:
if __name__ == "__main__":
a = [1, 3, 5, 7]
b = [2, 4, 6, 8, 10]
*******
result = merge_sorted_lists(a, b)
print("Merged List:", result)
OUTPUT:
Q4:
INPUT:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def nth_from_end(head, n):
main_ptr = head
ref_ptr = head
count = 0
while count < n:
if ref_ptr is None:
return None # n is greater than the number of nodes
ref_ptr = ref_ptr.next
count += 1
while ref_ptr:
main_ptr = main_ptr.next
ref_ptr = ref_ptr.next
return main_ptr.data if main_ptr else None
# Example usage:
if __name__ == "__main__":
# Create linked list: 10 -> 20 -> 30 -> 40 -> 50
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
head.next.next.next = Node(40)
head.next.next.next.next = Node(50)
*******
n=2
result = nth_from_end(head, n)
if result is not None:
print(f"{n}th node from the end is: {result}")
else:
print(f"List has fewer than {n} nodes.")
OUTPUT:
*******
