subject
Mathematics, 20.10.2021 14:20 jdchacon117

Let XX[1: nn] be a real array. A prefix of X is a subarray XX[1: kk] where 1 ≤ kk ≤ nn, and a suffix of X is a subarray XX[kk: nn]. The minimum-prefix-product problem is the problem of taking XX[1:nn] as input and returning the k such that XX[1] × XX[2] × … × XX[kk] is the smallest possible. The minimum-suffix-product problem is to find k such that XX[kk] × XX[kk + 1] × … × XX[nn] is the smallest possible. The minimum-subarray-product problem is the problem of taking XX[1: nn] as input and returning two integers k and r, (1 ≤ kk ≤ rr ≤ nn), such that XX[kk] × XX[kk + 1] × … × XX[rr] is the smallest possible. a. Write a divide-and-conquer algorithm for solving the minimum-prefix-product problem, and another divide-and-conquer algorithm for solving the minimum-suffix-product problem.
b. Write a divide-and-conquer algorithm for solving the minimum-subarray-product problem.
c. Analyze the time complexity of your algorithms.

ansver
Answers: 3

Other questions on the subject: Mathematics

image
Mathematics, 21.06.2019 15:00, 6clevare
If 1 is divided by the sum of y& 4. the result is equal to 3 divided by 4 .find the value of m?
Answers: 1
image
Mathematics, 21.06.2019 18:00, kush3489t
Aplane is taking off from bangladesh headed to new york city. at the same time, a plane from new york city is headed to bangladesh is also taking off. the plane bound to new york city is traveling at 600 mph, while the plane traveling to bangladesh is traveling at 400 mph. how far from new york city will the two planes meet if the distance between new york city and bangladesh is 8,000 miles?
Answers: 3
image
Mathematics, 21.06.2019 19:10, chancler
Find the roots of the polynomial function f(x) = x^3 + 2x^2 + x
Answers: 2
image
Mathematics, 22.06.2019 01:00, ramireztony741
Michael split a rope that was 28 inches long into 5 equal parts. brenden split a rope that was 30 inches long into 6 equal parts. which boy's rope was cut into longer pieces?
Answers: 1
You know the right answer?
Let XX[1: nn] be a real array. A prefix of X is a subarray XX[1: kk] where 1 ≤ kk ≤ nn, and a suffix...

Questions in other subjects:

Konu
Physics, 03.10.2019 09:00