Algorithmic Thinking with Python UCEST 105 university question paper and solution ( UCEST 105 answer key )

1.How do you use a decomposition strategy to design a menu-driven calculator that supports four basic arithmetic operators - addition, subtraction, multiplication, and division?

To design a menu-driven calculator using a decomposition strategy, you break the problem into smaller, manageable sub-tasks. Here's how to approach it step by step:

1. Problem Decomposition

Break down the calculator into smaller components based on the tasks:

Input Handling: Accept user input for numbers and operator selection.
Operation Implementation: Define how each arithmetic operation (addition, subtraction, multiplication, and division) will be performed.
Menu Management: Create a menu interface that allows users to select the desired operation.
Output Handling: Display the result of the operation.
Program Loop: Allow users to perform multiple operations by looping until they choose to exit.

2. Design Components

The key components of the calculator can be:

Input Functions: For accepting numbers and menu choices.
Operation Functions: Each arithmetic operation will be handled in a separate function.
Display/Output Functions: For displaying the menu and results.
Loop Control: A loop to repeatedly show the menu and process operations.

3. Implementation Plan

Define functions for each operation:

Addition: Add two numbers.
Subtraction: Subtract the second number from the first.
Multiplication: Multiply two numbers.
Division: Divide the first number by the second (ensure no division by zero).

4. Flow of the Program

Display a menu.
Take user input (choice of operation).
Accept two numbers.
Call the respective function for the operation.
Display the result.
Allow the user to repeat the process or exit.

# Simple Desktop Calculator in Python ( using if-elif)

while True

print("Select operation:")

print("1. Add")

print("2. Subtract")

print("3. Multiply")

print("4. Divide")

print("5.Exit")

choice = input("Enter choice (1/2/3/4/5): ")

if choice in ['1', '2', '3', '4']:

num1 = float(input("Enter first number: "))

num2 = float(input("Enter second number: "))

if choice == '1':

result = num1 + num2

print(f"{num1} + {num2} = {result}")

elif choice == '2':

result = num1 - num2

print(f"{num1} - {num2} = {result}")

elif choice == '3':

result = num1 * num2

print(f"{num1} * {num2} = {result}")

elif choice == '4':

if num2 != 0:

result = num1 / num2

print(f"{num1} / {num2} = {result}")

else:

print("Error! Division by zero.")

elif choice=='5':

exit()

else:

print("Invalid input. Please select a valid operation.")

2.A mad scientist wishes to make a chain out of plutonium and lead pieces. There is a problem, however. If the scientist places two pieces of plutonium next to each other, BOOM! The question is, in how many ways can the scientist safely construct a chain of length n?

This problem can be solved by thinking in terms of recursion and dynamic programming. The goal is to construct a chain of length $n$ using plutonium (P) and lead (L) pieces such that no two plutonium pieces are placed next to each other.

1. Problem Analysis

Each position in the chain can either be a plutonium (P) or a lead (L) piece.
We cannot place two plutonium pieces (PP) next to each other.
The length of the chain is $n$ , and we need to find the number of valid arrangements.

2. Recursive Insight

Let’s define $f(n)$ as the number of ways to construct a safe chain of length $n$ .

Consider the possibilities for the first piece:

If the first piece is a lead (L), then the rest of the chain (of length $n - 1) can be constructed in$ $f(n-1)$ ways.
If the first piece is a plutonium (P), then the second piece must be a lead (L) (because two plutonium pieces cannot be adjacent). So, the rest of the chain (of length $n - 2) can be constructed in$ $f (n - 2) ways.$

3. Recurrence Relation

Using the above observations, the recurrence relation for $f (n)$ can be written as:

f(n) = f(n-1) + f(n-2)

This is because:

$f(n-1)$ covers the cases where the chain starts with an L.
$f (n - 2) covers the cases where the chain starts with a P followed by an L.$

4. Base Cases

For $n = 1$ , the chain can only be either "P" or "L", so there are 2 ways: $f(1) = 2$
For $n = 2$ , the possible chains are "PL", "LP", and "LL" (but not "PP"), so there are 3 ways: $f(2) = 3$

5. Formula for General $n$

The formula is:

f(n) = f(n-1) + f(n-2)

with base cases $f(1) = 2$ and $f (2) = 3.$

This is similar to the Fibonacci sequence, but with different initial conditions.

