Warning! This is the 2012 course's website! You probably want the current course website.

Innehållförteckning veckovis:

vecka 11: introduktion, komplexitet, listor
vecka 12: stackar, köer, rekursion
vecka 13: binära sökträd, prioritetsköer, hashtabeller
vecka 16: självbalanserande träd
vecka 17: datastrukturer i Haskell

Här ligger lösningsförslag på en del av övningsuppgifterna. OBS! Tjuvkika inte, utan gör övningarna först och titta sen. Tänk också på att ibland finns det flera möjliga lösningar, och jag har bara angett en av dem. Det kan alltså vara fullt möjligt att din lösning är korrekt, även om den är annorlunda än min.

Vecka 11

Kapitel 1: Introduktion

Inga lösningsförslag på denna del.

Avsnitt 2.4: Komplexitet

Se kursboken och dess studenthemsida.
I stigande ordning: log n, 4n, n log n, 5n² + n, 3n³, n⁴
Om 2ⁿ = 1,5768 · 10²³, så gäller även att log₂ 2ⁿ = log₂ 1,5768 · 10²³. Men eftersom log₂ 2ⁿ = n · log₂ 2 = n, så får vi alltså:
n = log₂ 1,5768 · 10²³ = log₂ 1,5768 + log₂ 10²³ = log₂ 1,5768 + 23 · log₂ 10 = 0,657 + 76,404 = 77,061.
Svaret blir då att det största n som kan beräknas är 77.
Antag att beräkningstiden är 1 millisekund för "varje n". Vi får då följander tider: Nedan ges tillväxtstorleken för ett antal algoritmer. Vilka kan lösas inom rimlig tid om antal indata = 50?
1. 10 · 2⁵⁰ ms = 1,12 · 10¹³ s = 1,3 · 10⁸ dagar = 3,6 · 10⁶ år
2. 10000 · log₂ 50 ms = 56,4 sekunder = knappt en minut
3. 100000 · 50 ms = 5000 s = 1,4 timmar
4. 10 · 50! ms = 3,04 · 10⁶² s = 3,5 · 10⁵⁷ dagar = 9,6 · 10⁵⁴ år
Skriv följande funktioner i Ordo-notation:
1. 34x + x² = O(x²)
2. 1x + 2x + 3x + 4x + 5x + 6x + 7x = O(x)
3. 10⁴⁰⁰⁰x + 0,005 x² + 103/x³ = O(x²)
4. 10 log₂ x + 2 log₁₀ x = O(log x)
5. 2^x + 10^x = O(10^x)
6. (x–2) (x–1) x = O(x³)
Ange komplexiteten för följande KWArrayList-metoder, såsom de är definierade i avsnitt 2.3 i kursboken:
1. add(E) = O(1)
2. add(int,E) = O(n)
3. get(int) = O(1)
4. set(int,E) = O(1)
5. remove(int) = O(n)

Kapitel 2: Listor

Se kursboken och dess studenthemsida.
O(n), om vi inte har en pekare till sista elementet också, i vilket fall det blir O(1).
O(1)
Detta är en delmängd av Queue-gränssnittet. En kö kan implementeras som en enkellänkad lista där huvudet innehåller två pekare: en som pekar på första elementet och en som pekar på sista elementet. Ett annat alternativ är som en cirkulär ArrayList. Se även avsnitt 4.1 och 4.3 i kursboken.
Detta är en delmängd av Deque-gränssnittet. En deque kan implementeras som en dubbellänkad lista. För att kunna ta bort sista elementet så måste vi snabbt kunna hitta nästsista elementet, och det kan vi bara om sista elementet har en pekare bakåt. Ett annat alternativ är som en cirkulär ArrayList. Se även avsnitt 4.3 och 4.4 i kursboken.
Denhär uppgiften får du fundera mer på. Sen kan du tjuvkika i avsnitt 6.5 i kursboken.
Bli inspirerad av avsnitt 3.2: Testing Expressions for Balanced Parentheses. Du behöver en stack för att hålla koll på hur många nästade parenteser du har läst. Men eftersom stackoperationerna är O(1), så tar varje läsning av ett tecken konstant tid. Komplexiteten för att läsa hela strängen blir då linjär O(n).
Om det inte finns olika sorters parenteser så behöver du inte ens en stack, utan det räcker med en räknare som innehåller antalet nästade parenteser.

