Datum der Prüfung:
16.7.2013
Benötigte Lernzeit als Empfehlung:
2 Wochen
Aufgaben:
Das Gedächnisprotokoll der Klausur mit allen Aufgaben und dazugehörigen Puntzahlen liegt als .pdf vor. Ich habe keine Möglichkeit gefunden, diese auf eine Fachschaftsseite hochzuladen, deshalb liegt sie vorrübergehend in der Dropbox:

https://www.dropbox.com/s/888q80fnhalseir/Klausurprotokoll.pdf

Falls der Link nicht mehr funktioniert, oder jemand eine bessere Idee als Dropbox hat bitte eine kurze Email an jonas.marasus@cms.hu-berlin.de schicken, dann lade ich die datei anderswo hoch.

= Datum der Prüfung
25.9.14

= Prüfungsfragen

O-Notation
a) Funktionen ordnen (mit Beweis) n^4/(sqrt(n)*log n); 4^(log n) * log n; n^3 -10n^2 +200
b) (ohne Begründung) je eine Funktion angeben, die
- \in o(n^3) und \in klein-Omega(log n^3) ist
- nicht \in Omega(n log n) und nicht \in O(log n) ist
- \in o(n^4) und \in Theta(n^2-\sqrt(n) +10) ist
c) Zeigen oder widerlegen: f \in Theta (g) und g \in o(h) => f \in O(h)

Sortieren
a) Idee von Countingsort erklären
b) entscheiden und begründen, ob b1) Mergesort und b2) Quicksort Vorsortierung ausnutzen
c) Gegeben sei eine Folge a_1,..,a_n. Dabei wird (a_i, a_j) mit i<j, aber a_i>a_j als sog. falsches Paar definiert. Es sollte ein Algorithmus entworfen werden, der in O(n) alle falschen Paare beseitigt, sofern nur O(n) falsche Paare vorliegen (mit Laufzeitbeweis)

BB[alpha]-Bäume
a) in gegebenem BB[alpha]-Baum für alle Knoten die Balancen angeben
b) Sei alpha zwischen 0 und 1/2 gegeben. Was muss binärer Suchbaum erfüllen, um BB[alpha]-Baum zu sein?
c) für 3 verschiedene alpha-Werte entscheiden, ob der Baum aus a) legitimer BB[alpha]-Baum ist

B-Bäume
a) ein Element in einen gegebenen B-Baum einfügen
b) ein Element aus einem gegebenen B-Baum löschen
c) Wann/warum sind B-Bäume AVL- und BB[alpha] vorzuziehen?

Hashing
a) mit linearem Sondieren
b) mit double Hashing
keine weiterführenden Fragen

Schreibtischtest zu Prim, auch ohne weiterführende Fragen

Heaps und Bäume
a) aus gegebener Zahlenfolge nach Algorithmus aus der VL einen maxHeap aufbauen
b) Hier war die Inorder- und die Preorder-Traversierung eines binären Baumes (kein Suchbaum) gegeben und man sollte daraus den Baum auslesen (Pseudocode zu Inorder- und Preorder-Traversierung war mit angegeben)
c) zwei verschiedene Bäume mit derselben Preorder-Traversierung angeben
d) Beweisen oder widerlegen: Wenn Preorder-Traversierung eines binären Suchbaumes vorliegt, lässt sich daraus eindeutig der Baum bestimmen.

Beweisaufgabe zu Bäumen und einem gegebenen Pseudocode-Algorithmus - hatte leider keine Zeit, mich hiermit zu beschäftigen

Graphalgorithmen
Hier war (verbalisiert) ein All-pairs-shortest-path-Algorithmus gegeben, der u. a. Bellman-Ford und Dijkstra als Teilschritte benutzte
a) Schreibtischtest zu gegebenem Graph
b) Laufzeiten der Teilschritte und Gesamtlaufzeit angeben
c) und d) kleinere Beweise zu Zwischenergebnissen des Algorithmus
e) mit Hilfe der Erkenntnisse aus c) und d) Korrektheit des Gesamtalgorithmus zeigen

= Note (Optional)
2.x

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Die Küraufgaben waren zeitlich kaum zu schaffen (letzlich wurden dann aber auch 10 Punkte aus der Wertung rausgenommen). 

= Datum der Prüfung
25.9.14

= Prüfungsfragen

