You are given an array A, which stores n non-negative integers. Design an efficient divide-and-conquer algorithm that accepts A and n as inputs and returns the index of the maximum value in the array A. (1) Basic idea and Pseudocode: (Pleas first use a few sentences of plan language to explain the basic idea of your algorithm, then provide the pseudo-code of your algorithm. Please be clear about each step of your pseudo-code, when necessary, you can add comments to explain each step) Analysis: derive a recurrence for the running time T(n) of your algorithm, and solve the recurrence to provide the asymptotic running time of your algorithm.

You are given an array A, which stores n non-negative integers. Design an efficient divide-and-conquer algorithm that accepts A and n as inputs and returns the index of the maximum value in the array A. (1) Basic idea and Pseudocode: (Pleas first use a few sentences of plan language to explain the basic idea of your algorithm, then provide the pseudo-code of your algorithm. Please be clear about each step of your pseudo-code, when necessary, you can add comments to explain each step) Analysis: derive a recurrence for the running time T(n) of your algorithm, and solve the recurrence to provide the asymptotic running time of your algorithm.

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter15: Recursion

Section: Chapter Questions

Problem 6PE

See similar textbooks

Similar questions

Design and Analysis of Algorithms Consider the following description of a recursive algorithm:“The algorithm splits the input in three equal parts in constant time, process each part recursively and finally combines the solution in linear time”.Formulate a recurrence and solve it to compute total execution time of the algorithm.(Note: You can use any method for solving the recurrence.)
1. Design an algorithm to find the weighted sum of four test scores (https://en.wikipedia.org/wiki/Weight_function). Assume that the weights have been accurately calculated in advance such that their sum equals one. Your algorithm must-read in the four test scores and four corresponding weights in the following order: score1 weight1 score2 weight2 score3 weight3 score4 weight4 Write your algorithm such that it can be run with any set of data values. However, you can test your algorithm on the following sample data to verify that the result is 70: 90 0.10 80 0.20 70 0.30 60 0.40 2. Write an algorithm that prompts the user for the radius, in inches, and price of a pizza, and then reads in those values. Finally, have the algorithm compute and output the pizza’s cost per square inch. 3. Sports exercise advisor algorithm. In this algorithm you will start out with a temperature value in Celsius, so you do not need to ask the user for it. First, convert the temperature to Fahrenheit.…
Example: Algorithm to find maximum element in an array of size n. Requirement: Systematically describe the following steps for the simple example given above. 1. Problem statement2. Algorithm design3. Implementation using pseudo code4. Analysis of best, worst and average running times5. Space complexity6. Correctness of algorithm7. Visualization of Analysis
Develop python program of function randomArray(m, n) that takes two integers as argument and returns a 2D m-by-n array with random elements in it. Develop python program of function adder(a1, a2) that reads two 2D arrays of the same size and returns an array that is the summation of a1 and a2. To add the two arrays, you need to add their elements, correspondingly. Develop a python program of function inverseArray(a) that takes a 2D-array as argument and inverses the array. You will need to inverse the rows, first and then inverse the columns, next. For instance, if the array = [[2, 3, 4], [5, 6, 7]], the inverse will be = [[7, 6, 5], [4, 3, 2]]
9. Voting Suppose that the votes of n people for different candidates (where there can be more than two candidates) for a particular office are the elements of a sequence. A person wins the election if this person receives a majority of the votes. * Devise a divide-and-conquer algorithm that determines whether the two candidates who received the most votes each received at least n/4 votes and, if so, determine who these two candidates are. (NOTE: Please elaborate and explain briefly and please do not provide or copy answer from the internet or from chegg.)
can you please convert this python code into java? Python code is as shown below: # recursive function def row_puzzle_rec(row, pos, visited): # if the element at the current position is o we have reached our goal if row[pos] == o: possible = True else: # make a copy of the visited array visited = visited[:} # if the element at the current position has been already visited then it's a loop. # as then its not possible to reach the last element, set possible to False if visited[pos]: possible = False else: # set visitied for the element as True visited[pos] = True possible = False # if its possible to move left then recurse in the left direction if pos - rowlpos} > o and row_puzzle_rec(row, pos - row[pos], visited): # return immediately if the goal is reached return True # if its possible to move right then recurse in the right direction if pos + rowlpos} < len(row) and row_puzzle_rec(row, pos + row[pos], visited): # return immediately if the goal is reached. return True return possible…
Consider the given code below and the clock cycles are given. Identify all the stalls that are produced when one single code iteration is being executed. Show the overall number of cycles per iteration. Schedule the loop instructions in order to reduce the number of stalls. (Hint: Loop scheduling Reordering instructions can reduce the number of stalls) Unroll the loop in the following way: each unrolled iteration processes four array positions. Unrolled loop Unrolling the loop with a factor of four obtains loop : lw $ f0 , 22( $t0 ) lw $ f2 , 32( $t1 ) add.d $ f4 , $ f0 , $ f 2 mul.d $ f4 , $ f4 , $ f 6 sw $ f4 , ( $t2 ) addi $t0 , $t0 , 8 addi $t1 , $t1 , 8 subi $t3 , $t3 , 1 bnez $t3 , loop Lw and store—takes 2 clock cycles add.d takes 4 clock cycles mul.d takes 6 clock cycles addi and subi takes 0 clock cycles bnez takes 1 clock cycles
(c) Suppose you are given a set of 100m sprint times from the 2020 olympics. The input list has sizen and is not sorted, and you may assume that each time is distinct (there are no exact ties). Your team-mate completed in the event, and her time was exactly 10.57 seconds. She returns from the olympics upset, claiming that at least half the competitors had a faster time. Design an algorithm that takes as input the array A consisting of the n sprint times, and outputs the closest n/4 sprint times that are faster than friend's time. Justify why your algorithm runs in O(n) in the worst case. *For simplicity, you may assume n/4 is an integer your
Q1. (A) Draw a solution algorithm (at the same time) to find the maximum and minimum values of n matrix elements, and input the pseudo code. (B) The number of comparisons between the algorithms is recursively related and solved by assuming n=2k . © How to compare this algorithm with a simple algorithm to solve the same problem?
Algorithm problem w/ recurrence: Frying pancakes: a small pan can only hold two pancakes at a time. Each pancake needs to be fried on both sides. Frying one side takes 1 minute, no matter how many pancakes are on the pan. Consider this recursive algorithm: If n <= 2, fry the pancakes or the two pancakes together on each side. If n > 2, fry any two pancakes together on each side and then apply the same process recursively to the remaining n-2 pancakes. a. Set up and solve the recurrence for the amount of time this algorithm needs to fry n pancakes. b. Explain why this algorithm does not fry the pancakes in the minimum time for all n > 0. c. Give a correct recursive algorithm that executes the task in the minimum amount of time. > I was not sure how to start this. I have had trouble with recurrence in the past. Also from the work that I did do, I didn't know how there could be a better algorithm. Thanks in advance
can you please convert this python code into java? Python code is as shown below: # recursive function def row_puzzle_rec(row, pos, visited): # if the element at the current position is 0 we have reached our goal if row[pos] == 0: possible = True else: # make a copy of the visited array visited = visited[:] # if the element at the current position has been already visited then it's a loop. # as then its not possible to reach the last element, set possible to False if visited[pos]: possible = False else: # set visitied for the element as True visited[pos] = True possible = False # if its possible to move left then recurse in the left direction if pos - row[pos] > 0 and row_puzzle_rec(row, pos - row[pos], visited): # return immediately if the goal is reached return True # if its possible to move right then recurse in…
Find the complexity of the following blocks of code or algorithm’s description.[Note: your answer must show the steps that lead to your final answer] 1) The algorithm solves the problem ofsize n by recursively solving subproblems of size n – 1, and thencombining the solutions in constanttime.2) The algorithm solves the problemby breaking it into 16 subproblems of 1/4 the scale,recursively solving each submaze, and then combining thesolutions in linear time3) The algorithm solves the problem ofsize n by dividing it into 32 subproblems of size n/2, recursivelysolving each sub-problem, and thencombining the solutions in O(n5)time