Tutorien für Algorithmen und Datenstrukturen 2
Übungsblatt 2: Laufzeitoptimierte Lösungsverfahren
Aufgabe 2-1
Schreiben Sie eine Klasse, welche Ihre naïve Lösung aus Aufgabe 1-3a oder Aufgabe 1-3 geringfügig verbessert auf eine Komplexität von O(n2).
Aufgabe 2-2*
Schreiben Sie eine weitere Klasse zur Lösung des Maximum–Sub-Array–Problems. Diese Klasse soll das Interface MaximumSubArraySolver implementieren. Ihre Lösung soll die Effizienz O(n) haben. Lösen Sie diese Aufgabe durch Bearbeitung der untenstehenden Teilaufgaben.
Bitte beachten Sie, dass die in der Vorlesung Algorithmen und Datenstrukturen 1 gezeigten Algorithmen allesamt lediglich die Summe des Ergebnisses berechnen. Das eigentlich benötigte Ergebnis ist aber der Sub-Array selbst. Ein Array ist definiert durch seine Elemente, ein Sub-Array durch seine Grenzen und den gesamten Array. Der durch die Klasse SubArray definierte Datentyp SubArray ist zur eindeutigen Definition eines Sub-Arrays geeignet.
- Ändern Sie Ihren existierenden Algorithmus aus einer der vorhergehenden Aufgaben derart, dass statt des existierenden Lösungsalgorithmus eine entsprechend effizientere Lösungsmethode angewandt wird. Benutzen Sie dazu das in der Vorlesung Algorithmen und Datenstrukturen 1 vorgestellte Scanline-Verfahren als Vorlage.
- Ändern Sie Ihre Lösung von Teilaufgabe (a) so ab, dass zusätzlich zur Summe die Grenzen des Sub-Arrays ausgegeben werden. Die Grenzen können wahlweise entweder durch Beginn und Ende oder durch Start und Länge angegeben werden.
- Ändern Sie Ihre Lösung von Teilaufgabe (b) derart, dass sie das Interface MaximumSubArraySolver implementiert. Ziehen Sie Literatur wie etwa die Klassendokumentation („Javadoc“) oder Ihre Unterlagen der Vorlesung Programmiersprachen 1 zu Rate.
$Id: HEADER.html,v 1.6 2007/12/04 22:44:32 arne Exp $
Name Last modified Size Description
Parent Directory -
MaximumSubArraySolver.java 2023-10-11 10:00 2.4K
HEADER.html 2023-10-11 10:00 2.5K
Loesung21.java 2023-10-11 10:00 2.7K
doc/ 2023-10-11 10:00 - Klassendokumentation (Javadoc)