Uppgift 9

Algoritmuppgift (=uppgift 9)

Ge en tajt O-uppskattning, som funktion av n, av värstafallstiden för följande fem loopar:

Algorithm Loop1(n):
   a = 0
   for i = 1 to n
      a += i

Algorithm Loop2(n):
   b = 1
   for i = 1 to 4n
      b++

Algorithm Loop3(n):
   c = 1
   for i = 1 to n²
      c--

Algorithm Loop4(n):
   d = 5
   for i = 1 to 3n
      for j = 1 to i
         d = d + j

Algorithm Loop5(n):
   e = 5
   for i = 1 to n²
      for j = 1 to i
         e = e + j

Förklara varför (n+1)³ är O(n³). Använd dig av följande definition: f(n) är O(g(n)) om det finns positiva konstanter c och n₀ så att f(n) ≤ cg(n) för alla n ≥ n₀.
StableMarriage.java innehåller en implementation av algoritmen för stabil matchning från läroboken. Studera programmet noga och ge en uppskattning av körtiden för metoden stable(). Det räcker att undersöka algoritmens värstafallsbeteende. Ange svaret som en funktion av problemstorleken n och använd O-notation. Ange också hur du har mätt storleken n på problemet. Vilka grundläggande operationer valde du att räkna? Ge en detaljerad beskrivning av hur du har resonerat.

Den här delen av uppgiften ska som vanligt lämnas till din övningsledare på övningen 27,28/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.

Slutuppgift i programmering (=uppgift 11)

Slutuppgiften på den här delen av kursen är att skriva ett äventyrsspel som bygger på projektet i kapitel 7. Du ska implementera minst fyra, men gärna fler, av förslagen i uppgift 7.42-7.49.

Uppgiften ska redovisas i två steg. En första spelbar version ska vara klar senast 27,28/11. Då ska du låta någon annan provspela ditt spel och du ska prova någon annans program. Ni ger kommentarer till varandra och därefter förbättrar ni spelet. När båda är nöjda så är det dags att lämna in koden, på papper, till er övningsledare. Sista inlämningsdag är i samband med den näst sista övningen 4,5/12.