Herbst-2019-ITCS-8114-Algoden
Dieses Repository enthält die Projekte und Zuordnungen natürlich "ITCS 6114/8114: Algorithmen und Datenstrukturen" . Dieser Kurs wurde im Herbst 2019 -Semester im Rahmen meines Doktorarbeits bei UNC Charlotte belegt.
Projektliste
- Projekt 1: Vergleichsbasierte Sortieralgorithmen
- Projekt 2: Diagrammalgorithmen (Singles-Source-Kürzeste und minimaler Spannungsbaum)
- Projekt 3: Musteranpassungsalgorithmen
Im Folgenden finden Sie die Beschreibung und die Anforderungen der Projekte. Um die Details zu erhalten, gehen Sie bitte zum entsprechenden Projektverzeichnis.
Projekt 1: Vergleichsbasierte Sortieralgorithmen
Implementieren Sie die folgenden Sortieralgorithmen und vergleichen Sie sie. Sie können jede Programmiersprache (z. B. C/C ++, Java, Python, C#) verwenden. In diesem Projekt können Sie alleine oder als Team von zwei Arbeiten arbeiten.
- Insertion -Sortierung
- Sortierung zusammenführen
- Haufen [Vektorbasiert und ein Element gleichzeitig einfügen]
- In-Place Quicksort (jeder zufällige Element oder das erste oder das letzte Element Ihrer Eingabe kann pivot sein).
- Modifizierte Quicksort
- Verwenden Sie den Median von drei Jahren als Dreh- und Angelpunkt.
- Verwenden Sie für ein kleines Teilproblem der Größe <= 10 Insertionssorten.
Ausführungsanweisungen:
- Führen Sie diese Algorithmen für verschiedene Eingangsgrößen aus (z. B. n = 1000, 2000, 4000, 5000, 10000 .. 40000, 50000). Sie generieren zufällig Zahlen für Ihr Eingabearray. Notieren Sie die Ausführungszeit (müssen den Durchschnitt, wie in der Klasse erläutert) und zeichnen Sie sie alle in einem einzelnen Diagramm gegen die Eingangsgröße auf. Beachten Sie, dass Sie diese Sortieralgorithmen für denselben Datensatz vergleichen.
- Beobachten und präsentieren Sie auch die Leistung der folgenden zwei Sonderfälle:
- Eingabearray ist bereits sortiert.
- Eingabearray wird umgekehrt sortiert.
Bewertungsschema:
Einreichungsanweisungen:
- Canvas -Upload
- Ein gut formatierter Bericht über die ausgewählte Datenstrukturen, Komplexitätsanalyse, Ergebnisse und Code.
- Programmcode für die Ausführung hochladen. Stellen Sie sicher, dass Sie Readme für TA zur Verfügung stellen.
- Darüber hinaus in der Klasse Hardcopy of Report ohne Code für mich.
Projekt 2: Diagrammalgorithmen (Singles-Source-Kürzeste und minimaler Spannungsbaum)
In diesem Projekt werden Sie zwei unten erwähnte Graph -Algorithmen implementieren. Hinweis: Sie können alleine oder in einem Team von zwei Maxien arbeiten.
Problem 1: Finden Sie den kürzesten Pfadbaum sowohl in gerichteten als auch in ungerichteten gewichteten Graphen für einen bestimmten Quellscheitelpunkt. Angenommen, es gibt keine negative Kante in Ihrem Diagramm. Sie drucken jeden Pfad- und Pfadkosten für eine bestimmte Quelle.
Problem 2: Finden Sie bei einem verbundenen, ungerichteten, gewichteten Diagramm einen Spannungsbaum mit Kanten, der das Gesamtgewicht minimiert? (?) = ∑ (u, v) ∈T ? (?,?). Verwenden Sie den Kruskal -Algorithmus, um den minimalen Spanning Tree (MST) zu finden. Sie werden die Kanten des Baumes und die Gesamtkosten Ihrer Antwort ausdrucken.
Eingabeformat: Für jedes Problem nehmen Sie Eingaben aus einer Textdatei. Sagen Sie, Sie möchten Algorithmus in der folgenden ungerichteten Grafik ausführen. Das entsprechende Dateiformat wäre:
6 10 U
A B 1
A C 2
B C 1
B D 3
B E 2
C D 1
C E 2
D E 4
D F 3
E F 3
A
Hier repräsentieren die ersten beiden Zahlen die Anzahl der Eckpunkte und Kanten. Der Buchstabe U steht für ungerichtete Graph (D für gerichtete). Aus der zweiten Zeile erwähnt es alle Kanten und sein Gewicht (z. B. ???? (?,?) Und sein Gewicht ist 1. Die letzte Zeile ist optional. Wenn angegeben, repräsentiert es den Quellknoten.
Einreichungsanweisungen:
- Ein gut formatierter Bericht über eine kurze Beschreibung jedes Algorithmus, der ausgewählten Datenstruktur, der Laufzeit Ihres Codes, der Beispieleingabe/Ausgabe, Anweisung zum einfachen Ausführen Ihres Programms.
- Führen Sie für jedes Problem Ihr Programm für vier verschiedene Grafiken Ihrer Wahl aus. Verwenden Sie Ihr Urteilsvermögen, um Testgraphen zu definieren, die Sie für interessant und vernünftig halten. Zum Beispiel:
- Unbekanntes Diagramm: Mindestens 7 Knoten und 12 Kanten
- Regie Graph: Mindestens 7 Knoten und 15 Kanten
- Clean Code für TA zur Ausführung.
- Sie können jede Programmiersprache verwenden (z. B. C/C ++, Java, Python usw.)
- Bei der Arbeit in einem Team müssen beide Mitglieder alles separat einreichen.
- Hardcopy Ihres Berichts an mich direkt; eine Kopie pro Team.
Bewertungsschema:
Projekt 3: Musteranpassungsalgorithmen
Hinweis: Sie können alleine oder in einem Team von drei Maxien arbeiten.
Für diese Zuordnung implementieren Sie nur drei Muster -Matching -Algorithmen Ihrer Wahl aus der unten angegebenen Liste.
- Brute-Force-Algorithmus
- Boyer-Moore-Horspool-Algorithmus
- Knuth-Morris-Pratt-Algorithmus
- Boyer-Moore-Algorithmus
- Endliche Automatisierung für das Musteranpassung
Experiment:
- Vergleichen Sie drei Algorithmen für mehrere verschiedene Eingabetxt und Muster. mindestens 10 verschiedene Fälle
- Erwähnen Sie die Anzahl der in einer Tabelle für jeden Fall für jeden Algorithmus erforderlichen Vergleiche
Vorlage:
- Ein gut formatierter Bericht über die kurze Beschreibung der einzelnen Algorithmus, der verwendeten Datenstruktur, der Laufzeit Ihres Codes, der Beispieleingabe/Ausgabe und der Anweisung, Ihr Programm einfach auszuführen.
- Clean Code für TA zur Ausführung.
- Sie können jede Programmiersprache verwenden (z. B. C/C ++, Java, Python usw.)
- Wenn sie in einem Team gearbeitet haben, müssen beide Mitglieder alles separat einreichen.
- Hardcopy von Ihrem Bericht an mich direkt; eine Kopie pro Team.
Bewertungsschema:
- 3 x 15 = 45 Punkte: Für die Implementierung von drei Algorithmen
- 20 Punkte: Für das Experiment
- 10 Punkte: Bericht