Vecka 12

Kapitel 3: Stackar

Se kursboken och dess studenthemsida.
Jag ger ingen lösning, men ett tips är att utöka parentes-matchningen som finns i OH-bilderna om kapitel 3, stackar. Dessutom kan du titta i och bli inspirerad av kursbokens exempel på sid 171–188 om att evaluera postfix-uttryck, att konvertera infix- till postfixuttryck, och att konvertera parenteser.
Se ovan.

Kapitel 4: Köer

Se kursboken och dess studenthemsida.
Använd en kö med trädnoder som mellanliggande struktur, dvs. Queue<TreeNode<E>>. Som slutresultat använder vi en lista med element, dvs List<E>. Här är pseudokod:
- Börja med att stoppa in rotnoden i kön.
- Nollställ listan.
- Repetera ända tills kön är tom:
  - Tag ut första noden ur kön.
  - Om noden inte är tom:
    - Lägg till nodens data till listan.
    - Lägg till nodens vänstra samt högra barn till kön.
Du kan använda ett cirkulärt fält, samt två variabler: En som pekar på början av kön, och en annan som pekar på slutet.

Kapitel 5: Rekursion

Se kursboken och dess studenthemsida.
Här kan du utgå från parentes-algoritmen som finns i OH-bilderna för rekursion. Och kursbokens stack-exempel på sid 171–188.

Vecka 13

Kapitel 6: Träd och sökträd

Se kursboken och dess studenthemsida.
- Inorder: 1 2 3 4 5 6 7 8 9
- Preorder: 4 2 1 3 6 5 8 7 9
- Postorder: 1 3 2 5 7 9 8 6 4
Inte alls! T.ex. följande sekvenser ger alla olika binära sökträd: 123, 132, 321, 312, 213. (Den sista ger dock samma träd som sekvensen 231).

Här är ett förslag:

  public boolean add(E item) {
    Node<E> node = root;
    while (node != null) {
      int cmpResult = item.compareTo(node.data);
      if (cmpResult == 0) {
        return false;
      } else if (cmpResult < 0) {
        if (node.left == null) {
          node.left = new Node<E>(item);
          return true;
        } 
        node = node.left;
      } else {
        if (node.right == null) {
          node.right = new Node<E>(item);
          return true;
        } 
        node = node.right;
      }
    }
    return false;
  }

Om varje delträd vet hur många noder det innehåller så kan man göra ungefär såhär för att söka (fast man måste också tänka på null-noder, så det är inte helt korrekt):
```
  public E findElement(int n) {
    Node<E> node = root;
    while (true) {
      if (n <= node.left.size) {
        node = node.left;
      } else {
        n -= node.left.size;
        if (n == 1) {
          return node.data;
        } else {
          n--;
          node = node.right;
        }
      }
    }
  }
```
Koden för add(E), att lägga till element i trädet, måste uppdatera storleken i varje nod mellan roten och platsen där elementet läggs till. Det är enklast i den rekursiva varianten, eftersom vi inte vet förrän i slutet ifall elementet verkligen lades till. Efter att det rekursiva anropet har returnerat true så kan vi öka storleken på noden med 1.
Det finns flera möjligheter. Ett alternativ är att göra det i tre steg:
- Först tar vi reda på höjden h hos det vänstraste lövet.
- Sen tar vi reda på höjden h' hos det högraste lövet. Vi kontrollerar att h = h' eller h = h'+1.
- Slutligen kontrollerar vi att ingen nod har högerbarn men inget vänsterbarn. (Alternativt, att alla noder som har högerbarn också har vänsterbarn).

