Edit-Distance
Als edit-distance wird die Anzahl der Operationen bezeichnet, die benötigt werden, um einen String in einen anderen umzuwandeln.
Download (PHP)

Floyd-Warshall
Algorithmus der Graphentheorie, der die Länge der kürzesten Wege zwischen allen Paaren von Knoten eines gewichteten Graphen findet.
Download (PHP)

Transitive Hülle
Die transitive Hülle eines Graphen beschreibt durch ihre Kanten alle paarweise erreichbaren Knoten.
Download (PHP)

Matrix chain order
Die matrix chain multiplication ist ein Optimierungsproblem, das mithilfe dynamischer Programmierung gelöst werden kann.
Gegeben ist eine Anzahl von Matrizen, für deren Multiplikation die effizienteste Lösung gefunden werden soll. Das Problem ist nicht die Multiplikation der Matrizen, sondern eine optimale Reihenfolge für diese Multiplikation zu finden.
Download (PHP)

Knut-Morris-Pratt-Algorithmus
String-Matching-Algorithmus
Download (PHP)

A*-Suche
Algorithmus der Graphentheorie, der den kürzesten Pfades zwischen zwei Knoten in einem Graphen mit positiven Kantengewichten berechnet.
Da es sich bei dem Algorithmus um eine informierte Suche handelt, benötigt er eine Heuristik, um zielgerichtet zu suchen.

Folgende Heuristiken wurden verwendet:
a) Anzahl von Steinen auf einem falschen Feld
b) Summe der Manhattan-Distanzen aller Steine von Ihrem Zielfeld
c) Gaschnigs Heuristik
d) Summe von a und b

Entstand in Zusammenarbeit mit Christian Meilicke.
Download (Java)

Binäre Suche
Suchalgorithmus, der auf dem Prinzip “Teile und Herrsche” beruht. Setzt eine sortierte Liste voraus.
Download (Scheme)

Bubblesort
Stabiler, In-place Sortieralgorithmus mit schlechter Laufzeit.
Download (Java)

Insertionsort
Stabiler, In-place Sortieralgorithmus.
Download (Scheme)

Mergesort
Stabiler, nicht In-place Sortieralgorithmus basierend auf dem “Teile und Herrsche”-Prinzip.
Download (Scheme)

Quicksort
Nicht-stabiler, In-place Sortieralgorithmus basierend auf dem “Teile und Herrsche”-Prinzip.
Download (Scheme)