Julia Programme zur Vorlesung Algorithmen und Datenstrukturen
Implementierte Algorithmen und Datenstrukturen (Nummern analog zur Vorlesung)
- 01-Einführung - Summe - Summe mit Vorwissen - Insertion Sort - Selection Sort - 02-Teile und Herrsche - Merge Sort - Quicksort - Lampsort - Heap Sort - 03-Sortierung durch Verteilen - Counting Sort - Zeichenkettenvergleich - Beispielhafte Implementierung der Operationen für eine Linked List - Beispielhafte Implementierung der Operationen für einen Stack - Beispielhafte Implementierung der Operationen für eine Queue - Bucket Sort - 04-Prioritätswarteschlangen - Binärer Heap mittels Array - Binomial Heap - Fibonacci-Heap - 05-Selektion - Quickselect - 06-Mengen - Beispielhafte Implementierung einer Menge - Iteratoren und Typen in Julia - Selbstanordnende Listen - Binäre Suche - Binärer Suchbaum - Splay Baum - Rot-Schwarz-Baum - AVL-Baum - 07-Mengen von Zeichenketten - Trie - PatriciaTrie - 08-Disjunkte Mengen - Union-Find (mit Bäumen und Pfadkompression) - 09-Assoziation von Objekten - Einfache Zuordnung - Hashtabelle mit verketteten Listen und Reallokation - Hashtabelle mit offener Adressierung (Sondierung) - 10-Graphen - Beispiele zur Graphimplementierung - Breitensuche - Tiefensuche - Zusammenhangskomponenten (ZHKs) - Kürzeste Wege in DAGs mittels topologischer Sortierung der Knoten - Dijkstras Algorithmus - A* Algorithmus - Bellman-Ford Algorithmus - Kruskal - Jarnik-Prim - Ford-Fulkerson (mit Edmons Karp) - Euler-Kreis/ -Weg - 11-Suchgraphen für Spiele - Min-Max - Alpha-Beta-Pruning - Cutoff - 13-Dynamische Programmierung, Greedy Verfahren - Longest Common Subsequence (LCS) - Rucksackproblem - Greedy Locate - 14-Zeichenkettenabgleich - Brute Force - Knuth-Morris-Pratt-Algorithmus - Boyer-Moore-Verfahren - Rabin-Karp-Algorithmus - Suche in Suffix-Feldern - 17-Approximation - List-Scheduling - Übung - Adder - Bubble-Sort - Weekly-Julia
Ausführung Die Programme sind so konzipiert, dass sie direkt durch Aufruf über das Terminal oder den Debugger funktionieren und eine Beispielausgabe erzeugen. Sie haben keine externen Abhängigkeiten bzgl. Paketen außer einer einfachen Installation von Julia (hauptsächlich entwickelt unter Version 1.7, empfohlen Version 1.8.5). Bei den Graphalgorithmen kann durch Installation der Pakete `Plots` und `GraphRecipes` (`add Plots`, `add GraphRecipes`) eine bildliche Ausgabe ermöglicht werden, andernfalls werden nun Knoten und die Adjazenzmatrix dargestellt.
Im Ordner `Utils` befinden sich Datenstrukturen, die in einem der anderen Programme benötigt und geladen werden. Die Datenstrukturen basieren meist selbst auf einem der vorher behandelten Programme.