Skip to content

Latest commit

 

History

History
95 lines (68 loc) · 3.26 KB

ovn2.md

File metadata and controls

95 lines (68 loc) · 3.26 KB

Övning 2 grudat19

Fredag 5/4 kl 10.00

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

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. Vid övningen ska du vara beredd att muntligt presentera och diskutera dina lösningar och din programkod.

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)

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 O-notation.

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.

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.