6. Example

Let's manually compute $f(n)$ for small values of $n$ :

$f (1) = 2$
$f (2) = 3$
$f(3) = f(2) + f(1) = 3 + 2 = 5$
$f (4) = f (3) + f (2) = 5 + 3 = 8$
$f(5) = f(4) + f(3) = 8 + 5 = 13$

3.Write a case statement that will examine the value of flag and print one of the following messages, based on its value.

Flag value Message

1 Hot

2 Luke warm

3 Cold

Any other value Out of range

# Get the value of flag from the user

flag = int(input("Enter the value of flag: "))

# Match-case structure to check the value of flag and print the corresponding message

match flag:

case 1:

print("Hot")

case 2:

print("Luke warm")

case 3:

print("Cold")

case _:

print("Out of range")

Explanation:

match flag:: This starts the pattern matching based on the value of flag.

case 1:, case 2:, and case 3:: These handle the cases when flag is 1, 2, or 3, printing the respective messages.

case _:: The underscore _ acts as a wildcard to match any other values, so it catches all values that don’t match the specified cases and prints "Out of range".

4.Draw a flowchart to print the numbers that are divisible by 4 but not by 3 in a list of n positive numbers

5.Identify and rectify the problem with the following recursive definition to find the greatest common divisor of two positive integers.

ABC ( n , m )

if n == 2 return m

else return ABC(m , n mod m)

The given recursive definition of the function to find the greatest common divisor (GCD) has an issue:

Issue:

Incorrect Base Case: The condition if n == 2 return m is incorrect because the base case should occur when one of the numbers becomes zero, not when n == 2. In the Euclidean algorithm (used to find the GCD), the recursion should stop when one of the numbers becomes zero, and at that point, the GCD is the other number.
Correct Recursive Definition (Euclidean Algorithm):
The correct recursive definition for finding the GCD of two positive integers $n$ and $m$ using the Euclidean algorithm is:

Base Case: If $m == 0$ , return $n$ , because the GCD of $n$ and 0 is $n$ .

corrected code in Python

6.Write a recursive procedure to search for a key in a list of n integers

Recursive Linear Search (for an unsorted list):

For an unsorted list, linear search can be applied, which checks each element one by one.

Python Code for Linear Search:

def linear_search_recursive(arr, key, index):

# Base case: If we have checked all elements and not found the key

if index == len(arr):

return -1 # Key not found

# Check if the current element is the key

if arr[index] == key:

return index # Key found at current index

# Recursive call to check the next element

return linear_search_recursive(arr, key, index + 1)

# Example usage:

arr = [3, 7, 1, 9, 2, 8]

key = 9

result = linear_search_recursive(arr, key, 0)

if result != -1:

print(f"Key found at index {result}")

else:

print("Key not found")

Explanation:

Base Case: If index is equal to the length of the array, the search has gone through the entire list, and the key was not found.
Recursive Step: Check if the current element matches the key. If it does, return the current index; otherwise, recursively search in the rest of the list.

Recursive Binary Search (for a sorted list):

Binary search works by repeatedly dividing the search interval in half. If the key is smaller than the middle element, the search continues on the left half; otherwise, it continues on the right half.

Python Code for Binary Search:

def binary_search_recursive(arr, key, low, high):

# Base case: If the search space is invalid

if low > high:

return -1 # Key not found

# Calculate the middle index

mid = (low + high) // 2

# Check if the key is at the middle index

if arr[mid] == key:

return mid # Key found

elif arr[mid] > key:

# Key is in the left half

return binary_search_recursive(arr, key, low, mid - 1)

else:

# Key is in the right half

return binary_search_recursive(arr, key, mid + 1, high)

# Example usage:

arr = [1, 3, 5, 7, 9, 11, 13, 15]

key = 7

result = binary_search_recursive(arr, key, 0, len(arr) - 1)

if result != -1:

print(f"Key found at index {result}")

else:

print("Key not found")

Explanation:

Base Case: If low > high, the key is not in the list, so return -1.
Recursive Step: If the middle element is the key, return its index. Otherwise, recursively search in either the left or right half, depending on whether the key is smaller or larger than the middle element.

7.Compare and contrast greedy and dynamic programming strategies.

Greedy approach and Dynamic programming are two different algorithmic approaches that can be used to solve optimization problems. Here are the main differences between these two approaches:

