Diskussion der einzelnen Aufgabe der Klausur "Algorithmen und Datenstrukturen" vom SS 2023
Aspekte: Schwierigkeitsgrad,
Aufgabe 1.1 (6 Punkte, Sortieren, wenn ein Element falsch)
Diese Aufgabe ist algorithmisch sehr einfach: die Position des falsch einsortierten Elements ist gegeben, man muss also herausfinden, an welche Stelle es gehört und es dann dahin verschieben. Man kann es entweder dahin "tauschen" (so macht es die Musterlösung), oder man erzeugt ein neues Feld, in das man die Elemente geeignet kopiert.
Diese Aufgabe prüft im Wesentlichen, ob man eine Funktion mit einer einfachen Spezifikation implementieren kann. Zu unserer Überraschung konnten das viele nicht, obwohl die Hälfte der Übungsaufgaben von dieser Art war (für deulich anspruchsvollere Probleme).
Aufgabe 1.2 (6 Punkte, ist HeapSort stabil)
Bei dieser Aufgabe wurden zwei Themen aus verschiedenen Vorlesungen miteinander verbunden (Sortiere und binärer Heap). Sie ist dadurch etwas schwieriger als die übliche Aufgabe. Sehr schwierig ist sie allerdings nicht: man muss es nur anhand eines Beispiels durchspielen (drei Elemente reichen schon), dann sieht man, dass es nicht stabil ist. Das Prinzip, etwas erstmal anhand eines kleinen Beispiels zu verstehen, wurde in der Vorlesung sehr viele Male vorgemacht und auch immer wieder als Lern- bzw. Verständnismethode empfohlen.
== Aufgabe 1.3 (8 Punkte, Wahr-Falsch-Fragen zum Sortieren)
Frage 1 ("MergeSort immer Theta(n * log n)"): Einfache Verständnisfrage.
Frage 2 ("Muss die Eingabegröße eine Zweierpotenz sein"): Geschenkt, wenn man das Übungsblatt gemacht hat.
Frage 3 ("Die Vergleiche von MinSort hängen von der Eingabe ab"): Einfach, wenn man sich den Algorithmus (den wir über drei Vorlesungen hinweg genauestens analysiert haben) vergegenwärtigt. Es ergibt sich auch direkt aus der I/E-Analyse in Vorlesung 3.
Frage 4 ("BogoSort vs. HeapSort"): Ein bisschen gemein, weil sich manche nicht gemerkt haben, wie BogoSort funktioniert. Sonst trivial (BogoSort rät die Sortierung und kann auch mal Glück haben).
miteinander verbinden (Sortieren
Bei dieser Aufgabe ging es darum, ein Feld , das bis auf ein Element schon ganz sortiert war, vollständig zu sortieren, und zwar in O(n) Zeit.