Algorithm Concepts: Max Subarray Problem Analysis (CSCI 651)

Desklib provides past papers and solved assignments for students. This project analyzes algorithms for the maximum subarray problem.

CSCI 651 Algorithm Concepts
Assignment 1

Table of Contents
3. Max Sub Array algorithm using Brute Force approach.......................................................................3
4. Max Sub Array algorithm using Divide & Conquer approach............................................................4
6. Plot the running times as a function of input size for each algorithm in a single plot.........................6
CODE SCREENSHOTS..........................................................................................................................9
DIVIDE & CONQUER.......................................................................................................................9
BRUTE FORCE................................................................................................................................10
7. Do the theoretical and experimental running times agree?................................................................11
8. The real-world example that can be modeled and solved as a maximum subarray problem............11
Table of Figures:
Figure 1: running time graph using brute force.......................................................................................7
Figure 2: running time graph using divide and conquer..........................................................................8
Figure 3: code 1.......................................................................................................................................9
Figure 4: code 2.......................................................................................................................................9
Figure 5: code 3.....................................................................................................................................10
Figure 6: code 1.....................................................................................................................................10
Figure 7: code 2.....................................................................................................................................11

3. Max Sub Array algorithm using Brute Force approach
a.
This program calculates the maximum subarray using the brute force approach.
Creating a class named MaxSubarrayUsingBruteForce in which methods are included.
Method getMexSubarraySum (argument)
{
Loop1 from 0 to 10 (i)
{
Maximum ending sum equals int min value
Maximum current equals zero
Start equals zero
starting time in Nanosecond
Loop2 from 0 to 100 (j)
{
Add argument to Maximum current
if maximum current less than 0
maximum current = 0
add j to start
if maximum current greater than maximum ending sum
maximum ending sum = maximum current
previous index = start
last index equals j
}
end time in Nano seconds
Elapsed time = (end Time – start Time) / 1000
Elapsed Time (i++) = time Elapsed
Print time elapsed
Print max sub array
Starting a loop from previous index to the last index
Loop from the previous index to (last index – 1)
{
Print argument (i, j)

}
Print argument (i, last index)
Print maximum ending sum
Print previous index
Print last index
}}
main ()
{
 Creating scanner object and scanning the test file for the array.
 Calling the getMexSubarraySum (parameter: value [] [])
 Creating a graph object and calling graph to create the graph with input size and running time.
}
b. The asymptotic running time of the algorithm is O((n^2)) approximately as there are 2 nested
loops.
4. Max Sub Array algorithm using Divide & Conquer approach
This program calculates the maximum subarray using the divide & conquer approach.
Declaring 2 methods:
The first method will get the maximum subarray sum which passes from the middle element.
The second method will get a maximum of three elements.
Method maxSumOfSubArrayParts (argument 1, argument 2, argument 3, argument 4)
{
Maximum ending sum equals 0
Decremental Loop from argument 3 to argument 2
{
adding argument 1 in maximum ending sum
if maximum ending sum is greater than maximum ending left sum

max ending left sum equals max ending sum
}
Max ending sum to 0
Incremental loop from (argument 3) + 1 to argument 4
{
if maximum ending sum is greater than the maximum ending right sum
max ending right sum equals max ending sum
}
The returning sum of the max left and max right
}
Method getMexSubarraySum (argument 1, argument 2, argument 3)
{
if size of argument 2 = argument 3
{
return argument 1 [argument 2]
}
m = (argument 2 + argument 3 ) / 2
return max of the three arrays m, left and right
}
main ()
{
Creating a scanner object and scanning the file.

Incremental loop from 0 to 10
{
Datapoint equals value [] []
size equals datapoint’s length – 1
Start time to Nano time
calling getMexSubarraySum (dataPoint, 0, size) as parameters
End time to Nano time
Elapsed time = (end Time – start Time) / 1000
Elapsed Time (i++) = time Elapsed
Print time elapsed
}
Creating graph object and calling graph to create the graph with input size and running time
}
b. The asymptotic running time of the algorithm is O(nlogn) because method getMexSubarraySum is a
recursive method.

6. Plot the running times as a function of input size for each algorithm
in a single plot
The graphs represented below are made from the outputs generated by the experimental program
which generates random array sizes and random elements and count the time of the running function.
BRUTE FORCE
Figure 1: running time graph using brute force

DIVIDE & CONQUER
Figure 2: running time graph using divide and conqure

CODE SCREENSHOTS
DIVIDE & CONQUER
Figure 3: code 1
Figure 4: code 2

Figure 5: code 3
BRUTE FORCE
Figure 6: code 1

Figure 7: code 2
7. Do the theoretical and experimental running times agree?
Yes, the theoretical and the experimental running times absolutely agree.
When we run both brute force and divide & conquer with random elements, the graph shows us the
result as to how much better the divide and conquer approach is.
The brute force is taking greater time than the divide and conquer approach. Hence, this proves that
the divide and conquer approach is anytime better than the brute force approach.
8. The real-world example that can be modelled and solved as a
maximum subarray problem
In this case, a very good example can be the analysis of a business. For example, let’s consider there
is a company which has many employees. Now each employee has income details, which can be used
in this example. Now with the data of the employees and their incomes, we can easily find out in
which part of a particular year the company earns the highest and also track the growth of the
company. This will help the company to find what they did well to get higher results next time or
prevent some other issue from happening in the future.

References
Sleit, A., AlMobaideen, W., Qatawneh, M. and Saadeh, H., 2009. Efficient processing for binary submatrix
matching. American Journal of Applied Sciences, 6(1), p.78.
Bashar, M.E., 2007. Average case analysis of algorithms for the maximum subarray problem.
Tropp, J.A. and Wright, S.J., 2010. Computational methods for sparse solution of linear inverse
problems. Proceedings of the IEEE, 98(6), pp.948-958.