O-Notation
a) Funktionen ordnen (mit Beweis) n^4/(sqrt(n)*log n); 4^(log n) * log n; n^3 -10n^2 +200
b) (ohne Begründung) je eine Funktion angeben, die
- \in o(n^3) und \in klein-Omega(log n^3) ist
- nicht \in Omega(n log n) und nicht \in O(log n) ist
- \in o(n^4) und \in Theta(n^2-\sqrt(n) +10) ist
c) Zeigen oder widerlegen: f \in Theta (g) und g \in o(h) => f \in O(h)

Sortieren
a) Idee von Countingsort erklären
b) entscheiden und begründen, ob b1) Mergesort und b2) Quicksort Vorsortierung ausnutzen
c) Gegeben sei eine Folge a_1,..,a_n. Dabei wird (a_i, a_j) mit i<j, aber a_i>a_j als sog. falsches Paar definiert. Es sollte ein Algorithmus entworfen werden, der in O(n) alle falschen Paare beseitigt, sofern nur O(n) falsche Paare vorliegen (mit Laufzeitbeweis)

BB[alpha]-Bäume
a) in gegebenem BB[alpha]-Baum für alle Knoten die Balancen angeben
b) Sei alpha zwischen 0 und 1/2 gegeben. Was muss binärer Suchbaum erfüllen, um BB[alpha]-Baum zu sein?
c) für 3 verschiedene alpha-Werte entscheiden, ob der Baum aus a) legitimer BB[alpha]-Baum ist

B-Bäume
a) ein Element in einen gegebenen B-Baum einfügen
b) ein Element aus einem gegebenen B-Baum löschen
c) Wann/warum sind B-Bäume AVL- und BB[alpha] vorzuziehen?

Hashing
a) mit linearem Sondieren
b) mit double Hashing
keine weiterführenden Fragen

Schreibtischtest zu Prim, auch ohne weiterführende Fragen

Heaps und Bäume
a) aus gegebener Zahlenfolge nach Algorithmus aus der VL einen maxHeap aufbauen
b) Hier war die Inorder- und die Preorder-Traversierung eines binären Baumes (kein Suchbaum) gegeben und man sollte daraus den Baum auslesen (Pseudocode zu Inorder- und Preorder-Traversierung war mit angegeben)
c) zwei verschiedene Bäume mit derselben Preorder-Traversierung angeben
d) Beweisen oder widerlegen: Wenn Preorder-Traversierung eines binären Suchbaumes vorliegt, lässt sich daraus eindeutig der Baum bestimmen.

Beweisaufgabe zu Bäumen und einem gegebenen Pseudocode-Algorithmus - hatte leider keine Zeit, mich hiermit zu beschäftigen

Graphalgorithmen
Hier war (verbalisiert) ein All-pairs-shortest-path-Algorithmus gegeben, der u. a. Bellman-Ford und Dijkstra als Teilschritte benutzte
a) Schreibtischtest zu gegebenem Graph
b) Laufzeiten der Teilschritte und Gesamtlaufzeit angeben
c) und d) kleinere Beweise zu Zwischenergebnissen des Algorithmus
e) mit Hilfe der Erkenntnisse aus c) und d) Korrektheit des Gesamtalgorithmus zeigen

= Note (Optional)
2.x

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Die Küraufgaben waren zeitlich kaum zu schaffen (letzlich wurden dann aber auch 10 Punkte aus der Wertung rausgenommen). 

= Datum der Prüfung
10.9.15
= Benötigte Lernzeit als Empfehlung
4 Wochen
= Verwendete Materialien (Bücher, Skripte etc...)
Folien aus Vorlesung, Übung, Tutorium; Internet; Ottmann/Widmayer
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
dritter Prüfungsversuch -> starke Nervosität
Leser beginnt mit etwas Smalltalk (Wie läuft das Studium? Warum 2 mal durchgefallen), Beisitzer waren A. Nonym und ein Protokollant, Stift und Papier wird gestellt
Beisitzer sagen nichts
= Prüfungsfragen
Quick Sort --- wie funktioniert es genau? Komplexität von Worst/Average/Best-Case herleiten - kein genauer Beweis aber gut argumentieren können
Merge Sort --- wie funktioniert es genau? Komplexität von Worst/Average/Best-Case herleiten - kein genauer Beweis aber gut argumentieren können
Suchbäume --- Definition, Wie groß?, Kosten von Einfügen/Löschen, wie funktioniert das Löschen
Starke/schwache Zusammenhangskomponenten --- Was ist das? Wie berechnet man das? Kosaraju-Algorithmus ausführen
= Note (Optional)
bestanden ;)
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Die behandelten Themen werden sehr detailliert behandelt, Leser hilft bei Unsicherheiten weiter, Prüfung ist eher schlecht gelaufen

