Hemtal 2

A) Komplexitet

Läs om Algorithm Analysis i kursboken

1. Ordna följande funktioner efter hur snabbt dom växer:
   n, n2, nlog(n), nlog(n2), 5000n, n3, n2log(n)
2. Ett matrisproblem tar tid T(n)=k*n3 att lösa, där n är matrisens storlek. Om n ökar med en faktor tio, kan vi då kompensera det genom att köpa en dator som är tio gånger snabbare?
   
3. Vad innebär det att en algoritm är O(1)?
   

B) Rekursion

Läs om Tornen i Hanoi i kapitlet Recursion i kursboken

1. Vad är den rekursiva tanken?
2. Vad är basfallet?
3. Hur många flyttar behövs med 5 ringar?

C) Träd

Läs kapitlet Trees i kursboken

1. Rita upp ett binärt träd med åtta noder.
2. Markera vilka noder som är löv
3. Visa vilka noder som tillhör vänster delträd.
4. Vad är höjden för ditt träd?

---

Hemtalet tas med till övning 2 (5 september) och rättas där! Den som gjort uppgiften ska skriva sitt namn och personnummer överst till höger på alla blad.

Den som rättar ska skriva sitt namn och personnummer längst ner till vänster på första bladet, samt antal poäng.