bild
Skolan för
elektroteknik
och datavetenskap

Uppgift 9

Uppgiften ska lämnas till din övningsledare på övningen 25/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.

Maskinkod och assembler

Ta en titt på NIC, The Nada Instructional Computer. Ladda ner mjukvaran, prova simulatorn och assemblern, samt sätt dig in i hur de bifogade exempelprogrammen fungerar. Skriv sedan tre program som
  • multiplicerar varje element i en vektor med samma tal,
  • flyttar runt ordet 0xff i ett intressant mönster i minnet på adresserna från 0x80 till 0xff,
  • beräknar och skriver ut (i RAM) de tretton första Fibonacci-talen (1, 1, 2, 3, 5, 8, ...).
Programmen ska vara väldokumenterade och ska som vanlig lämnas in på papper.

Ordonotation

  • 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)3 är O(n3). Använd dig av följande definition: f(n) är O(g(n)) om det finns positiva konstanter c och n0 så att f(n) ≤ cg(n) för alla n ≥ n0.
  • 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
    
Copyright © Sidansvarig: Stefan Nilsson <snilsson@nada.kth.se>
Uppdaterad 2011-11-13