Skip to content

Latest commit

 

History

History
101 lines (71 loc) · 3.45 KB

ovn2.md

File metadata and controls

101 lines (71 loc) · 3.45 KB

Övning 2 grudat22

Fredag 8/4 kl 08.00

Vid övningen ska du vara beredd att muntligt presentera och diskutera dina lösningar och din programkod.

  • Gör (minst) en fil per uppgift och lägg filerna i katalogen username-ovn2 i organisationen grudat22 på KTH GitHub.
  • Utgå från mallarna i /grudat22/ovn0/.
  • Lösningar ska vara inlämnade före deadline.

Du väljer själv vilket av programspråken Python, Go eller Java du vill använda. Observera att all kod på den här kursen ska dokumenteras och testas.

Gör antingen uppgift 2.3 eller 2.5, inte båda.

Betyg G

2.1 Ordo-notation

Ordna funktionerna i följande lista i växande ordning med avseende på tillväxtstakt. Funktionen f(n) ska alltså komma före funktionen g(n) i listan om f(n) är O(g(n)).

  • f1(n) = n1.5
  • f2(n) = 10n
  • f3(n) = n log n
  • f4(n) = n +100
  • f5(n) = 2n

Vilka av följande påståenden är sanna? Motivera dina svar.

  • n(n + 1) / 2 = O(n3)
  • n(n + 1) / 2 = O(n2)
  • n(n + 1) / 2 = Θ(n3)
  • n(n + 1) / 2 = Ω(n)

Video om ordo-notation

2.2 Prefixsumma

Indata är en heltalsvektor A med n element. Vi vill beräkna en vektor B, där B[i] = A[0] + A[1] + ... + A[i]. Här är en enkel algoritm som löser problemet.

for i = 0 to n-1
    Add the numbers A[0] thru A[i].
    Store the result in B[i].

  • Beräkna tidskomplexiteten för denna algoritm och uttryck den på formen O(f(n)), där funktionen f(n) är så liten och enkel som möjligt.

  • Visa att tidskomplexiteten också är Ω(f(n)).

  • Hitta på en algoritm med bättre asymptotisk tidskomplexitet. Beskriv algoritmen i pseudokod och ange dess tidskomplexitet med Θ-notation.

Video om tidskomplexitet

2.3 Binärt sökträd

Implementera ett obalanserat binärt sökträd som lagrar textsträngar.

  • Använd koden för den länkade listan i övning 1 som mall.
  • Gör ett tydligt API med publika dokumenterade metoder.
  • Skriv utförlig testkod.

Följande metoder ska finnas:

  • Skapa ett tomt träd.
  • Lägg till ett nytt element.
  • Returnera antalet element i trädet.
  • Returnerar en sträng med alla element i bokstavsordning.

Ange tidskomplexiteten i värstafall för samtliga operationer.

Tips och råd (Video)

Betyg VG

2.4 En ovanlig funktion?

Ge ett exempel på en positiv funktion f(n) sådan att f(n) varken är O(n) eller Ω(n).

2.5 Treap (alternativ till 2.3)

Gör uppgift 2.3 med ett randomiserat binärt sökträd i stället för ett obalanserat träd.