Uppgift 8

Uppgiften ska lämnas till din övningsledare på övningen 16/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 7 (uppl 4: kapitel 6) i programmeringsboken.

• Uppl 5: Gör uppgift 7.15-7.19 och lämna in kompletta utskrifter av testklasserna CommentsTest och SalesItemTest.
• Uppl 4: Gör uppgift 6.16-6.20 och lämna in kompletta utskrifter av testklasserna DayTest och AppointmentTest.

Studera texterna om tidskomplexitet och asymptotisk notation.

• Lägg till en implementation av följande sorteringsalgoritm i BlueJ-projektet sort.jar. Glöm inte att uppdatera testkoden så att den även testar den nya algoritmen. Lämna in utskrifter av de modifierade klasserna Sort och SortTest.

  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 och förklara varför den tar linjär tid.
• 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).