INDA - Uppgift 1 våren 2006

Uppgiften ska lämnas till din övningsledare på övningen den 26/1. Glöm inte försättsbladet (pdf) och att alla papper ska häftas samman eller lämnas in i en plastficka.

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. Om du kör fast med någon uppgift så finns det som vanligt hjälp att få på labbarna.

Hemuppgift
Studera kapitel 8 i programmeringsboken och repetera följande i algoritmboken:
  • Programkorrekthet
  • Tidskomplexitet i värstafall
  • Ordo-notation
  • Matematisk analys av enkla algoritmer
  • Enkla rekursiva algoritmer

Skriftlig uppgift
Lämna in lösningar till uppgift 8.11, 8.14 samt 8.15 i programmeringsboken.

Här är två algoritmer som beräknar xn, där x är ett flyttal och n ett ickenegativt heltal.

double expIterativ(double x, int n)
{
    double res = 1.0;

    for (int i = 0; i < n; i++)
        res *= x;
    return res;
}

double expRekursiv(double x, int n)
{
    if (n <= 4)
        return expIterativ(x, n);

    return expRekursiv(x, n/2) *
           expRekursiv(x, (n + 1)/2);
}
Argumentera för att algoritmerna är korrekta. Använd en loopinvariant respektive ett induktionsbevis.

Beräkna tidskomplexiteten i värstafall för båda algoritmerna. Vad är en lämplig karakteristisk operation? Ange resultatet med hjälp av ordo-notation.



Stefan Nilsson
2006-01-10