Hemtal 1

Rita upp det binära sökträd vi får om vi i tur och ordning stoppar in följande tal:
78 24 28 6 89 38 64 26

Besvara sedan följande frågor:

Betyg E:

Hur många noder har trädet?
Hur många noder har vänster delträd?
Vad är trädets höjd?
Vilket tal ligger i roten?
Vilka tal ligger i löv?
Vilka tal är barn till 28?
Vilket tal är förälder till 64?
Hur ser en inorderutskrift av trädet ut?
Hur många jämförelser måste man som mest göra vid sökning i trädet?
Hur många jämförelser måste man som mest göra i ett balanserat binärträd med n noder?
Betyg C:
Hur ser en preorderutskrift av trädet ut?
Hur ser en postorderutskrift av trädet ut?
Man får snabb sökning både med binärsökning i en lista och sökning i ett binärt sökträd. Vilka föredelar resp nackdelar kan du komma på med respektive lagringssätt?
Betyg A:
Kan man skriva en funktion för att ta reda på om trädet är balanserat? Formulera en rekursiv tanke och ett basfall för en funktion som ska returnera True om trädet är balanserat, False annars.

Läs hela kapitlet Analysis i kursboken

Besvara sedan följande frågor:

Betyg E:

Vad innebär O(1)?
Ordna följande funktioner efter hur snabbt dom växer:
\(n\), \(n^{2}\), \(n\log{n}\), \(n\log{n^2}\), \(5000n\), \(n^{3}\), \(n^{2}\log {n}\)
Vilken tidskomplexitet har metoden sort i Pythons listor?

Betyg C:

Skriv ett par rader kod som har kvadratisk komplexitet. Glöm inte att berätta vilken variabel som representerar indatas storlek.
Varför spelar det ingen roll vilken logaritm man använder i Ordo-uttryck?

Betyg A:

Ett problem tar tid T(n)=k*n*log(n) att lösa, där n är indatas 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?
Förklara, och illustrera med ett räkneexempel.

Hemtalet lämnas in på kurswebbsidan (under Inlämningsuppgifter) senast på söndag 15 september kl 20.00.