Laboration 1.3, Group 28


This is a hand-in written by Mazdak Farrokhzad and Niclas Alexandersson in group 28 for the 3rd assignment on Lab1.

The assignment is about analysing an algorithm written in 3 different ways where all of them are functionally equivalent. The methods are available in the appendix.

The analysis consists of:

a. Description of what the algorithm does

b. Complexity analysis

c. Testing and numerical analysis

Description of what the algorithm does

The algorithm finds the sum of the first subsequence of numbers that has the greatest non-negative sum in an array of numbers. This may sound cryptic, so lets shed some light on it with an illustration.

If we have e.g. the sequence [1, 2, 3, 4] it will yield the sum 10, and the indexes will be seqStart = 0, seqEnd = 3

  • thus it will simply return the sum of the whole sequence.

Instead, lets use the sequence [-1, 2, 3, 4, -10, 5].

In this case the subsequence will be the sum [2, 3, 4] = 9, and the indexes will be seqStart = 1, seqEnd = 3.

Why? The first number, -1, will be skipped since it is negative. The sequence will then stop at 4 when it finds that 9 + -10 = -1. 5 is < 9, and therefore, 9 is the sum.

Complexity analysis

Laws and forumulas of summation

These summation