Zusatzaufgaben zum Erwerb von Votierpunkten für Algorithmen und Datenstrukturen 2001

Für die vollständige Bearbeitung einer Aufgabe (ein funktionierendes Programm) werden je nach Strukturierung des Quellcodes 3 - 5 Votierpunkte gutgeschrieben.
Abnahme der Lösungen während aller Tutorien vom 05.06. bis 15.06.01
Bei auftretenden Fragen und Hilfestellungen beim Programmieren stehen Tutoren gern zur Verfügung.

Erstellung einer zyklischen Liste und zufällige Ausgabe ihrer Elemente

Aufgabe von Stephan Finn, Tutorzeit: Dienstag 17 - 19 Uhr, finn@cs.uni-magdeburg.de

Es soll eine einfach verkettete Liste programmiert werden, deren letztes Element auf das erste zeigt. Die Elemente sollen vom Typ "Object" sein.
Die Datenstruktur soll folgende Prozeduten beinhalten:

void push(Object), fügt ein neues Element in die Datenstruktur ein (am Ende)
Object pop(int), geht in der Datenstruktur um "int" Schritte weiter, löscht das Element, auf dem es steht und gibt dieses zurück
int length(), gibt die Anzahl der enthaltenen Elemente zurück
boolean empty(), schaut, ob die Datenstruktur leer ist.

Mit dieser Datenstruktur soll ein Programm geschrieben werden, dass die Wochentage "Montag, ..., Sonntag" als Strings in der Struktur speichert und diese dann in zufälliger Reihenfolge ausgibt. Dazu soll eine Zufallszahl zwischen 0 und "length()" der Liste erzeugt werden und mit "pop(Zufallszahl)" das entsprechende Element gelöscht werden.

Hier sollte eigentlich eine kleine Illustration sein!

Darstellung einer analogen Uhr

Aufgabe von Andrea Frank und Folker Folkens, Tutorzeit: Montag 17 - 21 Uhr, Mittwoch 19-21 Uhr

Aufgabe ist die Darstellung einer analogen Uhr mit Hilfe eines Applets. Die Uhrzeit wird aus der Systemzeit geholt und aktualisiert.
Zur formalen Darstellung:

Einbau der Anzeige des Datums
Uhr besitzt Stunden-, Minuten- und Sekundenzeiger
evtl. verschiede Arten von Design des Ziffernblatts
Detaillierung des Ziffernblattes:

Zahlen von 1 bis 12
Minutenstriche

Dictionary

Aufgabe von Oliver Träger und Stephan Schosser, Tutorzeit: Mittwoch 13- 15 Uhr, Donnerstag 17-19 Uhr

Ein Dictionary ist ein abstrakter Datentyp, der Elementpaare (k, e) speichern kann.
k ist dabei ein Schlüssel und e ein Element.
Für die Aufgabe soll davon ausgegangen werden, dass k ein eindeutiger numerischer Schlüssel (Typ int) ist und e einen beliebigen Typ haben kann (Typ object).
Der Datentyp Dictionary ermöglicht es, über den Schlüssel k schnell auf ein beliebiges Objekt zuzugreifen.
Der Datentyp besitzt folgende Funktionen:

size() : Gibt die Anzahl der Elemente zurück
isEmpty() : Testet, ob das Dictionary leer ist
findElement(k) : Gibt Objekt zum Schlüssel k zurück, und eine Exception, sollte der Schlüssel k nicht existieren
insertElement(k,e): Fügt ein Element mit dem Schlüssel k und dem Objekt e ein
remove(k): Löscht das zum Schlüssel k gehörige Element

Implementieren Sie den Datentyp Dictionary aus Basis des in der Vorlesung vorgestellten AVL-Baumes.

Pattern-Matching-Algorithmus

Aufgabe von Stefan Habelski und Ingmar Hook, Tutorzeit: Donnerstag 13 - 15 und 19-21 Uhr

Implementation und Visualisierung eines einfachen Pattern-Matching-Algorithmus als Applet, bei dem man verfolgen kann, wie das Suchmuster immer schrittweise unter den Text gelegt wird und einzelne Buchstaben miteinander verglichen werden.
Es sollen dabei die Algorithmen "Brute Force" und "SBorder" (die in der Vorlesung als Pseudocode schon gegeben sind) umgesetzt werden, der Benutzer soll einen Text und ein Suchmuster eingeben und einen Ersetzungsalgorithmus auswählen können.
Damit es nicht zu aufwendig wird, können Suchmuster und Text in der Länge beschränkt sein, so daß man zur Darstellung eine einzige lange Textzeile verwenden kann, unter der jeweils das Suchmuster an der entsprechenden Stelle angezeigt wird. Die Buchstaben bzw. Wortteile, die gerade im Vergleich sind, sollen farblich hervorgehoben werden.

Traversierungen

