ANALYSIS OF ALGORITHMS

Group Programming Assignment 1

Prof. Xiaoli Fern

Due: Thursday, January 14 at 2PM on Canvas

You are required to work in groups of two or three students. To formally form your group on can- vas, I have created empty groups for this assignment that you can join. Coordinate with your team member so that you will join the same group. Please see http://guides.instructure.com/m/4212/l/ 64913-how-do-i-join-a-group-as-a-student for instruction on how to join a group.

Each group will need to submit one copy of the work to Canvas. This should include the project report as a pdf and the code that implements the algorithms. The report should have all member’s names included. Your implementation can be in Java, Python, C/C++, Matlab or R. Any language outside this list will need advance approval from the instructor. See the course syllabus for instructions/policies on using old work for students retaking CS325.

For this project, you will design, implement and analyze (both experimentally and mathematically) three algorithms for the maximum subarray problem:

Given array of small integers a[1, . . . , n] (that contains at least one positive integer), compute

max i≤j

j∑ k=i

a[k]

For example, MaxSubarray([31, −41, 59, 26, −53, 58, 97, −93, −23, 84]) = 187

Description of the algorithms

Your three algorithms are to be based on these ideas:

Algorithm 1: Enumeration Loop over each pair of indices i ≤ j and compute the sum, ∑j

k=i a[k]. Keep the best sum you have found so far.

Algorithm 2: Better Enumeration Notice that in the previous algorithm, the same sum is computed many times. In particular, notice that

∑j k=i a[k] can be computed from

∑j−1 k=i a[k] in O(1) time, rather

than starting from scratch. Write a new version of the first algorithm that takes advantage of this observation.

Algorithm 3: Dynamic Programming Your dynamic programming algorithm should be based on the following idea:

• The maximum subarray either uses the last element in the input array, or it doesn’t.

Describe the solution to the maximum subarray problem recursively and mathematically based on the above idea.

See pages 8-13 of https://web.engr.oregonstate.edu/~glencora/wiki/uploads/max-subarray.pdf for more details on these algorithms.

1

Testing for correctness You can test the correctness of your implementations using the test sets provided on canvas. The file has one test case per line (10 cases each with 100 entries). A line corresponding to the example above would be:

[31, -41, 59, 26, -53, 58, 97, -93, -23, 84], 187

with the input array followed by the sum of the maximum subarray.

2

Project report

Your typeset report must include:

Pseudocode Give pseudocode for each of the algorithms. Your pseudocode should make clear how many times your algorithm will

• add two numbers together

• take the max of two numbers

Note that the pseudocode in the above-linked pdf does not do this.

Run-time analysis For each algorithm, express the number of + and max (between two numbers) opera-

tions that it makes for an input array of n numbers as a sum (e.g. ∑n

i=1

∑n−1 j=i i

2). Give asymptotic bounds for each. (That is, you should give three sums and three asymptotic bounds, one for each algorithm.)

Experimental run-time analysis For the experimental analysis you will plot running times as a function of input size. Every programming language should provide access to a clock (not necessarily in seconds). Run each of your algorithms on input arrays of size 100, 200, 300, . . . , 900 and 1000, 2000, 3000, . . . , 9000 (that is, you should have 18 data points for each algorithm). The first enumerative algorithm may be frustratingly slow, so you may compute running times for sizes 100, 200, 300, . . . , 900.

To do this, generate random instances using a random number generator as provided by your programming language. Remember to include both positive and negative numbers! For each data point, you should take the average of a small number (say, 10) runs to smooth out any noise. For example, for the first data point, you will do something like:

for i = 1:10 A = random array with 100 entries start clock maxsubarray(A) pause clock

return elapsed time divided by 10

Note that you should not include the time to generate the instance. Plot the running times as a function of input size for each algorithm in a single plot. Label your plot (axes,

title, etc.). Include an additional plot of the running times on a log-log axis. See here for a tutorial on log-log plots: http://www.eecs.orst.edu/~glencora/cs325/videos/loglogplots.mp4 (and accompanying file: https://web.engr.oregonstate.edu/~glencora/wiki/uploads/loglogplots.m).

Note that if the slope of a line in a log-log plot is m, then the line is of the form Θ(xm) on a linear plot. Determine the slope of the lines in your log-log plot and from these slopes, infer the experimental running time for each algorithm. Discuss any discrepancies between the experimental and theoretical running times.

3

assignment1/testing.txt