Greedy Approach:

The greedy approach makes the best choice at each step with the hope of finding a global optimum solution.
It selects the locally optimal solution at each stage without considering the overall effect on the solution.
Greedy algorithms are usually simple, easy to implement, and efficient, but they may not always lead to the best solution.

Dynamic Programming:

Dynamic programming breaks down a problem into smaller subproblems and solves each subproblem only once, storing its solution.
It uses the results of solved subproblems to build up a solution to the larger problem.
Dynamic programming is typically used when the same subproblems are being solved multiple times, leading to inefficient recursive algorithms. By storing the results of subproblems, dynamic programming avoids redundant computations and can be more efficient.

8.Give the pseudocode for brute force technique to find the mode of elements in an array. Mode is the value that appears most frequently in the array

FUNCTION findMode(array):

DECLARE mode AS INTEGER

DECLARE maxCount AS INTEGER

// Initialize maxCount to 0

maxCount = 0

// Loop through each element in the array

FOR i FROM 0 TO LENGTH(array) - 1:

DECLARE count AS INTEGER

count = 0

// Compare the current element with every other element

FOR j FROM 0 TO LENGTH(array) - 1:

IF array[i] == array[j]:

count = count + 1 // Increment count for matching elements

// Update mode if the current count is greater than maxCount

IF count > maxCount:

maxCount = count

mode = array[i]

RETURN mode

Explanation of Brute Force Approach

Initialization:
- mode is declared to store the most frequently occurring element.
- maxCount is initialized to zero, which will track the highest frequency found.
Outer Loop:
- The outer loop iterates through each element in the array (i from 0 to the length of the array).
Inner Loop:
- For each element at index i, the inner loop compares it to every other element in the array (j from 0 to the length of the array).
- If the elements at index i and j are equal, the count is incremented.
Update Mode:
- After counting how many times the element at index i appears, it checks if this count is greater than maxCount.
- If it is, it updates maxCount and sets mode to the current element.
Return Mode:

After all elements have been processed, the function returns the mode.

9.Walk through the six problem-solving steps to find the largest number out of three numbers.

To find the largest number among three given numbers, we can follow a structured approach using six problem-solving steps. Here's how you can break down the process:

1. Problem Definition

