Uppgift 1 våren 2012

Uppgiften ska lämnas till din övningsledare på övningen fredagen 20 januari. Glöm inte försättsbladet (pdf).

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 läs också följande texter om

Skriftlig uppgift

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

Här är två algoritmer som beräknar xⁿ, 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. Du kan till exempel använda en loopinvariant respektive ett induktionsbevis.

Beräkna tidskomplexiteten som en funktion av n för båda algoritmerna. Ange resultatet med hjälp av ordo-notation.