|
INDA - Uppgift 7 2006/2007
Uppgiften ska lämnas till din övningsledare på övningen 26,27/10.
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 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.
-
Översätt psesudokoden på sidan 7 i algoritmboken till
en metod skriven i Java. Metoden ska som vanligt dokumenteras med
en /**...*/-kommentar.
-
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 R-1.2, R-1.3, C-1.17 i algoritmboken.
-
Gör uppgift C-1.8a i algoritmboken. Vilken blir värstafallstiden
för att avkoda ett 100-bitars meddelande om man optimerar algoritmen
så att den endast testar udda heltal p,
1 < p < r1/2?
Stefan Nilsson
2006-10-16
|