Goal: Find the largest number among three given numbers.
Inputs: Three numbers (let's call them a, b, and c).
Output: The largest number among the three.
Constraints: Numbers can be positive, negative, or zero.

2. Algorithm Design

Plan the solution: Design an algorithm to compare the three numbers. We will:
1. Start by comparing a and b.
2. Compare the result with c to find the largest.

3.. Implementation

Translate the algorithm into code: In this step, we write the code in a programming language (Python in this case):

The program can be implemented using suitable programming language. Python Implementation i shown below.

# Get input values

a = float(input("Enter first number: "))

b = float(input("Enter second number: "))

c = float(input("Enter third number: "))

# Compare numbers to find the largest

if a >= b and a >= c:

largest = a

elif b >= a and b >= c:

largest = b

else:

largest = c

# Output the result

print(f"The largest number is {largest}")

4. Testing and Debugging

Test the implementation with different inputs: We now test the program with various input cases to ensure it works correctly.
Test cases:
- Input: a = 5, b = 7, c = 3 → Output should be 7
- Input: a = -1, b = -5, c = -3 → Output should be -1
- Input: a = 0, b = 0, c = 0 → Output should be 0
Debug any issues: If the program doesn't work as expected, we trace the logic to find and fix errors.

5. Optimization

Make the solution more efficient if needed: In this case, the algorithm is already efficient with a time complexity of O(1), so no further optimization is necessary.
For larger programs, you might optimize by reducing redundant comparisons or improving how input is handled.

6. Evaluation and Maintenance

Evaluate the solution: After testing and optimization, we check if the solution meets the requirements and handles all edge cases (e.g., equal numbers, negative numbers, etc.).

Maintenance: If we need to maintain or update the code (e.g., if we later want to find the largest of four or more numbers), we can adjust the code accordingly.

We should test the function with different sets of numbers to verify its correctness. Here are a few test cases:

Test Case 1: A = 5, B = 10, C = 3
- Expected Output: 10
Test Case 2: A = -1, B = -2, C = -3
- Expected Output: -1
Test Case 3: A = 7, B = 7, C = 5
- Expected Output: 7
Test Case 4: A = 0, B = 0, C = 0
- Expected Output: 0

Summary

By following these six problem-solving steps, we can systematically find the largest number among three given numbers. This structured approach ensures that we understand the problem clearly, devise a logical plan, and validate our solution with various test cases.

10a.Your professor has given you an assignment on “Algorithmic thinking” to be submitted by this Wednesday. How do you employ means-end analysis to devise a strategy for completing your assignment before the deadline?

Here’s a concise 5-point strategy using means-end analysis to complete your assignment on Algorithmic Thinking:

Define the Goal: Complete the assignment by understanding and explaining the core concepts of algorithmic thinking.
Identify Current Knowledge: Assess what you already know about the topic and what needs further research or clarification.
Break Into Subtasks: Divide the assignment into smaller tasks such as research, outlining, writing, and reviewing.
Plan with Deadlines: Set specific deadlines for each subtask (e.g., research by Monday, writing by Tuesday) to ensure completion by Wednesday.
Monitor and Adjust: Regularly check progress, adjust the plan as necessary, and ensure each part is aligned with the final goal.

This streamlined approach will guide you to complete the assignment efficiently before the deadline.

Here are two problems in student life that can be solved using a heuristic approach:

10b.Name two current problems in your life that might be solved through a heuristic approach. Explain why each of these problems can be solved using heuristics.

1. Managing Study Time for Multiple Subjects:

Problem: You have limited time to study for several subjects, and it's hard to know where to start or how much time to allocate to each subject.
Why Heuristics Help: The Pomodoro Technique is a time-management heuristic where you study in focused intervals (e.g., 25 minutes of work followed by a 5-minute break). This helps you break up study time into manageable chunks, keeping you focused and avoiding burnout. It’s an efficient way to ensure consistent progress in all subjects.

2. Choosing Which Assignment to Work on First:

Problem: You have multiple assignments due soon, and it’s hard to decide which one to tackle first.
Why Heuristics Help: The deadline-first heuristic involves prioritizing assignments by the closest due date. This allows you to focus on the most urgent tasks, ensuring that you complete assignments on time without overthinking which one to start with.

Using heuristics simplifies decision-making, helping you manage tasks more effectively in student life.

11a.Mr. Shyam, a history professor, would like to know the percentage increase in the population of our country per decade given the first decade and the last decade. Other given data include the population at the beginning of each decade. Draw a flowchart for determining the percentage increase in the population.

Percentage Increase=((Population at the beginning of the decade-Population at the end of the decade)/Population at the beginning of the decade)×100

Start

Input First Decade Population (P1)

Input Last Decade Population (P2)

Calculate Population Difference:

Population Difference = $P2 - P1$

Calculate Percentage Increase:

$\text{Percentage Increase} = \left( \frac{P2 - P1}{P1} \right) \times 100$

Output Percentage Increase

End

11b.Draw a flowchart to find the average mileage of a car in kilometers per litre after six fill-ups at petrol pumps. Input data include the number of litres of diesel, the starting odometer reading, and the odometer reading at each fillup

Start

Input Starting Odometer Reading (O_start)

Initialize Total Distance to 0 and Total Fuel to 0

Loop for Each Fill-up (1 to 6):

Input Odometer Reading at Fill-up (O_fill)
Input Litres of Diesel Used (L_fill)
Calculate Distance for this Fill-up: Distance = $O_{fill} - O_{start}$
Update Total Distance: Total Distance += Distance
Update Total Fuel: Total Fuel += $L_{fill}$
Set O_start = O_fill (for next iteration)

Calculate Average Mileage:

$\text{Average Mileage} = \frac{\text{Total Distance}}{\text{Total Fuel}}$

Output Average Mileage

End

12a.A standard science experiment is to drop a ball and see how high it bounces. Once the “bounciness” of the ball has been determined, the ratio gives a bounciness index. For example, if a ball dropped from a height of 10 feet bounces 6 feet high, the index is 0.6, and the total distance traveled by the ball is 16 feet after one bounce. If the ball were to continue bouncing, the distance after two bounces would be 10 ft + 6 ft + 6 ft + 3.6 ft = 25.6 ft. Note that the distance traveled for each successive bounce is the distance to the floor plus 0.6 of that distance as the ball comes back up. Write an algorithm that lets the user enter the initial height of the ball, bounciness index and the number of times the ball is allowed to continue bouncing. Output should be the total distance traveled by the ball.

Algorithm:

Start
Input Initial Height (H)
- (e.g., 10 feet)
Input Bounciness Index (B)
- (e.g., 0.6)
Input Number of Bounces (N)
- (e.g., 2)
Initialize Total Distance to 0
For each bounce (from 1 to N):
- Add current height (H) to Total Distance (falling distance)
  - Total Distance += $H$
- Calculate the bounce back height:
  - Bounce Back Height = $B \times H$
- Add bounce back height to Total Distance (rising distance)
  - Total Distance += Bounce Back Height
- Set H = Bounce Back Height for the next bounce
Output Total Distance
End

Example Calculation:

Let’s say:

Initial height = 10 feet
Bounciness index = 0.6
Number of bounces = 2
First Bounce:
- Fall: 10 feet
- Bounce back: $10 \times 0.6$ feet
- Total so far = $10 + 6 =$ feet
Second Bounce:
- Fall: 6 feet
- Bounce back: $6 \times 0.6 = 3.6$ feet
- Total so far = $16 + 6 + 3.6 = 25.6$ feet

Final Output: 25.6 feet.

12b. Light travels at 3 × 108 meters per second. A light-year is the distance a light beam travels in one year. Write an algorithm that inputs a large distance value (in meters) and displays it in light-years.

This algorithm computes the total distance for any number of bounces based on user input.

Here's a simple algorithm to convert meters to light-years:
Algorithm: Meters to Light-Years Conversion

Input distance in meters (m)
Define speed of light (c) = 3 × 10^8 meters/second
Define seconds in a year (s_per_year) = 60 × 60 × 24 × 365.25 ≈ 31,536,000
Calculate light-year (ly) = c × s_per_year ≈ 9.461 × 10^15 meters/light-year
Convert input distance to light-years (ly_distance) = m / ly
Output ly_distance

Python Implementation:

def meters_to_light_years(m):

c = 3e8 # speed of light (m/s)

s_per_year = 60 * 60 * 24 * 365.25 # seconds in a year

ly = c * s_per_year # meters per light-year

ly_distance = m / ly

return ly_distance

# Test the function

distance_in_meters = float(input("Enter distance in meters: "))

distance_in_light_years = meters_to_light_years(distance_in_meters)

print(f"{distance_in_meters} meters is equivalent to {distance_in_light_years:.6f} light-years.")

13a.Write a recursive function to find an array's minimum and maximum elements. Your method should return a tuple (a, b), where a is the minimum element and b is the maximum.

def find_min_max(arr):

"""

Recursive function to find minimum and maximum elements in an array.

Args:

arr (list): Input array.

Returns:

tuple: (min_element, max_element)

"""

# Base case: If array has only one element

if len(arr) == 1:

return (arr[0], arr[0])

# Base case: If array has two elements

if len(arr) == 2:

return (min(arr[0], arr[1]), max(arr[0], arr[1]))

# Recursive case: Divide array into two halves

mid = len(arr) // 2

left_min, left_max = find_min_max(arr[:mid])

right_min, right_max = find_min_max(arr[mid:])

# Combine results

return (min(left_min, right_min), max(left_max, right_max))

# Test the function

arr = [5, 2, 8, 12, 3, 1, 6, 4]

min_element, max_element = find_min_max(arr)

print(f"Minimum element: {min_element}")

print(f"Maximum element: {max_element}")

**Explanation:**

1. Define a recursive function `find_min_max` that takes an array `arr` as input.

2. Base cases:

* If `arr` has only one element, return it as both minimum and maximum.

* If `arr` has two elements, return the minimum and maximum of those two.

3. Recursive case:

* Divide `arr` into two halves using the midpoint `mid`.

* Recursively call `find_min_max` on both halves.

* Combine results by finding the minimum and maximum of the left and right halves.

4. Return the minimum and maximum elements as a tuple.

13b.Write a program to input a matrix and determine its type: lower triangular,upper triangular, or diagonal.

def is_lower_triangular(matrix):

# Check if all elements above the diagonal are zero

rows = len(matrix)

for i in range(rows):

for j in range(i + 1, rows): # Only look above the diagonal

if matrix[i][j] != 0:

return False

return True

def is_upper_triangular(matrix):

# Check if all elements below the diagonal are zero

rows = len(matrix)

for i in range(1, rows):

for j in range(i): # Only look below the diagonal

if matrix[i][j] != 0:

return False

return True

def is_diagonal(matrix):

# Check if both upper and lower conditions hold (it is both lower and upper triangular)

return is_lower_triangular(matrix) and is_upper_triangular(matrix)

# Function to determine the matrix type

def determine_matrix_type(matrix):

if is_diagonal(matrix):

return "Diagonal Matrix"

elif is_lower_triangular(matrix):

return "Lower Triangular Matrix"

elif is_upper_triangular(matrix):

return "Upper Triangular Matrix"

else:

return "Neither Lower, Upper, nor Diagonal"

# Input the matrix

def input_matrix():

n = int(input("Enter the size of the square matrix (n x n): "))

matrix = []

print("Enter the matrix elements row-wise:")

for i in range(n):

row = list(map(int, input().split()))

matrix.append(row)

return matrix

# Example usage

matrix = input_matrix()

matrix_type = determine_matrix_type(matrix)

print("The matrix is:", matrix_type)

using numpy

import numpy as np

def is_lower_triangular(matrix):

# Check if all elements above the main diagonal are zero

return np.all(np.triu(matrix, 1) == 0)

def is_upper_triangular(matrix):

# Check if all elements below the main diagonal are zero

return np.all(np.tril(matrix, -1) == 0)

def is_diagonal(matrix):

# A diagonal matrix is both upper and lower triangular

return is_lower_triangular(matrix) and is_upper_triangular(matrix)

# Function to determine the matrix type

def determine_matrix_type(matrix):

if is_diagonal(matrix):

return "Diagonal Matrix"

elif is_lower_triangular(matrix):

return "Lower Triangular Matrix"

elif is_upper_triangular(matrix):

return "Upper Triangular Matrix"

else:

return "Neither Lower, Upper, nor Diagonal"

# Input the matrix

def input_matrix():

n = int(input("Enter the size of the square matrix (n x n): "))

print(f"Enter the {n}x{n} matrix elements row-wise (space-separated):")

matrix = []

for _ in range(n):

row = list(map(int, input().split()))

matrix.append(row)

return np.array(matrix)

# Example usage

matrix = input_matrix()

matrix_type = determine_matrix_type(matrix)

print("The matrix is:", matrix_type)

14a.Write a program to read N words and display them in the increasing order of their lengths. The length of each word is also to be displayed

# Input the number of words

N = int(input("Enter the number of words: "))

# Input N words

words = []

for _ in range(N):

word = input("Enter a word: ")

words.append(word)

words.sort(key=len)

# Display the words along with their lengths

print("\nWords in increasing order of their lengths:")

for word in words:

print(f"{word}: {len(word)}")

14b.There are 500 light bulbs (numbered 1 to 500) arranged in a row. Initially, they are all OFF. Starting with bulb 2, all even numbered bulbs are turned ON. Next, starting with bulb 3, and visiting every third bulb, it is turned ON if it is OFF, and it is turned OFF if it is ON. This procedure is repeated for every fourth bulb, then every fifth bulb, and so on up to the 500th bulb. Devise an algorithm to determine which bulbs glow at the end of the above exercise.

To determine which bulbs remain ON at the end of the process, let's analyze the pattern of how bulbs are toggled.

Key Observations:

Initial State: All bulbs are initially OFF.
Toggle Process:
- A bulb is toggled whenever its number is divisible by $k$
Important Insight:
- Each bulb will be toggled once for each divisor it has. For example, bulb 12 will be toggled on rounds 1, 2, 3, 4, 6, and 12 (since these are its divisors).
- A bulb ends up ON only if it is toggled an odd number of times. This happens when the bulb has an odd number of divisors.
- Bulbs with an odd number of divisors are perfect squares because divisors generally come in pairs (e.g., divisors of 12 are (1, 12), (2, 6), (3, 4)), but for perfect squares, one divisor is repeated (e.g., divisors of 9 are (1, 9), (3, 3)).

Conclusion:

Only bulbs whose numbers are perfect squares will remain ON at the end.

Algorithm:

Iterate over the numbers from 1 to 500.
For each number, check if it is a perfect square.
If it is a perfect square, that bulb remains ON.

import math
def find_glowing_bulbs(N):
   glowing_bulbs = []

   # Check for perfect squares between 1 and N
   for i in range(1, N + 1):
       if math.isqrt(i) ** 2 == i: # Check if i is a perfect square
            glowing_bulbs.append(i)

   return glowing_bulbs

# Example usage
N = 500 # Number of bulbs
glowing_bulbs = find_glowing_bulbs(N)
print("The bulbs that are ON are at positions:")
print(glowing_bulbs)

15a.Studies show that the capacity of an empty human stomach is 1.5 litres on average. Give a greedy algorithm to output an efficient lunch menu maximizing the total nutritional value. The available items along with their nutritional values are tabulated below:

Recipe Available quantity Nutritional value

Cooked rice 2.5 cups 800 calories

Sambar 1.5 cups 140 calories

Potato curry 0.5 cup 50 calories

Fish fry 0.5 cup 200 calories

Buttermilk 1 cup 98 calories

Payasam 2 cups 300 calories

You may assume that 1 cup is equivalent to 250ml.

To maximize the total nutritional value for lunch while adhering to the constraint of the stomach capacity (1.5 liters or 1500 ml), we can approach this problem with a greedy algorithm. The greedy choice at each step is to select the item with the highest nutritional value per milliliter until the stomach is full (or nearly full).

Problem Breakdown:

Total Stomach Capacity: 1.5 liters = 1500 ml.
Item Data:
- Cooked Rice: 2.5 cups = 625 ml, 800 calories.
- Sambar: 1.5 cups = 375 ml, 140 calories.
- Potato Curry: 0.5 cup = 125 ml, 50 calories.
- Fish Fry: 0.5 cup = 125 ml, 200 calories.
- Buttermilk: 1 cup = 250 ml, 98 calories.
- Payasam: 2 cups = 500 ml, 300 calories.
Nutritional Value per ml (to make greedy decisions):
- Cooked Rice: $\frac{800}{625} \approx 1.28$ calories/ml.
- Sambar: $\frac{140}{375} \approx 0.37$ calories/ml.
- Potato Curry: $\frac{50}{125} = 0.4$ calories/ml.
- Fish Fry: $\frac{200}{125} = 1.6$ calories/ml.
- Buttermilk: $\frac{98}{250} = 0.392$ calories/ml.
- Payasam: $\frac{300}{500} = 0.6$ calories/ml.
Greedy Strategy:
- Sort the items by their nutritional value per milliliter in descending order.
- Select as much of the highest value item as possible without exceeding the stomach capacity.
- Move on to the next highest value item if more capacity is available.
- Continue until no more capacity is available.

Maximum Nutritional Value: 1399.0 calories

Chosen Items:

Fish Fry: 125.00 ml, 200.00 calories

Cooked Rice: 625.00 ml, 800.00 calories

Payasam: 500.00 ml, 300.00 calories

Potato Curry: 125.00 ml, 50.00 calories

Buttermilk: 125.00 ml, 49.00 calories

15b.How are recursion and dynamic programming (DP) related? Is it possible to construct a DP version for all recursive solutions?

Relationship Between Recursion and Dynamic Programming (DP):

Recursion and dynamic programming (DP) are closely related techniques used to solve problems that can be broken down into overlapping subproblems. The main connection between them is how they approach solving such problems:

Recursion:
- Recursion solves a problem by breaking it down into smaller instances of the same problem.
- A recursive function calls itself with different inputs until a base case is reached.
- However, recursive solutions often suffer from recomputing the same subproblems multiple times, leading to inefficiency.
Dynamic Programming (DP):
- Dynamic programming is an optimization technique used to improve the efficiency of recursive solutions.
- It avoids recomputing the same subproblems by storing results of already solved subproblems and reusing them when needed.
- DP can be viewed as an optimized version of recursion that uses either memoization (top-down) or tabulation (bottom-up) to achieve efficiency.

In short:

Recursion focuses on breaking down the problem, but it may solve the same subproblems multiple times.
DP solves the problem efficiently by storing intermediate results (subproblems) and using them to avoid redundant computations.

Is it Possible to Convert All Recursive Solutions to Dynamic Programming?

Yes, for problems with overlapping subproblems:
- If a recursive solution has overlapping subproblems and optimal substructure, then it is possible to convert it into a DP solution.
- Overlapping subproblems mean that the recursive solution solves the same subproblems multiple times. DP avoids this by storing results.
- Optimal substructure means that the solution to the larger problem can be composed of the optimal solutions of its subproblems.
Examples: Fibonacci, Knapsack, Longest Common Subsequence (LCS), Matrix Chain Multiplication, etc.
No, for problems without overlapping subproblems:
- Some recursive problems do not have overlapping subproblems, so DP will not provide any performance gain.
- Examples: Merge Sort, Binary Search, Tree Traversals, etc. These problems involve solving independent subproblems, so memoization or tabulation won't improve performance.

When to Use Dynamic Programming Instead of Recursion:

Use DP when you encounter overlapping subproblems in a recursive solution, as it will improve time efficiency.
Avoid DP for problems where subproblems are independent (like divide-and-conquer algorithms without overlapping subproblems), as recursion may be sufficient.

Summary:

Recursion solves problems by breaking them down into subproblems, but may recompute the same subproblems multiple times.
Dynamic programming optimizes recursion by storing intermediate results to avoid redundant work.
DP works well for problems with overlapping subproblems and optimal substructure, but not all recursive problems can or should be converted into DP.

16a.Write a Python program for a random walk simulation in a 2D grid starting from the origin (0, 0). At each step, randomly move up, down, left, or right.Print the final position after 10 steps.

import random

# Define a function for the random walk simulation

def random_walk_2d(steps):

# Initialize position at origin (0, 0)

x, y = 0, 0

# Possible directions (up, down, left, right)

directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

# Simulate random walk

for _ in range(steps):

dx, dy = random.choice(directions)

x += dx

y += dy

return x, y

# Number of steps

steps = 10

# Perform the random walk

final_position = random_walk_2d(steps)

# Print the final position after 10 steps

print(f"Final position after {steps} steps: {final_position}")

16b.Use divide and conquer to find the majority element in an array, where the majority element appears more than n/2 times. Divide the array into two halves, find the majority element in each half, and combine the results to identify if there is a majority element in the entire array.

To find the majority element in an array (i.e., the element that appears more than $n/2$ times) using the Divide and Conquer approach, we can break the problem down as follows:

Strategy:

Divide: Recursively divide the array into two halves.
Conquer: Find the majority element in each half of the array.
Combine: Combine the results from the two halves to determine the majority element in the entire array.

Key Insight:

If both halves agree on the majority element, then that element is the majority in the entire array.
If they differ, count how many times each of the two majority candidates appears in the combined array and declare the one that appears more frequently as the majority element (if it qualifies by appearing more than $n/2$ times).

Algorithm:

Base Case: If the array has only one element, that element is trivially the majority.
Recursive Case: Recursively determine the majority element in the left and right halves of the array.
Combine: If the left and right halves agree on the majority element, return that. Otherwise, count the occurrences of the two candidates in the entire array and return the one that appears more than $n/2$ times (if any).

def find_majority(arr):

def majority_element_rec(lo, hi):

# Base case: if the subarray has only one element, return that element

if lo == hi:

return arr[lo]

# Divide the array into two halves

mid = (lo + hi) // 2

# Recursively find majority elements in the left and right halves

left_majority = majority_element_rec(lo, mid)

right_majority = majority_element_rec(mid + 1, hi)

# If both halves agree on the majority element, return it

if left_majority == right_majority:

return left_majority

# Otherwise, count occurrences of both left_majority and right_majority in the whole range

left_count = sum(1 for i in range(lo, hi + 1) if arr[i] == left_majority)

right_count = sum(1 for i in range(lo, hi + 1) if arr[i] == right_majority)

# Return the one that appears more frequently

return left_majority if left_count > right_count else right_majority

# Get the majority element from the full array

candidate = majority_element_rec(0, len(arr) - 1)

# Verify if the candidate is indeed a majority element

count = sum(1 for x in arr if x == candidate)

if count > len(arr) // 2:

return candidate

else:

return None # No majority element found

# Example usage

arr = [2, 2, 1, 1, 1,1,1,2, 2]

majority = find_majority(arr)

if majority is not None:

print(f"The majority element is: {majority}")

else:

print("No majority element found")