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