Oppgave 1: Fibonacci-utskrift

Bruk programmet for beregning av Fibonacci-tall (uten bruk av memoisering) fra
forelesningen, og utvid det med utskriftkommandoer slik at du får en utskrift som markerer, for hvert rekursivt kall,

   argumentet
   rekursjonsdybde
   returnert resultat.

Dybden kan passelig markeres med indentering av utskriften. For eksempel, kallet fib(4) (dvs. >javac fib med påfølgende argument 4) burde produsere noe slikt:

f(4) ...
  f(3) ...
    f(2) ...
      f(1) ...
      = 1
      f(0) ...
      = 1
    = 2
    f(1) ...
    = 1
  = 3
  f(2) ...
    f(1) ...
    = 1
    f(0) ...
    = 1
  = 2
= 5

Gi en enkel regel som bestemmer, for en slik utskrift, hvilken returverdilinje '=x' som
tilhører en gitt kallinje 'f(y)...'
 

Oppgave 2 - ADT Stabel

1. Gi en implementasjon av interface Stack

som beskrevet i kapittel 4.1 i læreboka:

   public interface Stack {
    /**
     * @return number of elements in the stack.
     */
     public int size();
    /**
     * @return true if the stack is empty, false otherwise.
     */
     public boolean isEmpty();
    /**
     * @return top element in the stack.
     * @exception StackEmptyException if the stack is empty.
     */
     public Object top()
       throws StackEmptyException;
    /**
     * Insert an element at the top of the stack.
     * @param element element to be inserted.
     */
     public void push (Object element);
    /**
     * Remove the top element from the stack.
     * @return element removed.
     * @exception StackEmptyException if the stack is empty.
     */
     public Object pop()
       throws StackEmptyException;
   }

Implementasjonen skal gjøres vha en array på størrelse N,
hvor du skal bruke minimumsstørrelsen N=4 ved oppstart.
Istedetfor å heve en StackFullException skal din
implementasjon doble størrelsen på den underliggende array
når antall element går over N.
Tilsvarende skal du halvere størrelsen på den
underliggende array når antall elementer går
under N/4, dog overholde minimumsstørrelse 4.

Test ut din stabel-implementasjon ved å reversere en array,
dvs gitt array med innhold 2,4,3,1,5 skal du skrive Java-kode
som vha din stabel returnerer en array med innhold 5,1,3,4,2.
 

Oppgave 3 - Introduksjon til kjøretidsanalyse og Stor-O notasjon.

Oppgave 4 - Mer kompleksitet/kjøretidsanalyse (eksamen H00)

void f1(int[] a, int n) {
   int i,j;
   for (j = 0; j < n; j++) {
      i = n;
      while (i > 1) {
         a[j] = a[j]/i;
         i = i/2;
      }
   }
}

void f2(int[] a, int n) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
      a[i] = a[i]+j; } } }

void f3(int[] a, int[] b, int[] c, int n) {
   int i=0, j=0, k=0;
   while (k < 2*n) {
      if (i<n && (j>n || a[i]<b[j]))
         c[k++]=a[i++];
      else
         c[k++]=b[j++];
   }
}

void f4(int[] a, int n) {
   int[] b = new int[n/2];
   int[] c = new int[n/2];
   if (n < 2) return;
   for (i = 0; i < n/2; i++)
      b[i]=a[i];
   for (i = n/2; i < n; i++)
      c[i-n/2]=a[i];
   f4(b, n/2);
   f4(c, n/2);
   f3(b, c, a, n/2);