* ( \ ‘STUDENT ASSIST CELL an intiative of KSU CET unit PREPARED BY: ROHAN ROBIN @@ KSU CET UNIT ‘COLLEGE OF ENGINEERING TRIVANDRUMMODEL QUESTION PAPER ‘APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY FIRST SEMESTER B. TECH DEGREE EXAMINATION, DECEMBER 2024 Course Code: UCEST105 ‘Course Name: Algorithmic Thinking with Python ‘Max. Marks: 60 Duration: 2 hours 30 minutes PARTA Answer all questions. Each question carries 3 marks CO] Marks How do you use a decomposition strategy to design a menu-driven calculator | 1 | @) that supports four basic arithmetic operators - addition, subtraction, multiplication, and division? ‘A mad scientist wishes to make a chain out of plutonium and lead pieces. | 4 |G) 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 ? Write a ease statement that willexainiie thé value of flag and print one ofthe | 3 | @) following messages, based on its value. Flag value Message 1 Hot 2 Luke warm 3 Cold Any other value Out of range Draw a flowchart to print the numbers that are divisible by 4 butnot by3ina| 3 |G) list of m positive numbers, Identify and rectify the problem with the following recursive definition to find | 4 | (3) the greatest common divisor of two positive integers ABC(n,m) ifm =2 return m else return ABC(m , n mod m) Write a recursive procedure to search for a key in a list of m integers. 478 ‘Compare and contrast greedy and dynamic programming strategies. 37 @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. QB) PARTB ‘Answer any one full question from each module. Each question carries 9 marks ‘Module 1 Walk through the six problem-solving steps to find the largest number out of three numbers. oy a) 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? 6) Dy ‘Name two current problems in your life that might be solved through @ heuristic approach. Explain why each of these problems can be solved using heuristics, @ ‘Module 2 mn a) 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. 6 b) 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. @ 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 ff. 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. (6)6 Light travels at 3 x 10° 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. QB) ‘Module 3 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, 6) ») Write a program to input a matrix and determine its type: lower triangular, upper triangular, or diagonal, @ 14 [ay Write a program to read V words and display them in the increasing order of their lengths. The length of each word is also to be displayed, 6 b) There are 500 Tight bulbs (numbered 1 to 500) arranged in a row. Initially, they are all OFF. Starting with bulb 2yall even numbered bulbs are tured ON. Next, starting with bulb 3, and visiting every third bulb, itis turned ON if it is OFF, and it is tumed 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. i) Module 4 Studies show that the capacity of an empty human stomach is 1.5 Titres on average, Give a greedy algorithm to output an efficient Iunch_menu maximizing the total nutritional value. The available items along with their nutritional values are tabulated below: Recipe | Available | Nutritional quantity | value Cooked rice} 2.5 cups | 800 calories Sambar | 1.5 cups | 140 calories Potato curry }0.5 cup _| 50 calories (6)Fish fry | [Link] | 200 calories Buttermilk} 1 cup 98 calories Payasam | 2 cups 300 calories ‘You may assume that I cup is equivalent to 250ml. ) | How are recursion and dynamic programming (DP) related? Is it possible to | 2 | (3) construct a DP version for all recursive solutions? 16 | a) | Write a Python program for a random walk simulation ina 2D grid starting | 3 | (4) from the origin (0, 0). At each step, randomly move up, down, left, or right. Print the final position after 10 steps! ') | Use divide and conquer to find'the miajority element in an array, where the | 2 (3) majority element appears more thai 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.1. Using a decomposition strategy to design a menu-driven calculator involves breaking the task into smaller ‘components: © Display Menu: A function to list operations (addition, subtraction, multiplication, division, exit), ‘© Input Handling: Functions to get and validate user choices and numbers. © Arithmetic Operations: Separate functions for each operation (e.g., add, subtract, multiply, divide). © Control Flow: A loop to display the menu, process input, perform the selected operation, and allow exit. Each components tested individually, then integrated for a modular, maintainable program. 2. The chain can end with ether: + Alead piece (sate to add any piece next) + A plutonium piece (must be followed by a lead piece) Recurrence Relation + PinjeP(n-1)+P(n-2) © P{n-1): Adding a lead piece atthe end, © P(n-2) : Adding a plutonium piace (which rGuires a lead piece before it), Base Cases: * P(t)= 2(Chain can be or", © P(2)=3 (Chains: "LL", "LP", "PL", 3, flag = int(input("Enter the flag value: ")) itflag print(Hot’) eli fa Print(Luke warm’) elif lag == 3: print(Cols") else: print’Out of range")5. The base case if (n ==2 return m) is incorrect. In the Euclidean algorithm for finding the greatest common divisor (GOD), the base case occurs when n == 0. At this point, the GCD is m, because any number's GCD with 0 is the umber itself 6. def recursive_search(arr,n, key): # Base case: if the list is empty, retum False retum False # Check if the last element matches the key itanin- 1} key: retum True # Recursive case: search in the rest of the list return recursive_searcharr, n= 1, key) 7 Feature Greedy Algorithm Dynamic Programming ‘Approach __-Makes a series of choices, picking the Solves subproblems and stores results to build up the 7 locally optimal solution ‘optimal solution Does not guarantee optimal solutions for Guarantees optimal solutions when the problem has Optimality all problems ‘optimal substructure Problem ‘Works well for problems with the greedy Works well for problems with overlapping subproblems Suitability choice property ‘and optimal substructure Complexity Usually more efficient, O(n log n) or O(n) Generally slower, O(a#) or higherFeature Greedy Algorithm Dynamic Programming ‘Typically requires more memory to store intermediate Memory Usage Generally uses less memory a Examples Activity selection, Huffman coding, MSTs _Knapsack problem, LCS, shortest path problems 8. —_Stop-t. Initialize an array “arf length “n Stop-2. Create a variable "max_count’ and sett 0. Step-3. Create a variable “"mode_value’ and set ito “nul or an intial value indicating no mode. Step-4 For each element "xn the array “ar [Link] “count 10 0 ‘tep-6. For each element’y” in the array ‘ar Stop-7. It increment ‘count’ by 4 ‘Step-6. If count > max_count’, set "max_count’f@ ‘cour and ‘mode_value’ to x’ Step-9, Return ‘mode_value’ PART: 9. To find the largest number out of three numbers, follow these six stops: ‘Step-1: Understand the Problem: You need to find the largest number from three given numbers, say a, b, and c. Step-2: Analyse the Problem: Compare the numbers pair by pair. ‘Step-3: Break Down the Problem: Compare a and b, then compare the larger value with c. Step-4: Devise a Plan: © Compare a and b to find the larger. © Then, compare the larger value with c ‘Step-5: Implement the Plan (Pseudocode) largest_of_ab = max(a, b) largest = max(largest_of_ab, c) return largest‘Stop-6 : Review and Reflect ‘The solution works in constant time O(1) and space O(1). 1042). ‘Step 1: Define the Goal (End) + Goal: Submit the completed assignment on "Algorithmic thinking” by Wednesday. ‘Step 2: Identify the Current Situation (Means) ‘Current Situation: You need to work on and complete the assignment. Depending on its complexity, this ‘might involve research, writing, and structuring the content, ‘Stop 3: Identify the Gaps + Gaps: © Ifyou haven't started the assignment yét, the gap is time management and planning. © If you've started but need to improve the guilty of your work, the gap might involve revising, clarifying concepts, or organizing the gontent better ‘Step 4: Formulate Subgoals (Intermediate Ends) * Break down the main goal into smaller tasks? 1, Understand the Assignment Requirements: Review the assignment prompt and ensure you know what's expected 2. Research: Gather materials or references on algorithmic thinking 3. Outline: Create an outine forthe assignment. 4, Write the First Draft: Write the content based on the outline, 5. Revise and Proofread: Edit the draft to ensure clarity, coherence, and accuracy. 6. Final Review: Double-check that all requirements are met. ‘Stop 5: Plan the Actions * Action Plan: 41. Today (Monday): Understand the requirements and gather research materials, 2. Tomorrow (Tuesday): Draft the assignment and organize the sections. 3. Wednesday Morning: Revise, prootread, and finalize the assignment.4, Wednesday Afternoon: Submit the assignment before the deadline. ‘Step 6: Take Action ‘+ Begin executing the plan step by step. Track your progress and make adjustments if needed to stay on schedule. 1010) 1. Time Management for Assignments and Exams ‘© Problem: Managing deadlines for multiple assignments and preparing for exams within a limited time, ‘+ Why Heuristic Approach Works: A heuristic approach can be applied here by prioritizing tasks based on Urgency and importance, using strategies like the 80/20 rule (focusing on the 20% of tasks that will give 80% of the results) or time-blocking (allocating specific time slots for different tasks). These shortcuts help, ‘make decisions without having to consider every detail, optimizing productivity without perfect accuracy. 2. Choosing the Best Study Techniques ‘+ Problem: Deciding which study methods or resources (¢.g., online courses, textbooks, group study) will be ‘most effective for understanding dificult subjects. ‘© Why Heuristic Approach Works: In this case, heuristics lke the trial-and-error method or relying on previous experience (e.g., which methods worked best in past exams) can be used. For example, if studying with flashcards has worked well for memorizing information before, using that technique again is a practical, effective shortcut without fully analyzing every possible study method.11a) Pairs Processed Calculate Percentage Inteas (Next Population “Current Population / Current Population) * 100 Display All Percentage Increases 1b) / \ Litres of Dideel for Each Fill: ‘ahd Odometer Readings” Galealate Average Miloade: ‘Total Distance) Total Diesel tkem/)12a) Algorithm Steps: Step 1 Stop 2: Step 3: Step 4: Step 5: 12) Steps: Input the folowing values: Initia! height ofthe ball (H). Bounciness index (B), where 0 1,000,000):§ Display in scientific notation with 2 decimal places: © Otherwise: § Display with 4 decimal places © Append "light-years" to the result 13a) def find_min_max(art) 's both min and max. # Base Case: If the array has only one element, iflen(ar) == 4 return (ar(0},arfo)) # Base Case: I the array has two elements, return min and max directly iften(arr) == 2: retuin (min(ar{0},arr{1)), max(ar{O}, art), # Recursive Case: Divide the array into two halves mid = lenfart) 12 left_min_max = find_min_max(arr{:mid]) # Min and Max from the left halt Fight_min_max = find_min_max(art{mic]) # Min and Max from the right half # Combine results: Find overall min and max overall_mi ‘min(left_min_max(0},right_min_max{o)) overall_max = max(lefmin_maxft}, right_min_max{1]) retum (overall_min, overall_max) Test the function am =[3,1,4,1,5,9,2,6,5,3]result = ind_min_max(arr) print(’Minimum:”, resul{0}, "Maximum, resut(1}) 13b.) 4 Input the matrix from the user det input_matrixrows, col): print("Enter the matrix row by row") rmatiic= for in range(rows): row =1) print(*Enter row {+4} (space-separated):”) row_input = input) elements = row [Link]() # Split the input string into list elements for element in elements: [Link](element)) # Convert each element to an integer if len(row) '= cots: print("Error: Row {+1} must have exactly {cols} numbers.") return None matrix-append(row) return matrix + Check if the matrixis diagonal det is_diagonal(matrix,n): for iin range(n): for jin range(n) If Le | and matixiy != 0:retun False retum True # Check if the matrix is upper triangular dof is_upper_tiangular(matrix, n): {orn range): {or in range(i): # Elements below the main diagonal if mati '= 0: return False retumn True # Check the matrix is lower triangular del is_lower_trangular(matrx,n) for iin range: {or in range(+ 1, n): # Elements above the fii diagonal” if mati '= 0: retum False retumn True # Main program print("This program checks if a matrix is diagonal, upper triangular, of lower triangular”) rows = int(input("Enter the number of rows: ")) Cols = int(input("Enter the number of columns: ")) if rows I= cols print(The matrix is not square, so it cannot be triangular or diagonal")14a) =1ows # Since it's square, rows and cols are the same matrix Input_matrix(tows, cols) it matrix itis_diagonal(matrix, n) print("The matrix is diagonal") lf is_upper_tiangular(matrx, n: print("The matrix is upper triangular li is_lower_triangular(matrix, n) print("The matrix is lower triangular.”) else: print("The matrix is neither diagonal, upper triangular, nor lower triangular") det sort_words_by_length() 4# Read number of words N= Int(input(‘Enter the number of words’) # Read the words from the user words for _ in range(N): word = input("Enter a word: ") [Link](word) 4# Sort the words by their lengths [Link]{key=ten) # Display the words and their lengths in increasing order of length print("inWords in increasing order of length")for word in words: print word) - Length: len(word)}") # Call the function sor words_by_length() 140) 1, Initial State: All bulbs are OFF. 2. Process: ©. Stop 4: Stating with bub 2, every even-numbered bulb i tuned ON. © Stop 2: Starting with bulb 3, every third bulb is toggled (Le., tuned ON ifit's OFF and OFF if it's ON). (© Step 3: This continues for each successive step, toggling every fourth bulb, every fith bulb, and 's0 on until the 500th bulb Each bulb is toggled as many times as the nufhiber of divisors it has. For example: (© Bulb 6 will be toggled in steps 2, 3, and 6 because 6 is divisible by 2, 3, and 6. © Bulb 12 willbe toggled in steps 2, 3, 4, Byand 12. '® A bulb will end up ON if itis toggled an odd number of times and OFF it itis toggled an even number of times. ‘© A bulb is toggled an odd number of times if and only if its number is not a perfect square. ‘© Thus, the bulbs that will be ON at the end are those whose numbers are not perfect squares Agorthm: 1. Identify all perfect squares up to 500. Output the bulb numbers corresponding to perfect squares. 15a) 1. Define food items with their quantities and nutional values 2, Convert the quantities to milters, 3, Calculate calories per mililiter for each food item. 4, Sort the food items by calories per milter in descending order. 5. Initialize total calories, remaining capacity '500 mi 6, For each food item in sorted list: a. If remaining _capacity > 0:{Ifthe item fits completely iis volume <= remaining_capacity), take it fully. li, Otherwise, take as much as possible. li, Add the corresponding calories to total calories. iv. Update remaining_capacity accordingly. 7. When remaining_capacity is 0 or all tems are considered, return total calories Selected Recipes: + Fish fry: 125.0 mi (100.00 calories) - Payasam: 500.0 ml (250.00 calories) = Cooked rice: 875.0 ml (280.00 calories) Total Calories: 630.00 15b) Relationship Between Recursion and Dynamic Programming (DF 1. Recursior © Solves a problem by breaking it down into smaller subproblems, © Each subproblem is solved independently, often leading to redundant computations when the ‘same subproblem is encountered multiple times. © Used when the problem has a recursive structure (e.9,, Fibonacci sequence, divide-and- ‘conquer problems), 2. Dynamic Programming (DP): © Optimizes recursive solutions by avoiding redundant computations. © Stores the results of subproblems (in a table or cache) so that each subproblem is solved only © Used when the problem has both overlapping subproblems and optimal substructure Not ll recursive solutions can be converted to DP. A recursive solution can be converted to DP if and only iit has these properties: 1. Overlapping subproblems - The same subproblems must be encountered multiple times. if each ‘recursive call works on unique subproblems, DP won't provide any benefit, 2. Optimal substructure - The optimal solution tothe larger problem must be constructible from optimal solutions of its subproblems.Examples where DP conversion typically doesnt work: © Tree traversal algorithms (each node is visited once) ‘© Divide and conquer algorithms like Mergesort (subproblems don't overlap) 168) import random def random_walk_2d(steps) # Starting postion atthe origin xy=0,0 4 Perform the random walk for _in range(steps): move = [Link]({up\ ‘dow, lett right!) wn yat STUDENT ASSIST CELL elif move = "left x=1 ‘right: retun x,y # Number of steps steps = 10 # Perform the random walk and print the result final_position = random_walk_2d(steps)ptint(*Final position after {steps} stops: (final_position)") 16) det majorty_element{nums): det find_majority(lo, hi): # Base case: one element ito retumn nums(o} # Divide: Split the array into two halves mid = (lo + hi 2 left_majorty = find_majority(lo, mid) Fight_majority = find_majority(mid +1, ti) # Combine: Ifthe two halves agree, return the common majority IF et_majority == right_majonty: retum lef_majority # Count occurrences in the current range and pick the majority left_count = nums{la:hi+ 1].count(le_majority) right count wums|lochi + 1countright_ majority) return left_majority if left_count > right count else right_majority # Find the majority element Candidate = find_majoriy(0, len{nums) - 1) # Verity the candidate return candidate if [Link](candidate) > len(nums) //2 else None‘Test the function ums = (3, 3,4,2,4, 4,2, 4,4] result = majority_element{nums) print("Majorty element: {result if result else ‘None}") MN _—"