= Datum der Prüfung
30.11.15
= Benötigte Lernzeit als Empfehlung
Ich habe mich 2 Wochen im voraus auf die Prüfung vorbereitet. 
= Verwendete Materialien (Bücher, Skripte etc...)
Ich bin sämtliche Foliensätze durchgegangen und habe Definitionen herausgearbeitet. Der Prüfer möchte ungern den Bereich des Lernens eingrenzen, dennoch werde keine Bewesie oder ähnliches in der Prüfung besprochen. 
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Herr Leser war sehr freundlich. Leitete das Gespräch und nahm mir die Nervösität, durch ein wenig Smalltalk, zum Beginn der Prüfung. 
Die Beisitzer enthalten sich eigentlich den Gesprächen. 
= Prüfungsfragen
Leser hatte mir im voraus gesagt, das Sortierverfahren ein beliebtes Thema seien. Demnach besprachen wir Quick- und Mergesort. Er wollte für jedes Verfahren eine kurze Erklärung, eine Konstelation von Best- und WorstCase und anhand dieser erklärt bekommen, wie die Fälle zustande kommen. 
Danach ging er zum Thema "Hashing" über. Wozu macht man dies?, Welche Strategien gibt es? (Overflow, Open) Welche Unterschiede besitzen sie? Genaue Beispiele beider Strategien(direct chainning/seperate chainning; lineares H., double H.). 
Zum Schluss stellte er mich vor die Wahl: Suchbäume oder Graphen - Suchbäume war meine Wahl:
Was sind allgemein Suchbäume? Min und Max Höhe eines Suchbaumes und zum Schluss das Löschen eines Knotens in einem Suchbaum. 
= Note (Optional)
Ich habe mit 3.0 bestanden. Konnte auf vieles eine Antwort geben. Es haben aber Zusammenhänge zwischen einzelnen Aussagen gefehlt, weswegen die Note zustande kam. 
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Sehr angenehme Prüfung. 
Man sollte vieles hinterfragen beim Lernen, sodass man wirklich sämtliche Zusammenhänge gut formuliert wiedergeben kann. Er wird viel hinterfragen!

= Datum der Prüfung
01.08.2016

= Benötigte Lernzeit als Empfehlung
ca. eine/anderthalb Wochen

= Verwendete Materialien (Bücher, Skripte etc...)
Folien aus der Vorlesung, Übung und dem Zusatztutorium; Übungsblätter; Youtube-Videos; zusätzliches Material, auf das Übungsleiter verwiesen hatten

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
sehr organisiertes und entspanntes "Vor der Prüfung"

= Prüfungsfragen
1.) AVL-Bäume: Balancen angeben, Elemente hinzufügen und löschen 

2.) Quellcode für Trie-Implementierung gegeben: Nachvollziehen, was der Code macht und konzeptuellen Fehler finden
a) Trie zeichnen für add()-Funktion
b) Instanz mit 5 Elementen finden, in der die Funktion contains(eis) falsche Ausgabe zurückgibt
c) Konzeptuellen Fehler in der Implementierung aufdecken und Verbesserungsvorschlag angeben

3.) Kruskal-Schreibtischtest für Minimale Spannbäume

4.) Hashing:
Schreibtischtest für Offenes Hashing mit
a) linearer Sondierung und
b) Double Hashing
c) Beurteilen, ob die gegebenen Funktionen Hash-Funktionen sind oder nicht mit Begründung
d) Entscheiden, ob die zuvor verwendete Hash-Funktion sich gut eignet (mit Begründung)

5.) Datenstrukturen
a) Entscheiden, ob gegebene Bäume AVL-Bäume, Suchbäume, Max-Heap oder Min-Heap sind
b) Min-Heap aus einer Reihe von angegeben Zahlen aufbauen
c) Angabe von Laufzeiten für Extrahieren des Minimums aus MinHeap, MaxHeap, binärem Suchbaum, AVL-Baum 
d) Implementierung der Funktionen dequeue und enqueue der Datenstruktur Queue mit einem binären Suchbaum + Angabe von Laufzeiten; Beurteilen, wie sich die Laufzeiten für AVL-Bäume ändern würden

