Job Saarnee

# Unit 5Long answer question of Python Programming

Q1 Explain iterator. Write a program to demonstrate the tower of Hanoi using function. [2019-20]
OR
Solve the Tower of Hanoi problem for n=38k and show all the steps. [21-22]

Solution:

An iterator is an object that enables us to traverse a container or data structure such as a list, tuple, dictionary, or set. It allows us to access elements of the container one at a time, without exposing its underlying implementation. Iterators are used to iterate over a sequence of values and perform operations on them.
In Python, an iterator is an object that implements the iterator protocol, which consists of the __iter__() and __next__() methods. The __iter__() method returns the iterator object itself, and the __next__() method returns the next value from the iterator.
Here is an example program to demonstrate the tower of Hanoi using a recursive function:
def tower_of_hanoi(n, from_rod, to_rod, aux_rod):
if n == 1:
print(f”Move disk 1 from {from_rod} to {to_rod}”)
return
tower_of_hanoi(n – 1, from_rod, aux_rod, to_rod)
print(f”Move disk {n} from {from_rod} to {to_rod}”)
tower_of_hanoi(n – 1, aux_rod, to_rod, from_rod)
# Sample usage
tower_of_hanoi(3, ‘A’, ‘C’, ‘B’)
In the above code, we define a function tower_of_hanoi() that takes four parameters: the number of disks n, the source rod from_rod, the destination rod to_rod, and the auxiliary rod aux_rod.
The function first checks if there is only one disk. If so, it simply moves it from the source rod to the destination rod. If there are more than one disk, it calls the tower_of_hanoi() function recursively on the subproblem of moving n-1 disks from the source rod to the auxiliary rod, then it moves the n-th disk from the source rod to the destination rod, and finally calls the tower_of_hanoi() function recursively on the subproblem of moving n-1 disks from the auxiliary rod to the destination rod.
When we call the function tower_of_hanoi(3, ‘A’, ‘C’, ‘B’), it prints the steps required to move three disks from rod A to rod C using rod B as an auxiliary rod:
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Q2 Discuss Sorting & Merging. Explain different types of sorting with example. Write a Python Program for Sieve of Eratosthenes. . [ 2019-20]
OR
Explain the term merge list and merge sorting in python programming?

Solution:

Sorting is the process of arranging data in a particular order, typically in ascending or descending order. Merging is the process of combining two or more sorted arrays or lists into a single sorted list.
There are many different algorithms for sorting data, and each has its own advantages and disadvantages in terms of time complexity, space complexity, and stability. Some of the most common sorting algorithms are:
Bubble Sort: Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The algorithm ends when no more swaps are needed. Here’s an example implementation in Python:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
Selection Sort: Selection sort is a simple sorting algorithm that repeatedly selects the smallest element from the unsorted portion of the list and swaps it with the leftmost unsorted element. Here’s an example implementation in Python:
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
Insertion Sort: Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. Here’s an example implementation in Python:
def insertion_sort(arr):
n = len(arr)
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
return arr
Merge Sort: Merge sort is a divide-and-conquer algorithm that works by recursively dividing the input array into smaller subarrays, sorting them, and then merging them back together. Here’s an example implementation in Python:
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr)//2
left_arr = arr[:mid]
right_arr = arr[mid:]
merge_sort(left_arr)
merge_sort(right_arr)
i = j = k = 0
while i < len(left_arr) and j < len(right_arr):
if left_arr[i] < right_arr[j]:
arr[k] = left_arr[i]
i += 1
else:
arr[k] = right_arr[j]
j += 1
k += 1
while i < len(left_arr):
arr[k] = left_arr[i]
i += 1
k += 1
while j < len(right_arr):
arr[k] = right_arr[j]
j += 1
k += 1
return arr
Quick Sort: Quick sort is a divide-and-conquer algorithm that works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. Here’s an example implementation in Python:
def quick_sort(arr):
if len(arr) <= 1:
return arr
The Sieve of Eratosthenes is an algorithm for finding all the prime numbers in a range of numbers up to a given limit. The algorithm works by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the multiples of 2. Here’s an example implementation in Python:
def sieve_of_eratosthenes(n):
# Create a boolean array “prime[0..n]” and initialize
# all entries it as true. A value in prime[i] will
# finally be false if i is Not a prime, else true.
prime = [True for i in range(n+1)]
p = 2
while p*p <= n:
# If prime[p] is not changed, then it is a prime
if prime[p] == True:
# Update all multiples of p
for i in range(p*p, n+1, p):
prime[i] = False
p += 1
# Print all prime numbers
for p in range(2, n+1):
if prime[p]:
print(p, end=” “)
This function takes a single argument n, which is the upper limit of the range of numbers to search for primes. The function creates a boolean array prime of length n+1, initializes all entries to True, and then iterates through the array starting at p=2. For each prime number p, the function marks all multiples of p as composite by setting their corresponding entries in prime to False. Finally, the function prints all prime numbers by iterating through the array and printing the indices of all True entries (excluding 0 and 1).

Q3  Discuss and differentiate Iterators & Recursion. Write a program for Recursive Fibonacci series? [ 2019-20]

Q4  Describe the differences between a linear search and a binary search? [2020-2021]

Q5  Write a python program for selection sorting algorithm? [2021-22]

Q6 Write a recursive function in python BinarySearch(Arr, L, R, X) to search the given element X, to be searched in given list Arr having R elements , where L represent lower bound and represents the upper bound? [2021-22]

Shopping Cart