The assignment revolves around analyzing and comparing the performance of three algorithms for finding the maximum subarray sum. The tasks are divided into several parts:

Task Overview:

Algorithm Implementation:

Implement three algorithms to find the maximum subarray sum.

Validate their correctness using small test arrays.

Runtime Analysis:

Add counters to measure the number of assignment statements in each algorithm.

Run the algorithms on randomly generated arrays of sizes $5,10,15,...,$ up to $50.$

Generate $2000$ arrays for each size and compute the average number of assignments for each algorithm.

Result Presentation:

Output the average number of assignments in a tabular format.

Plot graphs showing the relationship between array size and the number of assignments.

Analyze the results to determine the runtime complexity $($Big$-$O notation$)$ of each algorithm.

Extended Analysis:

Implement the ExperimentalRuntimeAnalyzer class.

Run the algorithms on larger arrays $(50,000$ to $800,000$ elements$).$

Repeat each experiment $5$ times and average the results.

Present the findings using tables and graphs, comparing theoretical and experimental growth rates.

Reporting:

Submit the source code, Excel spreadsheets with data and graphs, and a comprehensive report.

The report should include sections on theoretical analysis, experimental results, comparison of results, discussion, and conclusion.

Theoretical Analysis:

Algorithm $1$:

Description: Compute the sum of all subarrays of increasing sizes and track the maximum sum.

Time Complexity: O$($n$^3)$ due to the triple nested loop for subarray sum computation.

Algorithm $2$:

Description: Compute the sum of subarrays starting from each index.

Time Complexity: O$($n$^2)$ as it avoids recomputing sums from scratch by reusing previous computations.

Algorithm $3$:

Description: Compute sums for subarrays, restarting from the next index if the sum becomes negative.

Time Complexity: O$($n$)$ due to its linear nature, restarting computation only when necessary.

Experimental Setup:

Implementation:

Write a MethodTester class with methods for each algorithm.

Write a RuntimeAnalyzer class to measure assignment counts.

Generate random arrays and run the algorithms to collect data.

Data Collection:

Run experiments for arrays of sizes $5,10,15,...,50.$

Record the number of assignment statements.

Analysis:

Plot the data and compare the experimental results with theoretical predictions.

Discuss the performance and scalability of each algorithm.

Submission Requirements:

Source Code: C$++$ programs for the algorithms and runtime analysis.

Excel Data: Spreadsheets with data and graphs.

Report: A detailed report with theoretical analysis, experimental results, comparisons, and discussion.

This assignment aims to deepen the understanding of algorithm performance, growth rates, and the practical application of theoretical analysis in experimental settings.