You will analyze three algorithms to solve the maximum contiguous subsequence su

Question

You will analyze three algorithms to solve the maximum contiguous subsequence sum problem, and then evaluate the performance of instructor-supplied implementations of those three algorithms. You will compare your theoretical results to your actual results in a written report.

What is the maximum contiguous subsequence sum problem?

Given a sequence of integers A1, A2, ..., An (where the integers may be positive or negative), find a subsequence Aj, ... , Ak that has the maximum value of all possible subsequences.

The maximum contiguous subsequence sum is defined to be zero if all of the integers in the sequence are negative.

Consider the sequence shown below.

A1: -2
A2: 11
A3: -4
A4: 13
A5: -5
A6:   2

The maximum contiguous subsequence sum is 20, representing the contiguous subsequence in positions 2, 3 and 4. The sum of the values in all other contiguous subsequences is less than or equal to 20.

Consider a second sequence, shown below.

A1:   1
A2: -3
A3:   4
A4: -2
A5: -1
A6:   6

The maximum contiguous subsequence sum is 7, representing the contiguous subsequence in positions 3, 4, 5 and 6.

Four different algorithms have been developed to solve this problem, you can download them below.

You will:

1. Analyze each of the three algorithms in source code form.
To analyze an algorithm, you will review the C++ source code, then give the upper bound (in "Big-Oh" notation) on the execution time of the algorithm and briefly explain your reasoning.

2. Compile and run the program to evaluate the performance of the three functions.
To evaluate the performance of an algorithm on a computer, you will call the functions in a driver (such as the one we supplied: project08driver.cpp ) and execute the program. The driver can call these three functions with different prototypes shown below.

    int Max_Subsequence_Sum_BLUE ( const int [], const unsigned int );

    int Max_Subsequence_Sum_GREEN( const int [], const unsigned int );

    int Max_Subsequence_Sum_RED ( const int [], const unsigned int );

To evaluate a function, you will execute the program which uses that function for each of the following input sequence sizes:

      N = 64, 128, 256, 512, 1024, 2048

3. Write a report comparing your theoretical and actual results from 1. and 2.
        
In your report, include the times of all test cases for each combination of N and function (COLOR).

Your report will contain the following sections (in the order stated):

I couldn't upload the cpp files, but I can email it to anyone is willing to help.

Explanation / Answer

The idea is to split your sequence in half, find the answers for both halves, then use that to find the answer for the entire sequence.

Assume you have a sequence [left, right]. Let m = (left + right) / 2. Now, the maximum sum subsequence (MSS) of [left, right] is either MSS(left, m), MSS(m + 1, right) or a sequence that starts in [left, m] and ends somewhere in [m + 1, right].

Pseudocode:

This is O(n log n) because the recursion three has height O(log n) and at each level of the tree we do O(n) work.

Here is how it would run on -2, 4, -1, 3, 5, -6, 1, 2:

Of interest is the computation of MSS(0, 3) and MSS(0, 7), since these do not simply take the max of their children. For MSS(0, 3) we try to make as large a sum as possible adding consecutive elements starting with the middle of the interval (1) and going left. This max is 4. Next we do the same starting with the middle of the interval + 1 and going right. This max is 2. Adding these together gets us a maximum sum subsequence with the sum of 6, which is larger than the maximum sum subsequence of the two child intervals, so we take this one instead.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.