Oppgavesett 4 - Algoritmeanalyse / rekursjon

Oppgavene blir tema på øvingen fredag 10. februar. Innleveringen skal bestå av en pdf-fil med korte kommentarer og dokumentasjon (utskrifter etc.). Legg også ved godt dokumenterte java filer. Alt pakkes i en zipfil, med navn assignment04-*.zip der * er etternavnene til gruppemedlemmene. Javafilene skal tilhøre en pakke med navn package assignment04.

Fristen for innlevering er tirsdag 14.februar 09:00.

Oppgave 1

A)

Beskriv med presis pseudokode er rekursiv variant av binærsøk. Implementer deretter metoden i Java. Drivermetoden (metoden som kaller den rekursive funksjonen for første gang) skal ha signaturen public int binarySearchRec(int[] arr, int value). Metoden returnerer indeksen til elementet med verdien value, og -1 hvis den ikke finnes. Dokumenter at metoden virker.

B)

Test medoden over ved å telle gjennomsnittlig antall rekursive kall for økende størrelse på input. Plott verdiene og kommenter! Bruk målingene til å vise at metoden er av logaritmisk orden.

Oppgave 2

De følgende funksjonene skal implementeres og testes ved å måle kjøretida på varierende input. Resultatene skal plottes på en slik måte at det klart går fram hvordan funksjonene vokser med økende argumentverdier. Du skal ikke bruke Java sine mattefunksjoner.

A)

Implementer metoden int log(int b, int n), som implementer ⌊log_bn (b-logaritmen til n avrundet nedover til nærmeste heltall). Du skal ikke bruke noen av Java sine ferdige logaritmefunksjoner. Dokumenter at den virker.

B)

Bruk logaritmefunksjonen i forrige oppgave til å lage et kombinert diagram der du plotter et passende sett med grafer med forskjellig base (f.eks. ⌊log₂n, ⌊log_en, ⌊log₃n, ⌊log₅n,⌊log₁₀n, ⌊log₁₆n).

* Oppgave 3

Funksjonen A(m, n), der argumentene er to ikke-negative heltall, er definert slik:

Hvis m = 0: n+1
Hvis m > 0 og n = 0: A(m-1, 1)
Hvis m > 0 og n > 0: A(m-1, A(m, n-1))

Implementer funksjonen, og test den ved kjøre den og måle kjøretida med varierende input. Kan du si noe om funksjonens kompleksitet?

Oppgave 4

Her følger 5 matematiske funksjoner. For hver av de skal du angi kompleksiteten i O-notasjon, inkludert en kort begrunnelse. Du skal også plotte hver funksjon, sammen med den tilhørende O-funksjonen (for et passende sett av verdier for N).

f1(N) = 3N - 38912 + 0.3N²

f2(N) = 13N + 6N^-2

f3(N) = 3.14log₈N + 59.4N

f4(N) = 6N¹² + 8 N! + 560980357478N

f5(N) = 15log₈N⁴² + 2N

Oppgave 5

Her følger 4 java-funksjoner. For hver av de skal du angi kompleksiteten i O-notasjon, inkludert en kort begrunnelse. Om du mener det er nødvendig, kan du gjøre dine egne antagelser.

void alg1(int k) { for(int i = k; i > 0; i--) { int j = i+k; } }

void alg2(int n) { int j = 1; while (j <= n) { System.out.println(j); j *= 2; } }

void alg3(int[] a) { int m = a.length - 1; while (m >= 0) { for (int i = m; i < a.length; i++) { System.out.print(a[i]+" "); } System.out.println(); m--; } }

void alg4(int[] b) { for(int i = 0; i < b.length; i++) { alg3(b); alg1(i); } }