Übungsblätter

Lösungsideen

Blatt 1

2. Die Idee ist, einen Turnierbaum aufzubauen. Dazu sollte für jedes Element gespeichert werden, aus welcher Richtung es kam. Am Ende steht dann (nach n-1 Vergleichen) das kleinste Element an der Wurzel. Im Laufe des Turniers muss das zweitkleinste gegen dieses Element verloren haben. Man muss also den Pfad des kleinsten Elements hinablaufen und alle Elemente, mit denen es verglichen wurde, gegeneinander vergleichen. Da wir hier einen Binärbaum haben haben wir unter der Wurzel noch log(n) Schichten, so dass hier log(n)-1 Vergleiche genügen.
3. Anstatt eines Turnierbaumes sollte hier ein Weak-Heap verwendet werden. Ein (Min-) Weak-Heap lässt sich mit n-1 Vergleichen aufbauen (heapify), so dass dann das kleinste Element an der Wurzel steht. Wegen der Weak-Heap Eigenschaft, dass alle Elemente im rechten Teilbaum kleiner sind, aber nichts über die Elemente im linken Teilbaum bekannt ist, ist klar, dass das zweitkleinste Element innerhalb des linkesten Pfades (wenn man vom rechten Nachfolger der Wurzel aus immer dem linken Nachfolger folgt) liegt. Dieser Pfad hat wiederum eine Länge von log(n), so dass auch hier erneut log(n)-1 Vergleiche hinzukommen.
4. Hier sei auf die Notizen Lower bounds for selection of maximum, minimum, second smallest element and the median von Jørgen Bang-Jensen verwiesen, zu finden auf seiner Webseite (Link "Notes on lower bound proofs by J. Bang-Jensen in PDF"). Der Beweis hierzu ist in Abschnitt 5 ab Seite 5. Die grundlegende Idee ist, einen Gegenspieler zu betrachten, der für einen gegebenen Algorithmus eine Sequenz geben soll, die mindestens n+log(n)-2 Vergleiche bei Verwendung des gegebenen Algorithmus bewirkt. Dazu muss er sicherstellen, dass das kleinste Element mit mindestens log(n) anderen Elementen verglichen wird, unter denene sich dann das zweitkleinste befinden muss.
2. Die Idee stammt aus der Dissertation von H.B. Demuth von 1956 (Seiten 41-43). Sie wurde später von Lester Ford, Jr. und Selmer Johnson zum Merge Insertion Algorithm (siehe etwa Wikipedia), der in der nächsten Teilaufgabe gefragt war.
3. siehe vorherige Teilaufgabe
5. Hier ging es im Wesentlichen darum, dent Teil (Θ+1-2^Θ) abzuleiten und die Ableitung gleich Null zu setzen. Das Ergebnis lässt sich dann in die ursprüngliche Formel einsetzen.
2. In Adaptive Heapsort wird zunächst der Kartesische Baum konstruiert (O(n) Vergleiche). Das eigentliche sortieren läft dann über einen Heap: die Wurzel des Kartesischen Baums wird zunächst allein in den Heap gepackt. Danach geht der Algorithmus so, dass die aktuelle Wurzel des Heaps entfernt wird (Delete Min; 2log(n) Vergleiche) und anschließend die Nachfolger dieses Elementes vom Kartesischen Baum in den Heap eingefügt werden (jeweils ein Insert; log(n) Vergleiche). Damit kommt man auf insgesamt n Delete Mins und n Inserts, also 3n⋅log(n) Vergleiche.
3. Die Idee ist einfach, jeweils ein Delete Min mit einem Insert zu verknüpfen: statt erst das Delete Min auszuführen und dann das Insert, wird das neue Element erst hinten an den Heap angehängt und dann das eigentliche Delete Min durchgeführt. Damit spart man sich mindestens die Hälfte aller Inserts: Im Kartesischen Baum hat jeder Knoten höchstens zwei Nachfolger. Damit folgen auf ein Delete höchstens zwei Inserts. Das jeweils erste können wir mit dem vorhergehenden Delete zusammenführen, so dass höchstens noch n/2 Inserts übrig bleiben.
4. Bei einem Weak Heap sieht das Ganze sehr ähnlich aus, nur dass die Delete Min Operation hier log(n), statt 2log(n) im Heap, kostet. Durch den Trick der letzten Teilaufgabe ergibt sich die Laufzeit sofort.
5. An dieser Stelle war nach Multipartite Priority Queues gefragt. Diese wurden 2008 von Amr Elmasry, Claus Jensen und Jyrki Katajainen in den ACM Transactions on Algorithms vorgestellt (Titel: "Multipartite Priority Queues").

