Till KTH:s startsida Till KTH:s startsida

Hemtal 1

A) Träd

Läs kapitlen Trees och Implementation i kursboken

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.

B) Komplexitet

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.

Administrator Linda Kann created page 10 September 2013

Linda Kann tagged with hemtal 1. 10 September 2013

commented 19 September 2013

Hej Linda,

I have asked you after the last lecture if it is still possible to hand in my sollutions to the Hemtal1 ,and you said i can still upload it, because you reopened the Hand In Function. But somehow it is still not possible for me to upload it.

Administrator commented 19 September 2013

Now I've tried to fix the problem - please try again!