6.) Landau-Notation
a) Funktionen aufsteigend ordnen
b) zeigen, dass (1) 2^(n^3) in O(2^(2n^3) und (2) log n in O(sqrt(n)/log n) 
c) Beweisen, (1) Transitivität für Omega (f in Omega(g) und g in Omega(h) -> f in Omega(h) und (2) o(f) ist Teilmenge O(f)

7.) Sortierverfahren 
a) Entscheiden, ob Instanzen für bestimmte Laufzeiten mit bestimmten Sortierverfahren existieren
- Mergesort Theta(n)
- Heapsort Theta(n)
- Heapsort Theta(log n)
- Bubble/Quicksort Theta(n2)
- Bubblesort Theta(n log n) 
b) Sortierverfahren selbst entwickeln für einen Array [a1,...ai] mit k Klippen, wobei eine Klippe ein Element ist, für das gilt: für 1<=i<n, ai > ai+1: Sortierverfahren sollte in O(n log k) sein
c) Nutzung von Vorsortierung bei Bubblesort, Heapsort einschätzen

8) Suchverfahren 
a) Einschätzen, ob für gegebene Funktion contain(value) (1) lineare Suche und (2) binäre Suche geeignet
b) Angeben, wie man Funktion contain(value) in log n implementieren kann

9)  Algorithmen Entwurf: Gegeben war eine Liste A von Anträgen (A= {a2, a17, a83, b56 c53, ....}, die gestellt werden müssten. Hier gab es bestimmte Abhängigkeiten, z.B. Antrag a83 kann erst nach Antrag b56 gestellt werden. Diese Abhängigkeiten waren als Menge D von Tupeln gegeben (D = { (a2, a13), (a2, b56), (b56, a83), ...})
(a) Angabe einer Reihenfolge, in der die gegebenen Anträge ohne Konflikte gestellt werden können.
(b) Angabe eines Algorithmus zur Allgemeinen Feststellung solcher Reihenfolgen für beliebige A und D. Welche Datenstrukturen sollten verwendet werden? Welche Laufzeit hat der Algorithmus? (Punktevergabe gestaffelt nach Laufzeit mit idealerweise O(|A|+|D|)).

= Note (Optional)
2.x

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Fair gestellte Aufgaben, aber zeitlich knapp bemessen; Bewertung fiel (wesentlich) besser als erwartet aus

Datum: 29.09.2017
Zeit: 150 Minuten
Hilfsmittel: Keine
Atomsphäre: Sehr gute und ruhige Atmosphäre, Prof und Helfer / Korrektoren alle sehr freundlich :)
Lern-Materialien: Leute ihr müsst zu jeder Vorlesung und Übung. 
In der Klausur wurde so ziemlich alles abgefragt.
Viel Zeit zum Überlegen war nicht, ihr lest euch die Aufgabe durch und müsst
die sofort bearbeiten. Sonst scheiterts zeitlich.
Lest euch aber die Aufgaben SORGFÄLTIG durch. Nicht nur den ersten Satz durchlesen
und denken "ach so geht das" und dann einfach loslegen. Wisst ihr bestimmt, aber will ja nur sagen.. ^^
Neben Vorlesung und Übung gibt es natürlich auch genug guten Stoff im Internet, insbesondere
auf Wikipedia, stack overflow und youtube.
Naja ich hoffe dieses Gedankenprotokoll wird einigen von euch helfen. Ich hatte genug Stress und Angst mit der Prüfung, und
mir dabei noch alles zu merken was gefragt wurde war für mich persönlich etwas zu viel.
Aber ich habe mein Bestes getan und ich hoffe ihr werdet alles gut überstehen :)

FYI: Die Reihenfolge der Aufgaben ist falsch.

1.1 Zahlenfolge gegeben. Trage die Zahlen in Hashtabelle ein mit linearer Sondierung
1.2 .. mit doppeltem Hashing
1.3, 1.4 Weitere Aufgaben zu Hashing, irgendwas mit Tombs (haben aber nicht so viele Punkte gebracht)

2. Array mit Zahlen gegeben
2.1 Mergesort (grafisch darstellen)
2.2 Bucketsort mit Alphabet {0,1,2} (grafisch darstellen)
2.3 Worst- und Best-Case von: Mergesort, Bubblesort, Quicksort angeben

3. Suche
3.1 Funktionsweise von binärer Suche und Interpolationssuche kurz erläutern
3.2 Zwei verschiedene allgemeine Anordnung von Arrays. Worst- und Best-Case von
    Binärer Suche, Interpolationssuche und Fibonacci Suche angeben

