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):

a) analysis of Algorithm #1 (contained in "project08algorithm1.cpp"-- this is Blue function)
    b) analysis of Algorithm #2 (contained in "project08algorithm2.cpp"-- this is Green function)
    c) analysis of Algorithm #3 (contained in "project08algorithm3.cpp"-- this is Red function)
    d) the name and specification of the computer such as the Operating System, Processor, Memory.
    e) actual running times for function BLUE
    f) actual running times for function GREEN
    g) actual running times for function RED
    h) a statement about which algorithms from a) through c) are implemented by which functions (e) through (g), and conclusions about your theoretical and actual results
  
In sections (e) through (g), be sure to include the maximum contiguous subsequence sum for each array size to demonstrate that the computations are correct.

-------------------------------------------------

project08algorithm1.cpp (Blue)

------------------------------------------------------------------

project08algorithm2.cpp (Green)

---------------------------------------------------------------

project08algorithm3.cpp (Red)

----------------------------------------------------

project08driver

Explanation / Answer

a) algorithm 1 detects the Max_sum

b) algorithm 2 detects the Max_sum

c) algorithm 3 detects Max_sum based on the value of This_sum

d) computer processor: AMD A4 1250

OS: Windows 8.1

Memory: 4GB DDR3

e) actual running time for function BLUE: 20 s

f) actual running time for function GREEN: 20 s

g) actual runing time for function RED: 45 s

h) algorithm 1 --> function BLUE

algorithm 2 --> function GREEN

algorithm 3 --> function RED

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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