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).
Aufgabe 2.1 (6 Punkte, I/E-Sequenz für Programm)
Bei dieser Aufgabe gab es keine Tricks, man musste es einfach nur machen. I/E-Sequenzen waren das wesentliche Element von Vorlesung 3. Trotzdem gab es bei dieser Aufgabe viele Abgaben, die sehr oder total falsch waren.
Aufgabe 2.2 (6 Punkte, Wahr-Falsch-Fragen zur O-Notation)
Frage 1 ("n3 + 6n2 + n log n = Theta(0.5 n^3)"): Einfach, wenn man O-Notation verstanden hat, die Inhalt einer ganzen Vorlesung war.
Frage 2 ("n! = O(nn)"): Einfach, da sogar n! <= nn, was man leicht sieht und auch in Vorlesung 3 vorkam (da spielt die Fakultät eine wichtige Rolle).
Frage 3 ("log(n!) = o(n * log n)"): Hier musste man ein zentrales Element von Vorlesung 3 (log(n!) >= C * n * log n für eine Konstante C > 0) mit einem zentralen Element von Vorlesung 4 (Verbindung zwischen O, Omega, Theta, o, omega und Grenzwerten) verbinden.
Aufgabe 2.3 (8 Punkte, Transitivität von O und o)
Diese Aufgabe war etwas schwieriger, weil bei der Definition o die Konstante C allquantifiziert ist. Viele haben schon die Definition falsch hingeschrieben, weil sie sie offenbar gar nicht verstanden haben. Dann gab es keine Punkte. Darüberhinaus zeigte sich bei dieser Aufgabe die Schwierigkeit vieler, mathematische Beweise zu führen. Ein, zwei solcher Aufgaben waren bisher bei jeder Klausur dabei.