4. Heaps
4.1 Kann man Heapsort in-place implementieren, ohne die Laufzeit zu strapazieren (mit Begründung)
4.2 Worst-Case Laufzeit angeben, um in einem max-Heap das zweitgrößte Element zu finden (ohne Löschen)
4.3 Worst-Case Laufzeit angeben, um in einem min-Heap das zweitgrößte Element zu finden (ohne Löschen)
4.4 Worst-Case Laufzeit angeben, um in einem AVL-Baum das zweitgrößte Element zu finden (ohne Löschen)

5. (AVL-)Bäume
5.1 AVL-Baum einen bestimmten Knoten entfernen -> Rotationen erforderlich
5.2 größerer AVL-Baum einen bestimmten Knoten entfernen -> Rotationen erforderlich
5.3 binärer Suchbaum gegeben, wobei die Knoten Buchstaben waren. Finde geheime Nachricht
(pre-order / post-order / in-order Traversierung erforderlich)

6. Amortisierte Analyse
Kam völlig unerwartet, kann leider keine Infos dazu geben.

7. Allgemein Algorithmenentwurf
7.1 Erstelle Algorithmus, der erkennt, ob ein Array eine Permutation des anderen Arrays ist, in O(nlogn)
7.2 .. in O(n)
7.3 Vergessen..

8.
8.1 4 Funktionen gegeben, ordne nach asymptotischen Wachstum (ohne Begründung)
8.2 Das gleiche für 4 andere Funktionen
8.3 Zwei Funktionen f,g gebeben. Zeige, dass f in O(g)
8.4 Zeige, dass f nicht in O(g)
8.5 Beweise, dass es eine Funktion gibt, sodass gilt: f ist in O(g) UND f ist in Omega(g)
8.6 Das gleiche nur mit klein o und klein Omega

9.
Aufgabe mit sehr viel Text und einer Adjazenzmatrix gegeben. 
Floyd-Warshall Algorithmus war gefragt, war aber nicht direkt
vom Text ersichtlich.
9.1 Finde einen Weg von s1 nach s7, wobei die maximale Anzahl von Knoten vorkommen (4 Punkte)
9.2 Entwerfe Algorithmus, der irgendwelchen Weg zwischen zwei Knoten ermitteln, sry vergessen (6 Punkte)
9.3 Vergessen (3 Punkte)

10. Minimaler Spannbaum
Tabellle gegeben. Trage jeden einzelnen Schritt vom Kruskal Algorithmus in Tabelle
und zeichne den durch Kruskal entstandenen Graphen.

= Datum der Prüfung: 26.Sep.2019

= Prüfungsfragen
Es fehlen bei manchen Aufgaben eventuell Teilaufgaben. Hilfsmittel waren nicht erlaubt.

6 Aufgaben à 20 Punkte 

1. Landau

a) Funktionen aufsteigend nach asymptotischem Wachstum ordnen. Ein Beweis ist nicht nötig.

dritte √n^2
√n * ln(3)
√ln * ln(√n)
5 * ln(n^5)

b) Beweisen Sie n(ln)... klein omega  Geschnitten ... klein o (...)

c) Beweisen Sie 
g ∈ O(f) und f ∈ Ω(h), dann f ∈ Ω max(g,h)


2. Hashing

(1)
Werte 22,44,15,51,65 in dieser Reihenfolge in eine Hashtabelle einfügen, mit
a) linearem Sondieren. h(k)=k mod 7. 
b) geordnetem Hashing auf Grundlage von doppeltem Hashing. h'(k)=1+(k mod 3). s(i,k)=(h(k) - j * h'(k)) mod 7    mit 0<=j<7

(2)
Bestimmen Sie ob es sich um geeignete Hashfunktionen handelt. (Mit Overflowhashing bei Kollision). Für eine Hashtabelle von 0 bis n-1 mit n Werten
a) h(k)= k/n abgerundet
b) h(k)= (k * random (nicht deterministisch Zahl von 1 bis n)) mod n
c) h(k)= 1
d) h(k)= k mod n

Geben Sie für die Funktionen, die Sie als geeignet bezeichnet haben an wie gut Sie sind (Gibt es viele Kollisionen oder so etwas war gemeint. wieder mit overflow)


3. Algorithmenanalyse

a)
Gegeben war ein Array A=[7,5,3,4,4]
Im Code wurde ein Array B und ein Array C mit 0 indiziert. Die hatten eine Länge von irgendwas i...z 
Man sollte 
(i) nach der ersten forschleife das Array B angeben.
(ii) nach der zweiten forschleie das Array B angeben
(iii) für das Array B und C nach jedem durchlauf der dritten forschleife die Werte angeben
(vi) Worstcase Laufzeit des Algos abhängig von n und z angeben.

