Opgave 1 ***********************************************************

   i) T(n) = Theta(n^2) via Master Theorem Case III

  ii) T(n) = Theta(log(n)n^2) via Master Theorem Case II

 iii) T(n) = Theta(n^(log_3(10)) via Master Theorem Case I


Opgave 2 ***********************************************************

   i) Falsk

  ii) Sandt

 iii) Falsk

  iv) Sandt

   v) Falsk

  vi) Sandt

Opgave 3 ***********************************************************

** Spørgsmål a:

A: 1 2 5 4 2 6 6 9 8 7

** Spørgsmål b:

H: 3 45 x 59 x 23 38 53 60 72 87

** Spørgsmål c:

H: 4 1 5 2 5 5 8 7


Opgave 4 ***********************************************************

** Spørgsmål a:

Rækkefølge af knuder udtaget af køen:

  a, i, b, d, h, c, g, f, e

Afstandsværdier:

  a.d = 0, b.d = 2, c.d = 3, d.d = 2, e.d = 5,
  f.d = 4, g.d = 3, h.d = 2, i.d = 1 

** Spørgsmål b:

Rækkefølge af knuder udtaget af prioritetskøen:

  a, i, b, c, h, d, g, f, e

Afstandsværdier:

  a.d = 0, b.d = 13, c.d = 15, d.d = 25, e.d = 58,
  f.d = 43, g.d = 33, h.d = 24, i.d = 7 

** Spørgsmål c:

Rækkefølge af knuder udtaget af prioritetskøen:

  a, b, c, i, f, h, g, d, e

MST-kanter:

  (a,b), (b,c), (b,i), (i,f), (a,h), (h,g), (c,d), (i,e)

Opgave 5 ***********************************************************

** Spørgsmål a:

   i) Theta(n^4)
  ii) Theta(n)
 iii) Theta(n^2)
  iv) Theta(n log n)
   v) Theta(n^2)

** Spørgsmål b:

 C: 0 1 2 4 4 9 9 10

Opgave 6 ***********************************************************

   i) Er en løkke-invariant

  ii) Er ikke en løkke-invariant.

 iii) Er ikke en løkke-invariant.

  iv) Er en løkke-invariant.

   v) Er ikke en løkke-invariant.

Opgave 7 ***********************************************************

** Spørgsmål a:

   1  2  3  4
   2  5  7 10
   3  8 11 16
   5 10 17 22

** Spørgsmål b:

ChocolateBestCut(n,m,P)
   create new n x m size array C
   for (i=1;i<=n;i++)
       for (j=1;j<=m;j++)
          FillC(i,j,C,P)
   return C[n,m]

FillC(i,j,C,P)
    maxSoFar = P[i,j]
    if i>1 and j=1
        for (s=1;s<i;s++)
            maxSoFar = max(maxSoFar,C[s,1] + C[i-s,1])
    else if i=1 and j>1
        for (t=1;t<j;t++)
            maxSoFar = max(maxSoFar,C[1,t] + C[1,j-t])
    else if i>1 and j>1
        for (s=1;s<i;s++)
            maxSoFar = max(maxSoFar,C[s,j] + C[i-s,j])
        for (t=1;t<j;t++)
            maxSoFar = max(maxSoFar,C[i,t] + C[i,j-t])
    C[i,j] = maxSoFar

Algoritmen bruger Theta(nm max(n,m)) tid og Theta(nm) plads.

** Spørgsmål c:

Vi argumenterer først for det generelle tilfælde i>1 og j>1.

Se på en optimal opklipning OPT. Enten 1) er den blot pladen selv (ingen
opklipning), eller også 2) er der lavet mindst eet klip.

I case 2) efterlader dette to delplader, som eventuelle yderligere klip
i OPT bryder ned i mindre dele. Denne nedbrydning må være optimal for
hver af disse to delplader, for ellers kunne OPTs handlinger erstattes
af optimale opbrydninger af disse to delplader, og derved selv bliver
bedre.

For alle muligheder for placering af første cut ser vi på summen af
værdierne af optimale opklipninger af de to opståede delplader. Blandt
disse tal møder vi (pga. ovenstående) værdien af OPT, hvis vi er i case
2). Vi ser også på P[i,j], hvilket er værdien af OPT, hvis vi er i case
1).

Uanset om vi er i case 1) eller 2) gælder:

 a) Vi ser kun på værdier af mulige opklipninger, så vi ser kun på tal
    som er <= OPTs værdi.

 b) Blandt de tal, vi ser på, findes værdien af OPT.

Derfor er OPTs værdi lig maximum af de tal, vi ser på. Dette maksimum er
netop hvad fjerde linie i den rekursive formel beregner.

For tilfældene hvor i=1 og/eller j=1 er argumentet det samme, der er
blot færre muligheder for placering af første klip, hvilket giver
anledning til de tre første linier i den rekursive formel.