The input is a sequence of numbers a1, a2,…, an. A subsequence is a sequence of
ID: 3574537 • Letter: T
Question
The input is a sequence of numbers a1, a2,…, an. A subsequence is a sequence of numbers found consecutively within a1, a2,…, an. For example, in the sequence: -3, -1, 17, 5, 66, 22, -5, 42, both 17, 5, 66 and -1, 17 are subsequences. However, 66, -5 is not a subsequence because 66 and -5 do not appear consecutively in the sequence. A subsequence can contain only one number such as 66. It can also be empty.
....
....
(a)
Characterize the asymptotic growth of the worst-case time complexity of the algorithm. Justify your answer.
(b)
Can you find an algorithm that solves the same problem whose worst-case time complexity is linear?
The input is a sequence of numbers a1, a2,..., an. A subsequence is a sequence of numbers found consecutively within a1, a2,..., an. For example, in the sequence: -3, -1, 17, 5, 66, 22, -5, 42, both 17, 5, 66 and -1, 17 are subsequences. However, 66, -5 is not a subsequence because 66 and -5 do not appear consecutively in the sequence. A subsequence can contain only one number such as 66. It can also be empty. In the maximum subsequence sum problem, the input is a sequence of numbers and the output is the maximum number that can be obtained by summing the numbers in a subsequence of the input sequence. If the input was the sequence -3, -1, 17, 5, 66, 22, -5, 42, then the output would be 147 because the sum of subsequence 17, 5, 66, -5, 42 is 147. Any other subsequence will sum to an equal or smaller number. The empty subsequence sums to 0, so the maximum subsequence sum will always be at least 0. The algorithm below computes the maximum subsequence sum of an input sequence MaximumSubsequenceSum Input: a1, a2,...,an n, the length of the sequence. Output: The value of the maximum subsequence sum. maxSum 0 For 1 to n thisSum 0 For j i n to thisSum this Sum ai lf thisSurm maxSum), maxSum thisSum End-for End-for Return maxSum) (a) Characterize the asymptotic growth of the worst-case time complexity of the algorithm. Justify your answer. (b) Can you find an algorithm that solves the same problem whose worst-case time complexity is linear?Explanation / Answer
(a) The algorithm has two loops each iterations from 1 to n. For each value i there are n iterations for value of j. There are n possible values of i. So in total there are n*n iterations. Each operations inside the array is O(1) time. So total time is O(n*n)
(b) The algorithm in linear time is:
MaximumSum(a,N)
{
mx = 0
mx_t = 0
for i = 1:N
mx_t = mx_t+a[i]
if(mx_t<0)
max_t=0
end
if(mx < mx_t)
mx=max_t
end
end
return mx
}
This has only one loop. The idea is that we keep adding all the numbers to a sum variable and when that sum variable becomes negative we make it 0, because if it is negative then we will find maximum only when we ignore that part and start fresh.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.