Description
This assignment is a short assignment and it does not involve any programming.
With this assignment, you will deepen your understanding on how Algorithms 1 and 4 (discussed in lecture on pp. 61 in the textbook) go about solving the “maximal subsequence sum” problem. You will be asked to communicate your understanding in your own words.
Study both algorithms; consult your lecture notes and the text book as needed. You should not find it very difficult to understand how Algorithm1 solves the problem: it iterates over all possible subsequences of the input sequence and keeps track of the maximal sum at each iteration. The maximal subsequence sum is found at a cost of O(N3). You need not write to elaborate on this.
Algorithm4 is much more surprising and interesting. How can it be that the same problem can be solved with a single pass over the input values?!
Task 1: Answer the following questions …
- What is the maximal contiguous subsum for a vector of only positive values? (Explain in general, not by specific example.)
- What is the maximal contiguous subsum for a vector of only negative values? (Explain in general, not by specific example.)
- Imagine a stage of problem solving in the context of Algorithm 4: previous iterations have determined som candidate (so far seen) maximal subsum; in the current iteration, a local sum has been accumulated and its value is negative. What is the significance of this fact for this current iteration relative to our goal (= finding the overall maximal subsum)?
Task 2: Write one brief paragraph, in which you explain in your own words what the clever insight is that allows Algorithm4 to solve the problem in a single for-loop (= single pass over the input). Write plainly, clearly, and concisely. The answers from Task 1 should be helpful.
Type or write neatly (!) by hand.
The deadline for submitting this assignment is
Monday, January 20, 2020, at the beginning of class.
