# CS 201 Homework Assignment 2 solved

\$35.00

## Description

5/5 - (1 vote)

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,
1. 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.
2. 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.
3. 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;