Blatt 2

1. Trivial: Element i in Bucket i, fertig.
2. Zwei Arrays mit jeweils sqrt(C+1)+1 Elementen - hier also jeweis 10 Elemente. Das kleinste nicht-leere Bucket des oberen Arrays wird im unteren Array detailliert aufgedröselt, während im oberen Array die anderen Buckets durchaus mehrere verschiedene Elemente enthalten können.
3. Ein Radix-Heap besteht aus Buckets unterschiedlicher Größe. Das erste fasst ein Element, das zweite ebenfalls, das dritte zwei, das vierte vier, das fünfte acht etc. Zusätzlich verwaltet man (zumindest die unteren) Schranken der Buckets: Nur Elemente, deren Wert mindestens so groß wie die Schranke des aktuellen Buckets aber kleiner als die Schranke des nächsten Buckets sind, dürfen hier eingefügt werden.
  Wenn das erste Bucket leer wird, sucht man das nächste nicht-leere Bucket (i), setzt die Schranke des ersten Buckets auf i, des nächsten auf i+1, dann i+2, i+4, i+8 etc. (solange man noch nicht bei Bucket i+1 angekommen ist) und sortiert die Elemente aus Bucket i in die entsprechenden Positionen.
1. Beweis der amortisierten Kosten über drei mögliche Verfahren: Aggregat-Methode (englisch: aggregate method), Bankkonto-Methode (englisch: accounting method) und Potentialfunktion-Methode (englisch: potential method). Gerade das hiesige Beispiel für die dynamischen Arrays mit Verdoppelungsstrategie ist ein Standardbeispiel.
2. Die Oszillierungseffekte treten dann auf, wenn man die Arraygröße immer dann halbiert, wenn das Array nur noch zur Hälfte gefüllt ist: Beim nächsten Einfügen wird es wieder verdoppelt, wenn dann sofort wieder gelöscht wird, wird direkt wieder halbiert etc.
  Um das zu umgehen, muss man einen Wert wählen, der kleiner als 50% ist. Etwa für eine Minimalfüllung von 25% Prozent lässt sich zeigen, dass das Einfügen und Entfernen von Elementen in amortisiert k
