Siven an array of real numbers A[1..n], the maximum sum of contiguous subarray is 1 Σ OPT:= max sikis A[k]. k=" (a) Design a simple brute-force search O(n²) time algorithm to compute OPT. (b) Define the subproblem as follows: Let M (1) be the maximum sum of all contiguous subarrays ending at position i. Clearly M (1) = A[1]. What is the recurrence relation for computing M (i)? Use this to give a more efficient algorithm to compute OPT.

Siven an array of real numbers A[1..n], the maximum sum of contiguous subarray is 1 Σ OPT:= max sikis A[k]. k=" (a) Design a simple brute-force search O(n²) time algorithm to compute OPT. (b) Define the subproblem as follows: Let M (1) be the maximum sum of all contiguous subarrays ending at position i. Clearly M (1) = A[1]. What is the recurrence relation for computing M (i)? Use this to give a more efficient algorithm to compute OPT.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

solve
I need help the question
Derive the worst case upper bound of the following algorithm. Matrics_Multiplication (A, B) { I пхmmatrixА // m × p matrix B I пxрmatrixС // C= AB 1. Let C be a new matrix of the appropriate size 2. For i from 1 to n: For j from 1 to p: 3. 4. Let sum = 0 For k from 1 to m: 5. 6. Set sum - sum+A¡k × Brj 7. Set Cij - sum 8. Return C }
1. Let S be a set of n arbitrary but distinct numbers. (a) Give a deterministic algorithm to output the largest n³/4 of the numbers in S in sorted order. Your algorithm must use O(n) comparisons. (b) Show that any deterministic comparison-based algorithm that correctly outputs the median on inputs of n distinct elements must use at least n 1 comparisons. To be completely precise, the median is defined to be the [n/2]th smallest element.
The algorithm below searches for the maximum in an input array A. Assume A is a random sequence containing n distinguishable real numbers, what is the probability for line #4 to be executed exactly once? (The phrase "random sequence" here means the n numbers can appear in any order with equal chance.) mymax(A, n) { 1: max = A[1]; 2: for i = 2:n 3: if A[i] > max 4: max = A[i); 5: end; 6: end; 7: return max; }
Given an integer array [A], efficiently find a descending sorted triplet such that: A[i]> A[i]> A[k] and 0 <=i<j <k <n, where n is the array size. For example, Input: A[] = {9, 1, 6, 7, 3, 4, 5) Output: Any one of the following triplets: (9, 7,5) (9, 7, 4) (9, 7, 3) (9, 6, 5) (9, 6, 4) (9, 6, 3) a) Design a brute-force algorithm to solve this problem complexity of your solution b) Design a more efficient algorithm to do the same task with less complexity and analyse the complexity of your solution. c) Develop a python code to implement your efficient algorithm. depend on the correctness of the code, indentation, comments, test-case] d) Prepare a brief report (250 words) comparing the two algorithms
please
Problem 2: Finding an element.(i) Let n be an even positive integer. Let A be an array containing n not necessarydifferent integers. Elements in A are not necessary sorted. Describe an algorithmwhich in time O(n) tests whether there exists an element x in A that appears in Aat least n/2 times.(ii) Let S be a set containing n integers. An element x ∈ S is an approximate median ofS, if|{y ∈ S | y < x}| ≥ n/4and |{y ∈ S | y > x}| ≥ n/4Given an array A containing n different integers, not necessary sorted, describe analgorithm which in time O(n) finds all approximate medians of the set {A[i] | i =1, 2, . . . , n}.
Let M(n) be the minimum number of comparisons needed to sort an array A with exactly n ele- ments. For example, M(1) = 0, M(2) = 1, and M(4) = 4. If n is an even number, clearly explain why M(n) = 2M(n/2) + n/2.
Given an array of unsorted integers, find the maximum product of two integers in an array. For example, if the arc = [10, 8, -1, 7, 14] then the maximum product would be 140, as output of (10 x 14). To solve this problem, the following idea can be used: Design a brute-force algorithm to solve this problem using a Pseudocode and find its complexity - Another solution would be "Sort the array first, and then to get the product of its highest two integers". Is this idea better that the first one? Explain why? Is there any extreme case that should be considered while designing your algorithm? Justify your answer. Design your own idea to solve this problem in O(n) complexity, where n is the size of the array. [note: your idea should be explained in simple English, and then transformed into algorithm (pseudocode)].
A robber is planning to rob the houses along a street. The constraint is, that he cannot rob adjacent houses. If done, it will alert the police. For the below-given algorithm and input, your task is to draw a DP matrix AND return the maximum earnings in a single night: nums = [4,3,6,2,7,10,5] Algorithm: def rob(self, nums: List[int]) -> int: dp = [0]*len(nums) // Initialize dp array n = len(dp) if len(nums) == 1: return nums[0] elif len(nums) == 2: return max(nums[0],nums[1]) dp[0]=nums[0] dp[1]=max(nums[1],nums[0]) for i in range(2,len(nums)): dp[i] = max(nums[i]+dp[i-2],dp[i-1]) return dp[n-1]