In this homework, you will analyze and compare algorithmic complexity of four different solutions for the
Maximum Subsequence Sum Problem. For that, first read Section 2.4.3 (Solutions for the Maximum Subsequence Sum Problem) from the handout and study each of these four solutions. Be sure that you understand how the upper bounds are found for the running time of each solution. Then, implement these solutions in C++. Note that you may use the codes provided in the handout.
Next, write a driver (main) function that generates an array that contains integers and calls each of these solutions with that array as input. Run each solution on a computer and record execution times when different input sizes are used. You are expected to try many different input sizes, both small inputs and very large inputs (as large as thousands to millions depending on the solution), and observe the effects of different growth rates.
In this assignment,
Use your results to generate a comparison table and a plot of running time (y-axis) versus the input size N (x-axis). In particular, you are expected to produce a table and a plot as in Figure 2.2 and Figure 2.3 of the handout, respectively. In the table, each row corresponds to an input size and each column holds the running times of a specific solution.
Plot the expected growth rates obtained from the theoretical analysis (as given for each solution) by using the same N values that you used in obtaining your results. Compare the expected growth rates and the obtained results, and discuss your observations in a paragraph.
Provide the specifications of the computer you used to obtain these execution times. You can use any computer with any operating system for this assignment.
You can use the following code segment to compute the execution time of a code block. For these operations, you must include the chrono header file.
// Declare necessary variables
std::chrono::time_point< std::chrono::system_clock > startTime; std::chrono::duration< double, milli > elapsedTime;
// Store the starting time
startTime = std::chrono::system_clock::now();
// Code block ...
// Compute the number of milliseconds that passed since the starting time elapsedTime = std::chrono::system_clock::now() - startTime;
cout << "Execution took " << elapsedTime.count() << " milliseconds." << endl;