3. Um für das Einfügen (und auch das Löschen) von Elementen mit dynamischen Vektoren auf worst-case konstante Zeit zu kommen, ist eigentlich recht einfach (auch wenn es nicht unbedingt einfach, darauf zu kommen). Eine der ersten Referenzen, die dies behandelt, ist in dem Technischen Report Resizable Arrays in Optimal Time and Space von Brodnik, Carlsson, Demaine, Munro und Sedgewick von 1999 zu finden.
  Um Einfügungen in worst-case konstanter Zeit zu ermöglichen, benötigt man zwei Vektoren: Den aktuellen Vektor und einen zweiten, der doppelt so groß ist. Wann immer ein Element in den aktuellen Vektor eingefügt wird, werden die beiden nächsten noch nicht übertragenen Elemente in den größeren Vektor geschrieben. Sobald der aktuelle Vektor voll ist und man das nächste Element einfügt, löscht man den aktuellen Vektor, nimmt den größeren als aktuellen und erzeugt einen neuen (zunächst leeren) Vektor wiederum doppelter Kapazität. Dann fügt man das neue Element in den nun aktuellen Vektor ein und überträgt direkt die ersten zwei Elemente in den neuen. Damit erfordert jedes Einfügen höchstens drei Operationen.
  Wenn man Löschen und Einfügen in worst-case konstanter Zeit erreichen möchte, benötigt man nicht nur einen Vektor doppelter Kapazität, sondern noch einen dritten, der nun die halbe Kapazität des aktuellen Vektors hat. Wann immer ein Element gelöscht wird, werden die nächsten beiden noch nicht übertragenen Elemente des aktuellen Vektors in den kleineren übertragen (wenn schon alle Elemente in den größeren Vektor übertragen sind, muss sicherlich auch das letzte Element daraus gelöscht werden); wann immer ein Element eingefügt wird, werden die nächsten beiden noch nicht übertragenen Elemente in den größeren Vektor übertragen. Wenn der aktuelle Vektor voll wird, verwirft man den kleineren, wählt den größeren als aktuellen und erstellt einen neuen doppelter Kapazität. Dann fügt man in den nun aktuellen Vektor das neue Element ein und überträgt die ersten beiden in den neuen größeren Vektor. Wenn der aktuelle Vektor nur noch zur Hälfte gefüllt ist, löscht man den größeren Vektor, wählt den kleineren als aktuellen und erzeugt einen neuen halber Kapazität. Dann entfernt man aus dem nun aktuellen Vektor das letzte Element und überträgt die ersten beiden Elemente in den kleineren. Damit erreicht man, dass ein Einfügen höchstens drei Operationen, ein Löschen höchstens vier Operationen bewirkt.
