Algorithmen und Programmierung II

Die Lösung der Aufgaben und die Abgabe der Lösungen erfolgt in Zweiergruppen!

Hinweis: Benutze die Ressourcen der ALP2 Webseite.

Aufgabe 1 (20 P.)

Gib die (worst case) Laufzeiten der folgenden Probleme in der O-Notation an. Gib jeweils eine kurze Begründung Deiner Anwort.

1. Die binäre Suche eines Elementes in einem sortierten Feld (array) von n Elementen.
2. Das maximale Element aus einem unsortieren Feld mit n Elementen bestimmen.
3. Das (sortierte) Einfügen eines Elementes in eine sortierte Liste mit n Elementen.
4. Das Hinzufügen (push) eines Elemenentes zu einem mit einer Liste implementierten Stapel, der bereits n Elemente enthält.
5. Das Sortieren von n Elementen durch Mischen (merge sort).
6. Das Sortieren von n Elementen durch bubble sort.
7. Die Berechnung der Fakultät von n wie in Beispielprogramm aus Übung 1.2.
8. Die Berechnung aller Permutationen eines Wortes der Länge n wie in Übung 5.1.
9. Die Berechnung des Skalarprodukts zweier Vektoren mit je n Elementen.
10. Die Matrixmultiplikation zweier nxn-Matrizen.

Aufgabe 2 (4+2 = 6 P.)

Die Prozedur P ist durch Entrekursivierung einer bekannten rekursiven Prozedur mit Hilfe eins Stapels entstanden.

public class myP {

    public void P() {

    	PP e = new PP(1,3,2,3,0);
    	Stapel s = new Stapel(20);
    	s.push(e);
	while (!s.isEmpty() ) {
        	PP tmp = (PP)s.top();
	switch (tmp.stelle){
        		case 0: if (tmp.H==0) s.pop();
			else {
				e=(PP)s.top();
				s.pop();
				e.stelle=1;
				s.push(e);
                        		tmp = (PP)s.top();
				e= new PP(tmp.V,tmp.U,tmp.N,tmp.H-1,0);
				s.push(e);
			}
                    	break;
        		case 1:  e= (PP)s.top();
			System.out.print(e.V);
			System.out.print(" -> ");
			System.out.println(e.N);
                    	tmp = (PP)s.top();
			e= new PP(tmp.U,tmp.N,tmp.V,tmp.H-1,0);
			s.pop();
			s.push(e);
                    	break;
		}
	}
    }

    private static class PP {
        public PP(int V, int N, int U, int H, int stelle) {
            this.V = V;
            this.N = N;
            this.U = U;
            this.H = H;
            this.stelle = stelle;
        }

	public int V,N,U,H;
	public int stelle;
    }
}

a) Was sind die Ergebnisse der symbolischen Ausführung von  P? (d.h. P von Hand ausführen). 

b) Aus welcher bekannte Prozedur X ist P hervorgegangen?

Aufgabe 3 ( 20 P.)

Gegeben sei M eine quadratische Matrix. Die Zeilenzahl N ist eine gerade Zahl. 
Schreibe ein Java Programm, um M spiralenförmig im Uhrzeigersinn zu nummerieren.

Beispiel mit N=4:

Die Definition der Fibonacci ist:

fib(0) = fib(1) = 1;
fib(n) = fib(n – 1) + fib(n – 2) für n > 1

Die resultierende Folge ist:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Eine unmittelbare rekursive Lösung ist:

long fib (long n) {

	if (n == 0 || n == 1) return 1;

	else return fib(n – 1) + fib(n – 2);

}

1. Ist die Funktion fib linear rekursiv? Begründe Deine Antwort!

2. Ist die Funktion fib endrekursiv? Begründe Deine Antwort!

2. Entrekursiviere die Methode fib.

Aufgabe 5 (2 + 2 + 2 = 6P.)

Gegeben sei folgende Methode:

int mystery(int n,int h) {

    if (n==0) return h;
    return mystery(n-1,h*n);
}

1. Ist die Funktion mystery linear rekursiv? Begründe Deine Antwort!

2. Ist die Funktion mystery endrekursiv? Begründe Deine Antwort!

2. Entrekursiviere die Methode mystery.

19.06.2002