Uppgift 7

Uppgiften ska lämnas till din övningsledare på övningen 13,14/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 avsnitt 1.1 och 2.1 i algoritmboken.

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.
• Gör uppgift 5.58-5.63 i programmeringsboken.
• Gör uppgift 1.1-1.2 i algoritmboken.
• Vilken tid (räknat i antalet jämförelser, dvs antalet ">"-operationer) tar följande algoritm som minst respektive som längst? Ange tiden som en funktion av 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
  

• Gör uppgift 2.1-2.2 i algoritmboken.