4. Hier muss ich mal schauen, was der Quellcode von Stefan hergibt - und ob ich den hier hochladen kann (evtl. war es aber auch nur Code für die nächste Aufgabe; noch habe ich den nicht gesichtet).
Für die gesamte Aufgabe kann man auf die Seite Bit Twiddling Hacks verweisen. Dort sind verschiedenste Methoden angegeben. Algorithmen für das Finden des signifikantesten gesetzten Bits sind unter der Überschrift Finding integer log base 2 of an integer oder Find integer log base 2 of a 32-bit IEEE float beschrieben, welche für das Finden des niedrigst-signifikanten gesetzten Bits unter der Überschrift Counting consecutive trailing zero bits.
Für den Aufgabenteil e. sei gesagt, dass im Übungsblatt leider ein Fehler war: Nicht in SSE4.2, sondern in SSE4a findet sich die Instruktion LZCNT (Leading Zero Count, die derzeit nur von AMD Prozessoren (mit Barcelona Architektur) verfügbar ist (siehe auch Wikipedia).
1. Da wir hier nur ständige Einfügungen haben, muss nur gezeigt werden, dass eine 2 niemals eine andere 2 einholen kann. Dazu gehen wir davon aus, dass wir, so es noch mindestens eine zwei gibt, wir diese entfernen (indem wir die entsprechenden Weak-Heaps in einen der doppelten Größe verschmelzen) und erst danach die nächste Operation (hier also nur Einfügungen) vornehmen.
  Am Anfang haben wir keinen Weak-Heap, also 000. Wir müssen also ncihts verschmelzen und können direkt einen neuen einfügen, was zum Schema 001 führt.
  Danach haben wir immer noch keine 2, können also das nächste Elemnt einfügen, wodurch wir 002 erhalten.
  Vor dem nächsten Einfügen müssen wir diese beiden nun mergen, was zu 010 führt (was nach wie vor regulär ist) und können dann das nächste Einfügen (011).
  Allgemeiner, sind die Fälle, in denen hinten eine 0 ist, völlig undramatisch (vorne eventuell zwei Weak-Heaps mergen, hinten von 0 auf 1 wechseln). Wenn ganz hinten eine 1 ist, ist es ebenfalls nicht schlimm: wenn vor der 1 eine 0 (eventuell gefolgt von einer Reihe von Einsen) ist, ist das kein Problem, die Darstellung bleibt auch nach dem Wechsel zur 2 ganz hinten regulär. Und wenn ganz hinten eine 2 ist, ist davor irgendwo eine 0 und dazwischen eventuell eine Reihe von Einsen. Die zwei Weak-Heaps hinten werden erst gemergt, so dass wir eine 0, eine 1 weniger, eine zwei und noch eine 0 erhalten, so dass dann das Einfügen wieder undramatisch wird und die Regularität nicht zerstört.
2. Binär in redundant: Trivial, da binär selbst schon dem Schema für redundante Zahlen folgt (es taucht einfach keine 2 auf).
  Redundant in binär: Einen Block 01^l2 kann man einfach in 10^l0 = 10^l+1 umwandeln.
3. Dieses Verfahren nutzt die Tatsache, dass perfekte Weak-Heaps genau 2^k Knoten enthalten. Wenn wir also die beiden Weak-Heaps an Position i mergen, kommen wir auf einen Weak-Heap mit 2ⁱ+2ⁱ=2ⁱ⁺¹ Knoten, der natürlich an Position i+1 stehen kann.
  Normale perfekte Heaps hingegen haben nur 2^k-1 Knoten. Wenn wir die beiden an Position i mergen, erhalten wir einen neuen, der dann 2ⁱ-1+2ⁱ-1=2ⁱ⁺¹-2 Knoten hat, was einer weniger ist als der Heap an Position i+1 bräuchte, so dass das Resultat kein perfekter Heap mehr ist und das Verfahren damit nicht unmittelbar funktioniert.
Hier jetzt alle Zwischenergebnisse abzutippen ist mir zu aufwändig, sorry. Aber das Ganze ist ja an und für sich recht einfach: Beim Insert wird ein neuer Baum bestehend aus einem Knoten erzeugt. Wenn es schon einen solchen gibt, werden die gemergt und es entsteht einer mit zwei Knoten. Wenn es auch einen solchen schon gibt, werden auch diese gemergt etc., bis es irgendwann höchstens einen Baum jeder Größe gibt.
Das Löschen des kleinsten Elementes ist auch sehr einfach: Das kleinste Element steht an der Wurzel eines Baumes. Aus diesem wird dann die Wurzel entfernt, so dass eine Reihe neuer Bäume unterschiedlicher Größen entsteht. Wenn es schon welche mit identischer Größe gibt, muss wieder gemergt werden.
Für das DecreaseKey nehmen wir das Element, verkleinern dessen Wert und vertauschen es so lange mit seinem Elternknoten, bis es entweder selbst Wurzel eines Baumes ist oder der Elternknoten kleiner ist.
Für ein allgemeines Delete kann man so vorgehen, dass man den Wert des zu entfernenden Elementes auf -∞ gesetzt, es wie mit einem DecreaseKey behandelt und anschließend über DeleteMin entfernt.

Blatt 3

1. Das lässt sich durch einfache Formelumwandlungen zeigen:
2. Hier ist die Idee einfach, dass im schlimmsten Fall alle Buckets innerhalb des Dreiecks (mit g- und h-Werten von 0 bis m) expandiert werden müssen, was m ⋅ (m-1) / 2, also O(m²), entspricht.
Hier das BDD, das bestimmt werden sollte, inklusive bereits eingetragener Sat-Counts:

Das Ranking und Unranking funktioniert so, wie im Beispiel in der Vorlesung gezeigt (tatsächlich ist der Zustand, der in Teilaufgabe c. angegeben ist, genau jener, der in d. gesucht wird, hat also Rank 3).
Ich habe mal versucht, die drei Algorithmen zu implementieren. Das Resultat ist hier: A3_3.cc. Zum Starten müssen der gesuchte String (als erster Parameter) und die zu durchsuchende Datei (als zweiter Parameter) angegeben werden. Es werden nacheinander alle drei Algorithmen angestoszlig;en und die Indizes der Fundstellen ausgegeben.

Der Trie (ohne Fehlerfunktion) sieht folgendermaszlig;en aus:

Mitsamt Fehlerfunktion sieht das Ganze leider nicht mehr ganz so übersichtlich aus:

Die Übergangstabelle für den Automaten (jeweils Übergang von Knoten u über Kante mit Beschriftung δ nach Knoten v):

u	δ	v
0	0	0
0	1	1
1	0	8
1	1	2
2	0	3
2	1	2
3	0	4
3	1	9

u	δ	v
4	0	0
4	1	5
5	0	8
5	1	6
6	0	7
6	1	2
7	0	4
7	1	9

u	δ	v
8	0	0
8	1	9
9	0	14
9	1	10
10	0	11
10	1	2
11	0	12
11	1	1

u	δ	v
12	0	0
12	1	13
13	0	8
13	1	6
14	0	0
14	1	15
15	0	14
15	1	10

Das ergibt dann folgenden Automaten:
Hier sollte der Automat stehen...

Hier muss der Algorithmus zur Zeichenkettensuche mit Wild Cards verwendet werden (müssten Folien 43 bis 45 sein). Dabei ist das Muster M=1?0?0 und der zu durchsuchende Text T=10010010010110110010100110100011000. Der Zähl-Vektor C wird auf die selbe Länge wie T gesetzt und durchgehend mit Nullen initialisiert.
Die Multimenge aller Maximalen Teilstrings von M ist P={1, 0, 1}; die zugehörigen Startpositionen l₁=1, l₂=3 und l₃=5.
Da wir hier ausschlieszlig;lich Teilstrings der Länge 1 haben, können wir uns die Trie- und Automaten-Konstruktion sparen. Die Startpositionen der Teilstrings sind dann einfach die Positionen, an denen das entsprechende Zeichen steht. Für P[1] ergeben sich die Positionen {1, 4, 7, 10, 12, 13, 15, 16, 19, 21, 24, 25, 27, 31, 32}, für P[2] und P[3] die Positionen {2, 3, 5, 6, 8, 9, 11, 14, 17, 18, 20, 22, 23, 26, 28, 29, 30, 33, 34, 35}. Jetzt müssen wir nur noch diese 3 Arrays durchlaufen und im Zähl-Vektor C den Zähler an Position j-l_i+1 (j = Position in Array P[i]; i = gerade durchsuchtes Array von P) um 1 erhöhen. Das ergibt dann den Vektor C=31131130120221230221210322211132100. Überall dort, wo eine 3 steht, beginnt ein String, der dem Muster entspricht, hier sind das also die Positionen 1, 4, 7, 16, 24 und 31.

Blatt 4

1. Der Suffix-Trie sieht so aus:
  
  Der zugehörige Suffixbaum sieht etwa so aus (leider wurden nicht alle Knoten in dem Layer gezeichnet, in dem sie eigentlich auftauchen):
2. Um die längste Teilzeichenkette zu finden, die mindestens zweimal auftaucht, müssen wir den kompletten Baum durchsuchen (DFS, BFS o.ä.). Der tiefste Knoten, an dem verzweigt wird (also ein innerer Knoten) ist entscheidend. Der tiefste Knoten ist dabei derjenige, bei dem das bis dorthin stehende Wort maximale Länge unter allen inneren Knoten hat. Das bis dorthin stehende Wort entspricht dann der längsten mindestens doppelt vorhandenen Teilzeichenkette (hier: abaa). Laufzeit: O(n) (Suche durch den vollständigen Baum, der eine Größe von O(n) hat).
3. Entscheidend ist hier, dass die ausgehenden Kanten an jedem Knoten lexikographisch sortiert sind. Man verwendet dann einfach Tiefensuche: Zunächst folgt man dem kleineren der beiden Strings. Von dort aus läuft man weiter, als würde man normale Tiefensuche durchführen, bis man zum zweiten String kommt. Alle zwischendurch erreichten Strings liegen lexikographisch zwischen diesen beiden.
1. Für alle m_i (1 ≤ i ≤ k): Folge dem Pfad von der Wurzel bis zum letzten Buchstaben (≠ $) von m_i. Wenn hier ein innerer Knoten ist (also Verzweigungsgrad ≥ 2), dann ist m_i ein Substring von einem anderen (an dieser Stelle unbekannten) m'.
  Die Laufzeit sollte O(D) sein, wobei D die Sumem der Längen der einzelnen Strings ist.
  Alternativ kann man auch an jedem (inneren) Knoten eine Liste vorhalten, die speichert, von welchen Strings Suffixe über diesen Knoten führen (sollte direkt bei der Konstruktion machbar sein). Damit lässt sich dann auch exakt bestimmen, von welchen anderen Strings m_i ein Substring ist.
2. Zunächst der Beweis, dass die Doppelsumme tatsächlich zu O(kD) wird:
  Es gibt (natürlich) mehrere Möglichkeiten, dies zu zeigen, etwa über Induktion, genaues Hinsehen oder einfache Umwandlungen. Hier das letztere:
  
  Das eigentliche Verfahren läuft so ab: Wir erzeugen uns den generalisierten Suffixbaum für alle Paare. Darin merken wir uns in den einneren Knoten, von welchen der beiden Strings Suffixe durch diesen Knoten gehen. Der Pfad von der Wurzel bis zum tiefsten Knoten, in dem Suffixe aus beiden Strings enthalten sind, gibt die längste gemeinsame Zeichenkette an.
  Die Laufzeit ist durch die Zeit für die Tiefensuchen gegeben. Der generalisierte Suffixbaum für die Paare i und j hat O(|m_i| + |m_j|) Knoten. Für die Gesamtlaufzeit müssen wir dies für alle Paare aufsummieren, was zu obiger (Doppel-)Summe führt.
3. Zunächst erzeugen wir den generalisierten Suffixbaum für alle Zeichenketten. Anschließend durchlaufen wir diesen Baum für jede vollständige Zeichenkette ein weiteres Mal und fügen den entsprechenden Index dieser Zeichenkette als Zusatzinformation in eine Liste an den besuchten Knoten ein. Währenddessen prüfen wir, ob die Liste des nächsten Knotens genauso groß ist wie die des aktuellen Knotens. Ist das der Fall, gehen wir einfach weiter; anderenfalls haben wir eine Verzweigung gefunden, an der sich mehrere Strings aufspalten, also sich ihre Präfixe unterscheiden. Damit müssen wir für den aktuellen String bloß noch die Indizes in den Nachbarpfaden ausgeben und dazu diesen Knoten zurückliefern (wenn wir Elternzeiger verwalten lässt sich aus dem Knoten einfach der Präfix wieder generieren).
  Zur Laufzeit: Die Konstruktion benötigt Zeit O(nk) (und der generalisierte Suffixbaum hat O(nk) Knoten). Für das ablaufen der vollständigen Zeichenketten besuchen wir höchstens O(nk) Knoten. Der Faktor p ist ein reiner Ausgabeparameter; für jeden gemeinsamen Präfix eines Paars geben wir den Knoten zurück, der den Präfix beschreibt. Insgesamt kommen wir also auf O(nk + p).
  Prinzipiell sollte das auch funktionieren, wenn wir nicht auf einen generalisierten Suffixbaum setzen, sondern einen entsprechend kompaktierten Stringbaum; wir interessieren uns nur für gemeinsame Präfixe, so dass es unnötig ist, die restlichen Suffixe (neben den vollständigen Strings) mit zu speichern. An der Laufzeit sollte das jedoch keine größere Änderung bedeuten.
Ich habe mal wieder etwas implementiert. Nämlich findet sich in A4_3.cc ein C++ Programm, das, je nach übergebenem Parameter, entweder naives Union und Find, LRPC, REM oder SP-REM ausführt. Wie üblich, gilt: Die Implementierungen sind nicht sonderlich auf Effizienz getrimmt; vielmehr habe ich einfach versucht, die Beschreibungen aus den Folien in Code umzusetzen. Es läuft, aber wie gut es wirklich ist, ist eine andere Frage.