bild
Skolan för
elektroteknik
och datavetenskap

Uppgift 7

Uppgiften ska lämnas till din övningsledare på övningen 12/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 5 i programmeringsboken. Den här gången är det färre obligatoriska uppgifter och du väljer själv hur du vill studera kapitlet. Jag rekommenderar att du gör de uppgifter som du tycker att du har nytta av. Om du undrar över något så är det naturligtvis fritt fram att fråga på övningen eller labben.

Studera avsnittet om algoritmer i algoritmkursen.

Skriftlig uppgift

  • Gör uppgift 5.47-5.57 i programmeringboken och lämna in lösningen i form av en utskrift av den modifierade klassen BallDemo.
  • Lämna in lösningar till uppgift 5.58-5.63 i programmeringsboken.
  • Tiden för att exekvera följande algoritm beror både på antalet element n och ordningen på elementen. Vilken tid (räknat i antalet jämförelser, dvs antalet ">"-operationer) tar algoritmen som minst respektive som längst för ett visst givet n.
    Algorithm bubblesort(A, n):
       Input: An array A storing n integers.
       Output: An array with the same integers in ascending order.
       isReady = false
       while not isReady
          for i = 0 to n - 2
             if A[i] > A[i+1] then
                swap(A[i], A[i+1])
          isReady = true
          for i = 0 to n - 2
             if A[i] > A[i+1] then
                isReady = false
    
  • Låt T(n) vara tiden i mikrosekunder för att lösa ett problem av storlek n med en viss algoritm. För varje funktion T(n) och varje tid t i tabellen, ange det största värdet på n för vilket algoritmen kan lösa problemet på tiden t.
        T(n)   1 sekund    1 minut    1 timme    1 dag    1 år
    ------------------------------------------------------------
      log(n)
          n
    n log(n)
        n^2
        n^3
        2^n
         n!
    
    Logaritmerna är i basen 2. Ange n med 1-2 siffrors noggrannhet.
Copyright © Sidansvarig: Stefan Nilsson <snilsson@nada.kth.se>
Uppdaterad 2010-10-07