die forschleifen waren nacheinander, die erste und dritte lief von 1 bis n und die zweite von 2 bis z. Es ist nicht viel passiert aber alles sehr nervig notiert um durcheinander zu kommen. sowas wie C[B[A[i]]]=B[A[i]] + 1


4. Heaps

(1)
Gegeben waren drei Zeichnungen für die man in einer Tabelle bestimmen sollte ob es sich um Min/Max heap, Binären Suchbaum oder AVL-Baum handelt. Mehreres war möglich.

(2)
Build-heap Schreibtischtest 

(3)
Was ist die Worstcase Laufzeit um das zweitgrößte Element zu finden (mit Begründung)
a) aufsteigend sortierte einfach verkettete Liste
b) Max-Heap
c) AVL-Baum

(4)
k Arrays die aufsteigend sortiert sind und alle jeweils mindestens ein Element enthalten sollen zu einem einzigen Array zusammengefügt werden, welches aufsteigend sortiert ist. Volle Punktzahl wenn in O(log(k) * n * k).


5.

(1) 
Gegeben war ein nicht ganz korrekter Code, um zu bestimmen ob ein Klammerausdruck wohlgeformt ist (also "(([]))" soll true zurück geben, aber "(()))))))" soll false zurück geben).

a) Finde ein Beispiel für nicht wohlgeformt bei dem wegen des Fehlers nicht false zurück gegeben wird.

b) erkläre den Fehler (Es waren int Variabeln für die jeweiligen Klammertypen angelegt und mit switch case bei offener +1 und bei geschlossener -1 gerechnet. False wurde nur zurück gegeben wenn ein wert <0. Wenn also am Ende zu viele offene Klammern da waren oder wenn die Reihenfolge nicht stimmte, wurde das nicht abgefangen)

c) Schreibe einen korrekten Pseusocode der das Problem löst. Als Hinweis wurde Stack empfohlen

(2)
Angenommen es gibt ein nicht-stabiles Sortierverfahren N, dann überlegen Sie ein stabiles Sortierverfahren S, dass in O(n) auf Grundlage von N sortiert.

(3)
Eine Erklärung dazu was stabil bedeutet. Beweisen oder widerlegen Sie für die Implementierung von Quicksort aus der Vorlesung ob stabil


6. Floyd Warshall

(1) Schreibtischtest

Knoten C gerichtete Kante zu A
A gerichtete Kante zu D und E
D gerichtete Kante zu E
E gerichtete Kante zu B
B gerichtete Kante zu E

Jede Kante war scheinbar 1 Wert.

(2)
Beweis für Radius eines Graphen. Es war erklärt was der Radius ist. für ungewichtete, ungerichtete Graphen

(3)
Beweis, dass es mehr als einen minimales Knoten, also mit kleinstmöglichem Radius, in einem Graphen gebgen kann.

= Datum der Prüfung: 13.11.2019
= Benötigte Lernzeit als Empfehlung: 4 Wochen
= Verwendete Materialien: Bücher, Vorlesungsfolien, Altklausuren, Prüfungsprotokolle
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer: Die Prüfung war sehr angenehm. Ich war etwas nervös, weil es mein Drittversuch in diesem Modul war. Zuerst haben wir uns allgemein über das Studium unterhalten, danach haben wir mit der Prüfung begonnen. Prof Leser hilft einem auf die Sprünge, wenn man gerade nicht weiterkommt.
= Prüfungsfragen:

*QuickSort erklären*
->zwischendurch unterbrochen um nachzufragen
-Was passiert genau in diesem Schritt?
-Funktionen divide und quicksort
-Wieso wählen wir das Pivotelement so?
-WC/BC/AVC?
-Wie wurde der AVC in der Vorlesung bewiesen?

*Weiteres divide & conquer Verfahren?*
MergeSort
-> Fragen ähnlich wie bei QuickSort

*Gibt es Sortierverfahren die nicht durch Vergleiche sortieren?*
Meine Antwort: CountingSort-kurz erklärt
-> ist zwar richtig, aber er wollte auf BucketSort hinaus
BucketSort kurz die Idee erklärt (Laufzeit)

*Suchbäume*
-> Operationen/Laufzeiten/sym. Vorgänger/Nachfolger

*starke Zusammenhangskomponente*
-> Definition

