1)
 a)
  Skapa en array med buckets:

     0 1 2 3 4 5 6 7 8 9

  Läs in elementen ett och ett och lägg datadelarna i inläsningsordning i
  respektive nyckeldels bucket:

     0 1 2 3 4 5 6 7 8 9
       E   B   A D     C
           F   I G
                 H

  Gå igenom bucketarrayen i ordning och mata ut motsvarande nyckel-data-par:

    1:E 3:B 3:F 5:A 5:I 6:D 6:G 6:H 9:C

 b)O(n log n).
   Vid Bucketsort utnyttjar man att man har en begränsad (liten) mängd nycklar
   och kan stoppa in elementen på rätt plats direkt.

 c)
  Om element med samma nyckel (t.ex. 3:B och 3:F i a)) kommer i samma ordning i
  sorterad utdata som i osorterad indata.
  Bubblesort är stabil eftersom man där alltid jämför närliggande element och
  kan välja att swappa eller inte, och då inte byter plats på element med
  sammam nyckel.

2)
 a)
  f(n) tillhör O(g(n)) om f(n) <= cg(n) för alla n>=n_0, c och n_0 konstanter.

 b)
   lim 2^n/n² går mot oändligheten, är alltså inte < oo, alltså bevisat.
  n->oo

 c)
  Om T_a(n)=n² och T_b(n)=1000n så är T_A(1)=1 och T_b(1)=1000.

3)
 a)
  met1, ärvd från A
  met2, ärvd från A
  met3, definierad i B
  met4, definierad i B

 b)
  Om typerna är olika så överlagras metoderna och båda kan användas.
  Om typerna är lika så skymmer C-metoden den andra.

 c)
  En abstrakt metod har ingen kropp.
  Klasser som ärver A och som inte är abstrakta måste ge metoden en kropp.
  Det kan användas för att garantera att vissa metoder alltid finns, för att
  beskriva generella företeelser som inte kan beskrivas p åett generellt sätt
  (t.ex. rita ett geometriskt objekt).

 d)
  Varje objekt av klassen A innehåller/består av att antal objekt av klassen B.
  Eftersom C är en sorts A (ärver A) så gäller det även för C.

4)
 a)
  R: -
  S: fullt, fullständigt
  T: fullt, perfekt

 b)
          8
         / \
        /  12
       /   / \
      /   9  15
     4     \
    / \    11
   2   5   /
          10

 c)
  Ersätt 8 med det minsta elementet>8 (dvs 9) borttaget ur delträdet t.h. om 8:
          9
         / \
        /  12
       /   / \
      /  10  15
     4     \
    / \    11
   2   5

 d)
  Pre: 8 4 2 5 12 9 11 10 15
  In: 2 4 5 8 9 10 11 12 15