ROUGH DRAFT authorea.com/6669
Main Data History
Export
Show Index Toggle 0 comments
  •  Quick Edit
  • Algorithms - Lab 3, Problem 1

    Introduction

    This is a hand-in written by Group 7 (FIRE) for the Algorithms course (TIN092) at Chalmers University of Technology.

    Group 7 consists of:

    • Mazdak Farrokhzad

      • 901011-0279

      • twingoow@gmail.com

      • Program: IT

    • Niclas Alexandersson

      • 920203-0111

      • nicale@student.chalmers.se

      • Program: IT

    a) Complexity

    Our algorithm for calculating a numerical value is, in pseudocode:

    Computes the numerical value for C(n) for average quicksort complexity Input: n is the size of the problem. C(n): if n = 0 then: return 1 end if sum <- 0 for i: 0 .. n-1 do: sum <- sum + C(i) end for return 2/n * sum + n end

    The complexity of this algorithm in turn is:

    \[\begin{aligned} T(n) = \begin{cases} c_0 & \text{if } n = 0\\ c_1 + \displaystyle\sum_{i = 0}^{n-1} T(i) & \text{if } n > 0 \end{cases}\end{aligned}\]

    \(T(n-1), n > 1\) is, using the recursive definition above: \[T(n-1) = c_1 + \sum_{i = 0}^{n-2} T(i)\]

    Using this, we expand \(T(n)\) and get:

    \[\begin{aligned} T(n) &= c_1 + \sum_{i = 0}^{n-2} T(i) + T(n-1)\\ &= 2T(n-1)\end{aligned}\]

    Thus we get:

    \[\begin{aligned} T(n) = \begin{cases} c_0 & \text{if } n = 0\\ 2^{n-1}(c_0 + c_1) & \text{if } n > 0 \end{cases}\end{aligned}\]

    Meaning \(T(n) \in \mathcal{O}(2^n)\).

    b) Dynamic programming

    The execution tree for \(C(4)\) is:

    [->, >=stealth’,shorten >=1pt,auto,node distance=3.5cm,semithick] [.\(C(1)\) \(C(0)\) ] [.\(C(2)\) \(C(0)\) [.\(C(1)\) \(C(0)\) ] ] [.\(C(3)\) \(C(0)\) [.\(C(1)\) \(C(0)\) ] [.\(C(2)\) \(C(0)\) [.\(C(1)\) \(C(0)\) ] ] ] ]

    \label{fig:execution-tree}

    The optimized version - using dynamic programming - of the algorithm in a) becomes:

    Computes the numerical value for C(n) for average quicksort complexity Input: n is the size of the problem. Memory: initialize mem[n] with 0 C(n): if mem[n] = 0 then: if n = 0 then: mem[n] <- 1 end if sum <- 0 for i: 0 .. n-1 do: sum <- sum + C(i) end for mem[n] <- 2/n * sum + n end if return mem[n] end

    From the outset, it is obvious that the memory complexity is \(\mathcal{O}(n)\)

    The cost of initializing the memory is: \(n\) The algorithm will do \(n\) fills.

    [>=stealth,shorten >=2pt,thick]

    = [draw,anchor=center,minimum size=3em, thin]

    in 0,1,2,3,4 at (0,-) (m) \(m_\m\); (5.9/1.5 - /1.5,-) – +(0,); ; in 1,2,3,4

    (5.9/1.5 - /1.5, -) circle(0.15em);

    in 1, ..., (5.9/1.5 - /1.5, -+ 0.95) – +(-0.5,0);

    \label{fig:lookup-calls}

    It will also do: \(i - 1\) lookup for each \(i\), so the total complexity is:

    \[\begin{aligned} T(n) &= n + n + \sum_{i=0}^{n-1} \left[i-1\right]\\ &= 2n + \sum_{i=0}^{n-1} i + \sum_{i=0}^{n-1} 1\\ &= 3n + \frac{n(n-1)}{2}\\ &= \frac{5n + n^2}{2}\\ &\in \mathcal{O}(n^2) \end{aligned}\]

    c) Linear algorithm

    Computes the numerical value for C(n) for average quicksort complexity Input: n is the size of the problem. Memory: initialize sum with 1 C(n): if n = 0 then: return 1 end if sum <- 1 for i: 1 .. n-1 do: sum = sum + 2/i * sum + i end for return 2/n * sum + n end

    The complexity of this algorithm is:

    \[\begin{aligned} T(n) &= c_0 + \sum_{i=1}^{n-1} c_1\\ &= c_0 + c_1 + c_1 n\\ &\in \mathcal{O}(n) \end{aligned}\]