-
= Note (Optional): 2.3

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...):

Alles in Allem fand ich die Prüfung entspannter als ich mir sie vorgestellt hab. Ich musste oftmals etwas länger überlegen, aber die Stille war nie zu lang. Entweder kam eine neue Frage oder Prof Leser hat versucht mir zu helfen. Er fragt auch mal nach Begriffen, die man selbst erwähnt hat(Beispiel: -QuickSort ist ein allgemeines Sortierverfahren,dh es sortiert nur durch Vergleiche-
-> *Nennen Sie ein Sortierverfahren, welches nicht durch Vergleiche sortiert*). Ich empfehle jedem, der einen Drittversuch hat, diesen mündlich zu machen, weil es weniger riskant scheint.

= Datum der Prüfung : 10.08.2021
Insgesamt 120 Punkte und 150 Minuten Zeit
= Prüfungsfragen:
1.a)Beweisen oder Wiederlegen sie für folgende Funktionspaare die beiden Aussagen 
f in O(g) und f in Omega(g) (3*4 Punkte)

i: (2+n)^n und 2^n
ii: 3n^2+5n+3 und 2n^3+5n
iii: Wurzel(n) und log(n^2)

b) Sei f0 in O(f) und g0 in O(g). Beweisen sie g0+f0 in O(max(f,g)) (4 Punkte)

c) Beweisen sie o(f) geschnitten Omega(f) = Leere Menge (4 Punkte)

2.a) In einem sortierten Array der Länge n werden k nicht aufeinanderfolgende Zahlen durch zufällige andere ersetzt. Geben sie einen Algorithmus an, der dieses Array in O(n+k*log(k)) löst und begründen sie die Laufzeit.

b)Ein Tal-Array ist ein bis zu einem index i abwärts sortiertes und ab i aufwärts sortiertes Array. 
Gegeben ist ein Algorithmus foo
foo(Array C):
i=1
j=n
while(true):
  if(i<n and C[i]>C[i+1])
     i++
  elsif j>1 and C[i]>C[i-1])
     j--
  elseif(i==j)
     return C[i]
  else
     return -1

i) was gibt foo für das Tal-Array A[59,50,35,31,29,34,40,49] aus
ii) was macht der Algorithmus generell
iii) was ist die Komplexität

3. Schreibtischtest Quicksort für [5,13,17,2,3,11,7]
4.a) Hashtabelle Schreibtischtest mit linearer und doppelter Sondierung 
b)sind folgende Funktionen zum Hashen mit overflow einsetzbar?
h(k)= 2k/n abgerundet
h(k)=0
h(k)=k*(nicht deterministische random zahl) mod n
h(k)=k+c mod n
b) sind die die einsetzbar sind gut um Kollisionen zu vermeiden (mit Begründung)?
c)i)Folgende Hashtabelle gegeben: _,_,16,10,19,5,_,_,_,_,_
Geben sie eine Hashfunktion und Einfügereihenfolge an damit die Tabelle rauskommt (Sondierung ist s(k,j)=h(k)-1)
ii)wie wahrscheinlich ist es, dass die nächste Zahl an der Position 1 landet
iii) wie viele Kollisionen treten durchschnittlich auf, wenn man eine Zahl in diese Tabelle einfügt

4. Ein Array ist gegeben und man soll buildHeap darauf ausführen und dabei nach jedem swap den Heap zeichnen (6 Punkte)
delete min auf einem Heap und wiederum nach jedem swap zeichnen (4 Punkte)

5. Entwerfen sie einen Algorithmus, der in O(n) true zurückgibt, wenn der Baum balanciert ist (im sinne eines AVL Baums, also mit höhe rechts-links <=+-1) und ansonsten false. Platzverbrauch egal, der Baum darf jedoch nicht modifiziert werden. (Schwierigkeit war (für mich) dass man bei rekursion nicht die Höhe sondern nur true oder false zurückgeben durfte)

6. Schreibtischtest Prim Algorithmus an einem Graphen ( genauso wie Aufgabe 5 bei der Probeklausur 2019)

7.Es ist ein azyklischer ungerichteter gewichteter Graph gegeben, der ein Wasserverteilungssystem darstellen soll mit einer Quelle q.
  q a b c d e f g h i
