Uppgift 8

Uppgiften ska lämnas till din övningsledare på övningen 19/11.

För godkänt måste du ha gjort samtliga deluppgifter. Det är tillåtet att göra enstaka fel och misstag men det är viktigt att du försöker lösa samtliga uppgifter.

Hemuppgift

Studera kapitel 6 i programmeringsboken. Den här gången finns det inga obligatoriska uppgifter från boken men det är naturligtvis fritt fram att göra uppgifterna på egen hand. Glöm inte heller att utnyttja labbar och övningar för frågor och diskussioner. Du får också gärna tjuvstarta med slutuppgiften i programmering som du hittar i nästa veckas uppgift.

Studera texterna om tidskomplexitet och asymptotisk notation.

Skriftlig uppgift

• Lägg till en implementation av följande sorteringsalgoritm i projektet sort.jar. Glöm inte att uppdatera testkoden så att den även testar den nya algoritmen. Lämna in en utskrift av den modifierade klassen Sort.

  Algorithm insertionsort(A, n):
     Input: An array A storing n integers.
     Output: An array with the same integers in ascending order.
     for i = 1 to n-1
        // Loop invariant: A[0..i-1] is sorted.
        Move A[i] to its correct position
        within the subarray A[0..i]
  

• I avsnittet tidskomplexitet finns en algoritm som kastar om ordningen på elementen i en vektor på kvadratisk tid. Hitta på en algoritm som gör samma sak, men på linjär tid. Beskriv din algoritm både i ord och i pseudokod.
• 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)).
  • f₁(n) = n^1.5
  • f₂(n) = 10ⁿ
  • f₃(n) = n log n
  • f₄(n) = n +100
  • f₅(n) = 2ⁿ
• Vilka av följande påståenden är sanna? Motivera ditt svar.
  • n(n + 1) / 2 = O(n³)
  • n(n + 1) / 2 = O(n²)
  • n(n + 1) / 2 = Θ(n³)
  • n(n + 1) / 2 = Ω(n)
• 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.
• Ge ett exempel på en positiv funktion f(n) sådan att f(n) varken är O(n) eller Ω(n).