INDA - Uppgift 9 2005/2006


Algoritmuppgift (= uppgift 9)
Studera avsnitt 2.3-2.4 i algoritmboken. Lämna in skriftliga lösningar till följande uppgifter (i algoritmboken).

  • 2.9(a)-2.9(d)
  • 2.11
  • 2.14
  • 2.16
  • Vilka av följande påståenden är sanna? Motivera ditt svar.
    • n(n + 1) / 2 = O(n^3)
    • n(n + 1) / 2 = O(n^2)
    • n(n + 1) / 2 = Theta(n^3)
    • n(n + 1) / 2 = Omega(n)
  • Ordna följande funktioner enligt asymptotisk storlek (från den minsta till den största):
    (n-2)!, 5 log(n+100)^10, 2^(2n), 0.001n^4 + 3n^3, (log n)^2, 3^n, n^(1/3).
Den här delen av uppgiften ska som vanligt lämnas till din övningsledare på övningen 24/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.35-7.42.

Uppgiften ska redovisas i två steg. En första spelbar version ska vara klar senast 24/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 30/11.



Stefan Nilsson
2005-10-18