Need a good answer. You will analyze three algorithms to solve the maximum conti

Question

Need a good answer.

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.

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.

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

algorithm 1-

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

Sample driver-

___________________________________________________________________________________________

A good working answer needed,

thank you

Explanation / Answer

Algorithm 1

int Max_Subsequence_Sum( const int A[], const int N )
{
int This_Sum = 0, Max_Sum = 0;

for (int i=0; i<N; i++)
{
    This_Sum = 0;
    for (int j=i; j<N; j++)
    {
      This_Sum += A[j];
      if (This_Sum > Max_Sum)
      {
        Max_Sum = This_Sum;
      }
    }
}
return Max_Sum;
}

Actual running time for function BLUE will beO( N2)

i will run for n time and j will run for i time where i=n

so total running time is n*n=n2

==================================================

Algorithm #2  

//project08algorithm2.cpp

int Max_Subsequence_Sum( const int A[], const int N )
{
int This_Sum = 0, Max_Sum = 0;

for (int i=0; i<N; i++)
{
    for (int j=i; j<N; j++)
    {
      This_Sum = 0;
      for (int k=i; k<=j; k++)
      {
        This_Sum += A[k];
      }
      if (This_Sum > Max_Sum)
      {
        Max_Sum = This_Sum;
      }
    }
}
return Max_Sum;
}

This function will run for N3 as all the three variables will run for n times

so n*n*n=n3

===========================================================

Algorithm #3

//project08algorithm3.cpp

int Max_Subsequence_Sum( const int A[], const int N )
{
int This_Sum = 0, Max_Sum = 0;

for (int Seq_End=0; Seq_End<N; Seq_End++)
{
    This_Sum += A[Seq_End];

    if (This_Sum > Max_Sum)
    {
      Max_Sum = This_Sum;
    }
    else if (This_Sum < 0)
    {
      This_Sum = 0;
    }
}
return Max_Sum;
}

This function will run for N time as

Seq_End will run for n time.

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

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