Algorithmen und Datenstrukturen 2

Übungsblatt 9: Maximum–Sub-Array–Problem, rekursive Algorithmen

Abgabe bis Montag, 29. Juni, 16:30 Uhr.

Aufgabe 9-1 *

Implementieren Sie den rekursiven, nach dem Prinzip divide and conquer arbeitenden Lösungsalgorithmus des Maximum–Sub-Array–Problems. Verwenden Sie für die Bestimmung der Randmaxima Ihre Methoden aus den Aufgaben 8-1 und 8-2.

Tipp. Verwenden Sie folgende Methodensignatur:

static int methodenName (int[] array, int linkeGrenze, int rechteGrenze)

Tipp. Die Methoden aus den Aufgaben 8-1 und 8-2 müssen leicht angepasst werden, um im Kontext dieses Algorithmus wie nötig funktionieren zu können.

Aufgabe 9-2

1. Ist der Algorithmus aus Aufgabe 9-1 als hard split, easy join oder als easy split, hard join zu charakterisieren? Begründen Sie Ihre Antwort. Kennzeichnen Sie in Ihrem Quellcode zu Aufgabe 9-1 jeweils Beginn und Ende von split und join!
2. Nennen Sie weitere Beispiele für divide and conquer–Algorithmen und teilen Sie diese als hard split, easy join bzw. easy split, hard join ein!

Zusatzaufgabe 9-3

In dem Array new int[] {1, -1, 1} sind mehrere Maximum–Sub-Arrays mit derselben Summe 1 enthalten.

1. Schreiben Sie einen Algorithmus in „natürlicher Sprache“ nach Dr. Bürg, der nicht ein, sondern alle maximalen Sub-Arrays ermittelt und deren Grenzen ausgibt. Verwenden Sie ein Lösungsverfahren Ihrer Wahl.
2. Schreiben Sie eine Java-Klasse, deren Objekte geeignet als Rückgabetyp für eine Methode wären, die Ihren Algorithmus aus Teilaufgabe (a) in Java implementiert.
3. Kombinieren Sie Teilaufgaben (a) und (b) in einer Klassenmethode in Java.

$Id: HEADER.html 2009-06-22 $