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 n2
        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 n2
        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₀.
• Studera följande algoritm och ge en uppskattning av körtiden. Ange svaret som en funktion av problemstorleken och använd O-notation. Beskriv i detalj hur du har resonerat. Vilka grundläggande operationer valde du att räkna? Hur påverkas körtiden om alla element i vektorn är lika?

  Algorithm Reverse(a):
      Input: An array a.
      Output: The same array with elements reversed.
      n = a.length
      for i = 0 to n/2
          if a[i] != a[n-1-i]
              Swap the elements a[i] and a[n-1-i]
      return a
  

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