q     1       
a         2      
b 1     9   2     
c     9
d   2             3
e     2           3
f                   3
g                 2
h         3 3   2   2
i             3   2
(Graphisch(lol) angegeben, nicht als Tabelle)
a)Geben sie die Adjazenzliste an
b) wie lange braucht das Wasser Bis es alle Knoten erreicht hat
c) geben sie einen Algorithmus an, der b für azyklische Graphen ausrechnet.( Ich glaube in O(n^2)

= Datum der Prüfung: 31.07.2024
= Benötigte Lernzeit als Empfehlung
= Verwendete Materialien: Folien, Internet, Probeklausuren

Aufgabe 1 O-Notation und Mastertheorem
1.1 4 Paare von Funktionen f und g. Es war anzukreuzen, ob f Omega(g) oder g Omega(f)? (Bin mir nicht sicher ob es Omega oder O war)

1.2 Zeige am Entscheidungsgraph, warum es keinen allgemeinen Sortieralgorithmus geben kann, der schneller als Omega(n!) ist

1.3 Irgendwas mit Beweise, dass log(n!) element Omega(n log n)

1.5? Wende das Mastertheorem an und gib jeweils eine Funktion g(n) an, so dass T(n) in Θ(g) ist. (Das Mastertheorem mit den drei Fällen war gegeben.):

T(n) = 16T(n/4) + n^2 + 3n
T(n) = 81T(n/3) + n^(7/2)


Aufgabe 2 Sortieren

k-MergeSort Algorithmus war als Pseudocode mit kurzer Erklärung gegeben: Im Prinzip teilen wir bei MergeSort solange, bis die Teile kleiner als k sind. Die Teile dann mit BubbleSort sortieren und dann wie bei MergeSort zusammenfügen.

2.1 Schreibtischtest für 4-MergeSort ausführen auf einer gegebenen Instanz von 13? Elementen.

2.2 Eine Best-Case und eine Worst-Case Instanz für 4-MergeSort angeben.

2.3 Wahr oder Falsch? Mit Begründung bzw. Sortierverfahren
Lässt sich Array A der Länge 3n in O(n) sortieren, wenn man folgende Eigenschaft des Arrays kennt:
Das Array besteht aus sortierten Tripeln. Z.B. [3, 9, 34, 5, 12, 19, 1, 4, 7]
Das erste, mittlere und letzte Drittel des Arrays sind für sich sortiert, z. B. [5, 12, 30, 52, 2, 6, 13, 20, 1, 7, 15, 42]

Aufgabe 3 Datenstruktur

Es soll eine Datenstruktur gefunden werden, die kompakte Intervalle speichert. Jedes Intervall enthält dabei die 0. 
Die Operation query(x) soll alle Intervalle ausgeben, in denen x enthalten ist und zwar in O(k). k ist dabei die Anzahl an Intervallen, in denen x vorkommt.

3.1 Eine solche Datenstruktur beschreiben. (Vorprozessierung darf beliebig lang dauern)

3.2 Begründen warum bei der Datenstruktur aus 3.1 query() in O(k) läuft.

Aufgabe 4 Heaps

4.1 Erstelle einen Heap mit dem Bottom-Up-Sift-Down Verfahren, bei dem alle Elemente gleichzeitig eingefügt werden. (Der Start in Heap-Form war gegeben und man sollte den „Heap“ nach jeder Swap-Operation aufschreiben. Die Grundstruktur war schon gegeben, man musste nur die Label eintragen.)

4.2 Schreibtischtest der deleteMin() Operation auf einem gegebenen Heap

4.4? Laufzeit von Dijkstra unter Verwendung eines Binären Heaps bzw. eines Fibonacci Heaps als Prioritätswarteschlange.

Aufgabe 5 Graphen

5.1 Führe den Dijkstra-Algorithmus auf dem gegebenen Graphen aus. (Schreibtischtesttabelle wie in der Übung mit Angabe der Prioritätswarteschlange)

5.4? Finde einen Algorithmus der in O(|V| + |E|) Laufzeit und mit O(n) Speicher herausfindet, ob ein gegebener Graph bipartit werden kann.

5.6? a) Wie lautet die Schnitteigenschaft eines minimalen Spannbaums?
b) Wie lautet die Kreiseigenschaft eines minimalen Spannbaums?

Aufgabe 6? Hashing 

6.1 Führe die folgenden insert() und delete() Operationen aus. Dabei soll lineares Sondieren benutzt werden. Eine Tabelle für die einzelnen Schritte und den Array Indizes war angegeben.

Funktion war glaube einfach f(n) = n mod 13 und bei Kollisionen sollte f(n) - i mod 13 bentutzt werden

6.2 Nenne 2 Eigenschaften einer guten Hashfunktion