Avsnitt 6.5: Prioritetsköer

Se kursboken och dess studenthemsida.
(–––)
Denhär uppgiften lämnas åt studenten att lösa. I princip finns allt som behövs i kursboken och i lab 2, fast metodnamnen är annorlunda.
En heap är en specifik datastruktur (ett nivåbalanserat binärt träd med vissa egenskaper). En prioritetskö är en abstrakt struktur som kan implementeras på flera olika sätt, bl.a. som en heap. I javatermer är en prioritetskö ett interface medan en heap är en klass.
Det står i boken. Exempelträdet lagras som fältet {A,B,C,D,E,F,G,H,I,J}.
Lämnas som övning åt studenten.

Kapitel 7: Hashtabeller

Se kursboken och dess studenthemsida.
(–––)

Vecka 16

Kapitel 9: Självbalanserande sökträd

Se kursboken och dess studenthemsida.
(–––)
(–––)
1. Heap: nivåbalanserat
2. Binärt sökträd: obalanserat
3. AVL-träd: höjdbalanserat
4. Röd-svart träd: höjdbalanserat (fast höjdskillnaden kan vara större än 1)
5. 2-3-träd, 2-3-4-träd, B-träd: höjdbalanserade
6. Skiplista: i genomsnitt nodbalanserat
(–––)
Påståendet är falskt. Pröva t.ex. att bygga ett träd från elementen [1, 2] och jämför med ordningen [2, 1].
Skriv Java-kod för dubbelrotation i ett AVL-träd (ej två enkelrotationer).
1. Binärt sökträd: falskt
2. AVL-träd: sant
3. Röd-svart träd: falskt (skillnaden kan vara upp till dubbelt så många noder)
Tjuvkika på källkoden :)

Vecka 17

Datastrukturer i Haskell

  revQueue :: [a] -> [a]
  revQueue as = popQueue (makeQueue as)
    where popQueue queue | isEmpty queue = []
                         | otherwise = front queue : popQueue (dequeue queue)
          makeQueue [] = emptyQueue
          makeQueue (a:as) = enqueue a (makeQueue as)

(–––)
Antingen lägger vi till element i början av listan och tar ut i slutet (med standardfunktionerna last och init). Då blir komplexiteten för dequeue linjär.
Alternativt kan vi lägga till i slutet (med ++[a]) och ta ut i början. Då blir komplexiteten för enqueue istället linjär.

  preorder :: BST a -> [a]
  preorder t = preord t []
    where preord Empty as        = as
          preord (Node a l r) bs = a : preord l (preord r bs)

  postorder :: BST a -> [a]
  postorder t = postord t []
    where preord Empty as        = as
          preord (Node a l r) bs = postord l (postord r (a : bs))

För att listor i Haskell inte går att modifiera in-place.

Detta är det minsta icke-nivåbalanserade heapträdet jag kan komma på:

Heapträd tar mer minne, eftersom varje nod innehåller pekare till sina barn. I en heap behövs inga pekare, utan elementen kan ligga tätt ihop.
(–––)

  binSort :: Ord a => [a] -> [a]
  binSort as = inorder tree
    where tree = foldr insert emptyTree as

(–––)
(–––)
Du kan t.ex. utgå från lab 3 och modifiera main-funktionen lite grann.

  class BinarySearchTree t where
    emptyTree :: t a
    isEmpty   :: t a -> Bool
    leftSub   :: t a -> t a
    rightSub  :: t a -> t a
    rootVal   :: t a -> a
    insert    :: Ord a => a -> t a -> t a
    remove    :: Ord a => a -> t a -> t a
    inorder   :: t a -> [a]
    get       :: Ord a => a -> t a -> Maybe a

(–––)
(–––)
(–––)

DIT960 | LP4 | VT2012 Datastrukturer DV[an error occurred while processing this directive]: Lösningsförslag