[-11, 44, 40, -26, -5, 48, 19, -6, 25, 48, -28, 1, 23, -16, 24, 37, 12, -19, -3, -19, -13, 22, -11, 47, -16, -5, 0, 16, 29, -46, 1] [-20, 4, -19, 43, -18, 17, 50, 7, 40, -4, 13, 34, 42, -15, -17, -38, -49, 20, -46, -35, -41, -16, 42, 22, 0, -38, 9, 28, 25, 15, -37, 34, 17, -12, 43, 12, -37, -44, -45, 45, -39, 10, -46, -9, 27, 11, -27, -32, -3, 50] [-42, 26, 10, -38, 27, 4, 28, -16, 32, -38, -49, -26, 18, -44, 24, -24, -16, 11, 41, 38, -40, 23, -13, -37, -42, 21, 23, 47, -17, 3, -23, 15, 5, 47, -13, -35, 3, 26, -4, 8, 8] [-8, 6, 38, 35, 23, 30, 16, -2, -50, -41, -13, -38, 17, -12, -16, -12, 20, -47, -40, -39, 37, -46, 36, 26, 16, 13] [34, 36, -37, 23, 23, 8, -2, -15, -36, 5, 44, 21, -42, 17, -14, -30, 37, 21, -16, 18, 49, 36, -36, -8, 38, -40, -14, 40, -4, 0, -35, -34] [-50, 31, 25, -12, 13, -20, 46, -12, -32, 44, -25, -50, 16, -5, -30, 25, -25, -34, -6, -28, 4, 6, -41, 6, 44, -50, 5, 18, 44, -39, 9, 28, 2, -12, -2, -21, -39, -17, 1, 27, 22, 41, -20, -27, 36, 46, 43] [-46, -35, -15, -50, 45, -6, 19, 25, 25, -5, -50, -31, 49, -25, -30, -21, -11, -48, 9, -27, 32, 3, -9, -41, 20, -45, 22, 47, -33, 6, 40, -30] [21, -44, -19, -17, 23, -43, -26, 17, -44, 39, -6, 12, -28, -16, -36, -23, -27, 42, -26, -12, 8, 48, -41, -41, -11, 46, 44, -30, -44, -49, 15, 43, 47, -22] [26, -17, 8, -18, 32, 16, -50, -43, 22, -25, -23, 32, 27, -14, -44, -3, 8, -19, 28, -45, -6, 29, 30, -24, -37] [-5, -22, -26, -42, -40, -33, 10, 15, -27, 26, 21, 2, 49, 13, 44, 43, 35, 30, 9, 12, 49, -39, 33, 34, 2, 34, -40, -13, 0, 14] [36, 40, -8, 28, 38, -38, 24, -33, -27, -18, 26, 9, 9, 38, -35, 11, 36, -17, 20, 45, -9, 27, -24, -27, -28, -25, 41, -46, 29, 27, 34, -28, -44, -6, 26, 42, -16, 40, 27, 14, 22, 37, -26, 46, 21, 45, -40, -25, 5, 50] [5, 12, 34, 10, 20, 50, -38, 39, -27, 37, 23, 34, 19, 0, 18, -9, -14, 2, -8, -16, 34, 2] [-11, -14, -21, -2, -28, 37, -9, -35, -33, -18, -42, -44, 25, -32, 33, -44, -16, -42, 44, -43, -25, -39, -3, 31, -46, -41, 38, -49, 11, 11, 28, -22, -44] [-11, 23, -28, -33, -32, -7, 44, 23, -11, 39, -49, -42, -15, -50, -20, 39, -3, 45, 43, 48, 10, 47, 11, 47, -3, -22, -50, 0, 24, 1, 50, 16, 34, -2, 48, 34, -6, 44, -21, -37, -44, 6, -2, 45, 28, 16, -34] [-38, -22, 46, -43, 16, -47, 21, -31, 34, 43, -9, -40, -41, 17, 32, -7, -46, -39, 44, 10, -8, 23, -23, 31, 3, 2, -10, -11, 10] [2, -11, -7, 31, -18, 11, 10, 12, 33, -36, -44, 33, 4, 28, 39, 20, 1, 45, 38, -48, -26, 26, 35, 50, 26, -7, -45, -25, -29, 28, -47, -50, 15, 38, -3, -6, -39, 20, 45, 4, -32, 23, 48, 39, 3] [-4, 46, -30, 37, 33, 38, 1, -24, -39, 22, 0, 14, -1, 31, 28, -1, 15, 15, 40, 0, 12, 49, 38, -33, 16, -9, -49, 44, 41, -33, -8, -32, -29, -47, 16, 44, -45, 47, -25] [47, -5, -6, -22, -2, -37, 37, 21, -45, 3, 7, -42, 24, -12, -12, 15, -3, -12, 1, 29, -47, -1, -30, -31, 23, 28, 23, 38, 39, 42, -5, -4, -31, -31] [26, -14, 38, 44, -9, -18, 17, 41, 24, -1, 42, -36, 37, -17, -28, -26, -44, -23, 1, -16, -9, 9, 14, -48, -11, 49, 36, -3, 43, -15, 4, -17, 17, -1, 44, 28, -14, 50, -21, -3, 13, -6, -44, -22, -37, 40, -10] [-44, -47, -48, 17, 47, 3, -3, -20, -3, -20, 9, -4, -25, -22, 13, 11, -3, 12, -13, -20, 3]