Archiv von discourse.mafiasi.de vom Saturday September 21, 2019.

Klausurvorbereitung AD WiSe 2014/15

henning

Hallo interessierte Menschen!

Bei Diskussionen über das AD-Repetitorium formte sich die Idee, ein Thema im Discourse zu eröffnen, in dem Fragen gestellt, sowie Inhalte besprochen und diskutiert werden können. Als Einstieg haben wir uns ein paar Aufgaben überlegt, die ihr lösen könnt. Wenn ihr wollt, könnt ihr dazu gerne Fragen stellen oder euch eigene Aufgaben ausdenken. Vielleicht wisst ihr ja auch schon Bescheid und könnt Anderen ihre Fragen beantworten. Wir haben aber auch Menschen angesprochen, die hin und wieder hier rein schauen werden, um eure Fragen zu beantworten.

In Kurz: Wir möchten euch dazu motivieren:

  • Fragen zu Inhalten zu stellen, die ihr habt (und Antworten zu bekommen)
  • Die Fragen Anderer zu beantworten
  • Euch selbst Aufgaben zu überlegen

Um die Motivation etwas zu steigern fangen wir mal mit ein paar Aufgaben an:

  1. Folgendes Array ist gegeben: [20, 9, 13, 4, 5, 8, 2, 1, 1, 3, 2]. Zeichne den dazugehörigen Max-Heap als Baum. Ist die Heapeigenschaft erfüllt? Warum/warum nicht?

  2. Entferne die Wurzel des Heaps und stelle die Heap-Eigenschaft wieder her (wie? und welcher Aufwand?)

  3. Nimm das ursprüngliche Array und sortiere es. Du kannst dazu einen Algorithmus deiner Wahl nehmen. Welche Laufzeit hat der von dir gewählte Algorithmus?

  4. Bestimme die Laufzeit der binären Suche mit Hilfe des Mastertheorem (mit Begründung)

  5. Welche Datenstruktur würdest du für eine PriorityQueue verwenden (eine Queue, aus der Elemente gemäß einer Priorität entnommen werden). Begründung!

  6. Gegeben ist eine Hashmap. Welche Laufzeit hat das Einfügen von $n$ Elementen durchschnittlich? Wie ist die Laufzeit im Worst-Case, und wie sieht dieser aus (wann tritt dieser auf?)

  7. Zeige, dass $n! \in O(n^n)$

  8. In welchen Fällen sollte man Bellman-Ford statt Dijkstra verwenden, um einen kürzesten Pfad zu finden?

Viel Erfolg für die Klausur!

-- eine nicht näher bestimmte Menge von Menschen, die gerade zusammensaß wink