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.
Aufgabe 3.1 (5 Punkte, Hashing mit offener Adressierung)
Diese Aufgabe war sehr einfach, mit dem einzigen Kniff, dass man sich das Leben hier deutlich einfacher machen kann und sollte, indem man die Hashfunktion zuerst zu h(x) = x - 2 mod 5 vereinfacht. Dass man hier nicht 26 * 1981 - 137 ausrechnen musste, ergab sich aus vielen Hinweisen aus der Vorlesung.
Aufgabe 3.2 (7 Punkte, schlechtes Verkleinerungsregel bei dynamischem Feld)
Wie das im Pinzip geht, war wesentlicher Inhalt von Vorlesung 6 (es stand auf Folie 20). Man musste es nur noch für die konkret in der Aufgabe gegebene Regel ausarbeiten. Dabei wurde sehr viele Fehler gemacht. Zum Beispiel haben sehr viele gesagt, dass das Feld schon nach einen pop wieder verkleinert wird, was einfach nicht so ist, wenn man sie die Zahlen anschaut.
Aufgabe 3.3 (8 Punkte, Wahr-Falsch-Fragen zum Mastertheorem)
Frage 1 ("Summe T_i = O(n + Phi_0)"): Einfach, das war genau das Mastertheorem aus der Vorlesung 6 (Folie 29).
Frage 2 ("Alternative Bedingungen"): Dazu muss man sich den Beweis des Mastertheorems hinschreiben.
Frage 3 ("Frage bezüglich der Bedinungen"): Dito.
Frage 4 ("Erfüllt T_i = O(1) und Phi_i = i die Bedinungen"): Man muss es einfach nachprüfen, kein besonderer Trick.
Viele haben Frage 2 und Frage 3 falsch beantwortet, weil sie das Mastertheorem nicht richtig verstanden haben. Dadurch haben sie dann 0 Punkte für die ganze Aufgabe bekommen (wobei auch viele noch eine der anderen beiden Aufgaben falsch beantwortet haben). Sie hätten diese beiden Fragen unbeantwortet lassen sollen. Es fehlt offenbar die Wahrnehmung dafür, ob man es verstanden hat oder nicht (eines der größten Hindernisse beim Lernen und Verstehen).
Ergibt sich aus dem Beweis des Mastertheorems