Algorithmen und Programmierung II

Aufgabe 1 (10 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 (5 Zusatzpunkte)

Das Java-Programm BallAnim öffnet ein Fenster und animiert darin ein paar fliegende Bälle - Objekte der Klasse Ball. Diese ist eine abstrakte Klasse, d.h. man kann Ball-Objekte nicht direkt erzeugen, sondern nur Objekte einer nichtabstrakten Unterklasse. Insbesondere müssen diese Unterklassen neben ihrem Konstruktor die beiden Methoden

 public void paint(Graphics g)
 public Ball[] collideWith(Ball aBall)

implementieren.

Die paint-Methode malt den Ball innerhalb des Quadrates der Seitenlänge Ball.SIZE und mit unterer linker Ecke (x*Ball.SIZE, y*Ball.SIZE). (Dabei sind x und y Instanzvariablen des Ball-Objektes. Untere linke Ecke heißt hier minimale Koordinaten - was nicht mit unten links auf dem Bildschirm übereinstimmt, da dort die y-Koordinate von oben nach unten wächst.)

Die collideWith-Methode gibt den oder die Bälle zurück, die den jetzigen Ball bei einer Kollision (gleiche Koordinaten) mit dem als Parameter übergebenen Ball ersetzen. Die Position der zurückgeliegerten Bälle soll die Position des Balles sein, die er vor der letzten Bewegung innehatte, die zu der Kollision geführt hat. Dazu stellt Ball die Methode

 public Point getLastLocation()

zur Verfügung. (Points haben zwei int-Einträge, x und y. Siehe auch API-Doc.)

Man kann z.B. eine Reflektion darstellen, indem collideWith einen Ball zurückgibt, der die Flugrichtung (Instanzvariable direction in Ball) des als Parameter gegeben Balles hat.

In dem Programm ist bereits eine Ball-Unterklasse als Beispiel gegeben: SoapBubble, ein Ball-Objekt, das bei jeder Kollision sofort vernichtet wird.

Erstelle zwei weitere Unterklassen von Ball mit anderen paint- und Kollisionsverhalten (z.B. ein Ball, der beim Aufprall reflektiert wird oder ein Ball-Objekt, das sich bei den ersten paar Aufprällen in zwei Bälle teilt) und verwende diese in der Animation (in der main-Methode von BallAnim, wo bisher nur SoapBubbles konstruiert werden).