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 1.2 och 1.4 i algoritmboken.

Skriftlig uppgift

• Lägg till en implementation av insättningssortering i projektet sort som finns i Nadas filsystem i katalogen /info/2D1345/inda06/sort/. 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.
• Repetera avsnitt 1.1.4 i algoritmboken och beräkna sedan tidskomplexiteten för följande algoritm genom att ställa upp och lösa en rekursiv ekvation.

  /**
   * Computes n! Precondition: 0 <= n <= 20.
   * (20! < 2^63 - 1, the maximum value of a long.)
   */
  public long factorial(int n) {
      if (n == 0) {
          return 1;
      } else {   // n > 0
          return n*factorial(n - 1);
      }
  }
  

• Gör uppgift R-1.7 i algoritmboken.
• Gör uppgift R-1.10, R-1.12 och R-1.13 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)
• Ordna följande funktioner enligt asymptotisk storlek (från den minsta till den största):
  (n-2)!, 5 log(n+100)^10, 2^(2n), 0.001n^4 + 3n^3, (log n)^2, 3^n, n^(1/3).