Uppgift 8

Uppgiften ska lämnas till din övningsledare på övningen 20,21/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 avsnitt 2.2-2.3 i algoritmboken.

Skriftlig uppgift

• Lägg till en implementation av insättningssortering i projektet sort.zip. Glöm inte att uppdatera testkoden så att den även testar den nya algoritmen.

  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
        // Loop invariant: A[0..i-1] is sorted.
        Move A[i] to it's correct position
        within the subarray A[0..i]
  

  Lämna in en utskrift av den modifierade klassen Sort.
• Gör uppgift 2.3 i algoritmboken.
• Vilka av följande påståenden är sanna? Motivera ditt svar.
  • n(n + 1) / 2 = O(n^3)
  • n(n + 1) / 2 = O(n^2)
  • n(n + 1) / 2 = Theta(n^3)
  • n(n + 1) / 2 = Omega(n)
• Ge ett exempel på en positiv funktion f(n) sådan att f(n) varken är O(n) eller Omega(n).
• Gör uppgift 2.6 i algoritmboken.