ROUGH DRAFT authorea.com/4691
Main Data History
Export
Show Index Toggle 0 comments
  •  Quick Edit
  • Laboration 1.3, Group 28

    About

    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 laws/formulas are used frequently. They are very common and thus we won’t prove any of them. Most of them can be found here

    1. \(\displaystyle\sum_{n=s}^t C\cdot f(n) = C\cdot \sum_{n=s}^t f(n)\)

    2. \(\displaystyle\sum_{n=s}^t f(n) + \sum_{n=s}^{t} g(n) = \sum_{n=s}^t \left[f(n) + g(n)\right]\)

    3. \(\displaystyle\sum_{n=s}^t f(n) - \sum_{n=s}^{t} g(n) = \sum_{n=s}^t \left[f(n) - g(n)\right]\)

    4. \(\displaystyle\sum_{i=m}^n 1 = n+1-m \Rightarrow \sum_{i=m}^{n-1} 1 = n-m\)

    5. \(\displaystyle\sum_{i=m}^n i = \frac{n(n+1)}{2} - \frac{m(m-1)}{2} \Rightarrow \sum_{i=m}^{n-1} i = \frac{n(n-1)}{2} - \frac{m(m-1)}{2}\)

    6. \(\displaystyle\sum_{i=0}^n i^2 = \frac{n(n+1)(2n+1)}{6} = \frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6}\)

    Version 1

    Rough estimate

    The 3 nested loops takes in worst case: \(ne * nd * nc = n^3 * cde = kn^3\).

    Conclusion: The algorithm computes with \(\mathcal{O}(n^3)\) time complexity.

    Mathematically correct estimate

    The mathematically correct estimate is represented by the function \(T(n)\).

    Define the function as: \[T(n) = a + \sum_{i=0}^{n-1} f_3(n) = a + \sum_{i=0}^{n-1} (b + \sum_{j=i}^{n-1} (c + \sum_{k=i}^{j} d))\] Each loop in the method corresponds to one sum or one method \(f_i\) where the lowest index is the innermost sum/loop.

    Define the other functions: \[\begin{aligned} f_1(j,i) &=\sum_{k=i}^j d = d \sum_{k=i}^j 1 = d(1 + j - i) = d + dj - di,\\ f_2(n,i) & = \sum_{j=i}^{n-1} (c + f_1(j,i)) \\ & = c\sum_{j=i}^{n-1} 1 + d\sum_{j=i}^{n-1} 1 + d\sum_{j=i}^{n-1} j - di\sum_{j=i}^{n-1} 1 \\ & = (c + d)\sum_{j=i}^{n-1} 1 + d(\frac{n(n-1)}{2} - \frac{i(i-1)}{2}) - di(n-i) \\ & = (c + d)\sum_{j=i}^{n-1} 1 + \frac{d}{2}n(n-1) + \frac{d}{2}i^2 + \frac{d}{2}(1-2n)i,\\ T(n) & = a + f_3(n) = a + \sum_{i=0}^{n-1} (b + f_2(n,i))\\ & = a + b\sum_{i=0}^{n-1} 1 + \sum_{i=0}^{n-1} f_2(n,i)\end{aligned}\]

    Some substitution:

    \[\begin{split} \sum_{i=0}^{n-1} f_2(n,i) & = (c+d)\sum_{i=0}^{n-1} (\sum_{j=i}^{n-1} 1) + \frac{d}{2}n(n-1)\sum_{i=0}^{n-1} 1 + \frac{d}{2}\sum_{i=0}^{n-1} i^2 + \frac{d}{2}(1-2n)\sum_{i=0}^{n-1} i \\ & = (c+d)\sum_{i=0}^{n-1} (n-i) + \frac{d}{2}n^2(n-1) + \frac{d}{2}(\frac{n(n-1)(2n-1)}{6}) + \frac{d}{2}(1-2n)\frac{1}{2}n(n-1) \\ & = \frac{1}{2}((c+d)(n^2 + n) + d(n^3 - n^2) + d(\frac{n^3}{3} - \frac{n^2}{2} + \frac{n}{6}) + \frac{d}{2}(1-2n)(n^2-n)) \end{split}\]

    After some simplification, we are left with: \[\begin{aligned} \sum_{i=0}^{n-1} f_2(n,i) & = \frac{d}{6}n^3 + (\frac{c}{2}+\frac{d}{2})n^2 + (\frac{c}{2}+\frac{d}{3})n, \\ T(n) & = \frac{d}{6}n^3 + (\frac{c}{2}+\frac{d}{2})n^2 + (b + \frac{c}{2}+\frac{d}{3})n + a, \\\end{aligned}\]

    Estimating constants:

    1. method scope, outside all loops:
      \(a = initMaxSum + outerLoopInit + outerLoopCondExtra + return = 1 + 1 + 2 + 1 = 5\)

    2. outer loop:
      \(b = forLoopTurn + middleLoopInit + middleLoopCondExtra = 3 + 1 + 2 = 5\)

    3. middle loop:
      \(c = forLoopTurn + initThisSum + innerLoopInit + innerLoopCondExtra + branch = \\ 3 + 1 + 2 + 8 = 14\)

    4. inner loop:
      \(d = forLoopTurn + addThisSum = 3 + 1 = 4\)

    Finally, substitute constants: \[T(n) = \frac{2}{3}n^3 + 9n^2 + \frac{40}{3}n + 5) \in \mathcal{O}(n^3)\]