I120 - Algoritmer, Datastrukturer og Programmering

                                                        Løsningsforslag
                                                          Oppgavesett 2

Oppgave 1

public class Oppgave1 {
    int fib(int tall, String innrykk) {
        // Skriv ut dette kallet:
        System.out.println(innrykk+"f("+tall+") ...");
        int res;
        if (tall<2) res = 1;
        else res = fib(tall-1,innrykk+"  ")+fib(tall-2,innrykk+"  ");
        // Skriv ut resultatet:
        System.out.println(innrykk+"= "+res);
        return res;
    }
    public static void main(String[] args) {
        Oppgave1 f = new Oppgave1(); // Kunne vaert static over??
        f.fib(5,"");
        f.fib(6,"");
    }
}

Oppgave 2

Se læreboka side 142-143 for Java-implementasjon med fast array-størrelse.
Løsning med dobling og halvering av array-størrelse er del av Oblig1.

Oppgave 3

R-2.5

Thomas, her må du legge inn samme som i
file:/net/www/htdocs/ii/undervisning/kurs/h00/i120/losninger/oppgave2/sol2.html
Jeg fant ikke ut hvordan gjøre dette.

R-2.9
Vi må vise

 1.f(n)+g(n) er O(max{f(n), g(n)}) og
 2.max{f(n), g(n)} er O(f(n)+g(n))

Vi bruker definisjonen på side 47 i læreboka. For både 1) og 2) kan vi velge konstanten n0=1.
For 2) kan vi velge konstanten c=1, da max{f(n), g(n)} <= f(n)+g(n), om vi antar (naturlig
nok) at f(n) og g(n) begge er positive, for alle n. For 1) velger vi konstanten c=2, siden
f(n)+g(n) <= 2*(max{f(n), g(n)}). Dvs f(n)+g(n) = 2*(max{f(n), g(n)}) for verdier av n hvor
f(n)=g(n), og ellers er f(n)+g(n) < 2*(max{f(n), g(n)}.

Oppgave 4

f1 er O(NlogN). En ytre for-løkke som utfører
 while-løkken N ganger.
For hver av disse utføres operasjonene inne i
 while-løkken  x ganger, hvor x er antall ganger
vi kan dele N på 2 før vi når ned til 1.
Per definisjon er x=log_2 N, dvs log base2 av N.

f2 er O(N^2), dvs N i annen. Tildelingen i den indre for-løkken utføres
1 gang når i=1, 2 ganger når i=2, osv inntil n-1 ganger når i=n-1.
Kjøretiden totalt blir dermed O(Sum{i=1} til {i=N-1} i)= O(N^2).

f3 er O(N). k starter på 0, øker med 1 hver gang gjennom while-løkken,
og vi stanser når k=2N-1.

f4 er O(NlogN). Dette er Flettesorteringsalgoritmen.
Analysen kan gjøres ved å se at kallet f4(N) leder til to kall
f4(N/2) samt O(N) tid for å flytte elementer mellom tabeller og
kjøre f3. Vi kan sette opp et (binært) tre av rekursive kall,
som vil ha dybde logN, og se at det i hvert nivå vil utføres O(N) arbeid.