Aufgabe von Verena Lommatzsch und Mirko Böttcher, Tutorzeit: Montag 15-17, Dienstag 13-15 und Freitag 13-15 Uhr

Schreibe ein JAVA Programm, welches die inorder- und preorder-Darstellung eines Binärbaums von der Konsole einliest und daraus die postorder-Darstellung berechnet.

Sprouts / Brussels Sprouts

Aufgabe von Andrea Frank, Tutorzeit: Montag 17 - 19 Uhr, Mittwoch 19-21 Uhr

Sprouts (Pflanzensprossen) und Brussels Sprouts (Rosenkohl) sind einfache topologische Spiele für zwei Personen. Bei beiden Spielen wird zunächst eine beliebige Menge von Punkten auf ein Blatt Papier gezeichnet. Die Spieler ziehen abwechselnd. Ein Zug besteht darin, zwei Punkte durch eine Linie zu verbinden, und auf dieser Linie einen neuen Punkt zu zeichnen. Die Verbindungslinie darf keine bereits früher gezeichneten Linien schneiden. Bei Sprouts dürfen von einem Punkt nie mehr als drei Linien, bei Brussels Sprouts nie mehr als vier Linien ausgehen. Auch die auf Verbindungslinien gezeichneten Punkte dürfen wieder mit anderen verbunden werden. Man beachte jedoch, daß durch die Verbindungslinie, auf die sie gezeichnet wurden, von ihnen bereits zwei Linien ausgehen.

Aufgabe ist es, eine graphische Oberfläche für diese beiden Spiele zu entwickeln.

B-Baum

Aufgabe von Ivo Rößling, Tutorzeit: Dienstag 19 - 21 Uhr

In der Vorlesung wurde bei der Untersuchung verschiedener Typen von (Such)Bäumen unter anderem das Prinzip des B-Baums diskutiert.

Für einen B-Baum der Ordnung m gilt:

Jede Seite enthält höchstens 2m Elemente.
Jede Seite, außer der Wurzelseite, enthält mindestens m Elemente.
Jede Seite ist entweder Blattseite ohne Nachfolger oder hat i+1 Nachfolger, falls i die Anzahl ihrer Elemente ist.
Alle Blattseiten liegen auf der gleichen Stufe.

Man entwickle eine Klasse BBaum bzw. BTree, welche es ermöglicht, vergleichbare Objekte (siehe Comparable) in einem derartigen Suchbaum zu verwalten und folgende Zugriffsmethoden bereitstellt:

insert(Comparable obj): fügt ein Objekt in den B-Baum ein
delete(Comparable obj): löscht ein Objekt aus dem B-Baum
boolean is_in(Comparable obj): sucht im Suchbaum nach dem angegebenen Objekt

Die Ordnung m des B-Baums soll bei der Initialisierung variabel gewählt werden können.

Es soll außerdem ein kleiner Testrahmen (Programm) geschrieben werden, welcher die Auswirkung der Anwendung dieser Funktionen adäquat widerspiegelt.

Ungerichteter Graph

Aufgabe von Ivo Rößling, Tutorzeit: Dienstag 19 - 21 Uhr

In der Vorlesung wurden beim Thema "Graphen" Modelle für die Repräsentation gerichteter und ungerichteter Graphen besprochen.

Man entwickle eine Klasse Graph für die Repräsentation ungerichteter Graphen , die - dem in der Vorlesung vorgestellten Prinzip folgend - die folgenden Zugriffsmethoden unterstützt:

insertNode: Einfügen eines Knotens
connect: Ziehen einer Kante,
deleteNode: Löschen eines Knotens,
disconnect: Entfernen einer Kante,
numVertices: Bestimmung der Anzahl aller Knoten im Graphen,
numEdges: Bestimmung der Anzahl aller Kanten in G,
isInNode: Prüfen, of Knoten in G,
isInEdge: Prüfen, ob Kante ist in G,

Dabei obliegt es dem Programmierer, eine für ihn geeignete Repräsentationsmöglichkeit für Knoten und Kanten zu wählen - insbesondere, ob er die "Intelligenz" einzig in der zu entwickelnden Graph-Klasse belässt, oder ggf. für Knoten und/oder Kanten eine zusätzliche Klasse implementiert.
Bei Bedarf können zum Erlangen weiterer 2 Punkte noch folgende Methoden implementiert werden:

hasCycle: Prüft, ob der Graph einen Zyklus hat
isCoherent: Prüft, ob der Graph zusammenhängend ist
isAttainableFrom: Prüft, ob ein Knoten von einem anderen aus erreichbar ist.

Auch hier obliegt es dem Programmierer, eine für seine Zwecke geeignete Modellierung zu wählen - insbesondere, ob der Rückgabewert der Methode(n) bereits im Vorfeld beim Aufbau des Graphen, oder erst on-demand bestimmt wird.