1
2 3 4 5
1 2 3 4 5 6
Aufgabe2 InsertionSort(4Punkte)
Gegeben seien folgende zwei Implementierungen von InsertionSort. Hierbei wird die Funktion buildHeap verwendet, die einen effizienten Algorithmus implementiert, um ein Array in die in der Vorlesung besprochene Struktur eines binären Min-Heaps zu bringen.
Funktion void InsertionSort1(int[] a, int n): InsertionSort
forinti=1ton-1do int j = i;
while j > 0 · a[j-1] > a[j] do swap(a[j], a[j-1]);
j = j – 1;
Funktion void InsertionSort2(int[] a, int n): InsertionSort auf Binärem Min-Heap
buildHeap(a, n); forinti=1ton-1do
int j = i;
while a[j-1] > a[j] do
swap(a[j], a[j-1]); j = j – 1;
a)* Warum kann in InsertionSort2 auf die Bedingung j > 0 in der inneren Schleife verzichtet werden, ohne dass j über die Array-Grenzen hinweg zu laufen droht? Begründen Sie Ihre Antwort.
0 1 2
0 1 2
b)* Sie messen die tatsächliche Laufzeit beider Implementierungen für zufällige Eingabe-Arrays. Dabei stellen Sie fest, dass InsertionSort2 trotz des zusätzlichen Aufwands, der durch buildHeap entsteht, schneller ist. Warum ist dies der Fall? Begründen Sie Ihre Antwort.
IN-GAD-8-20200803-E5378-04 – Seite 4 / 16 – Seite leer
1
2
3 4
1 2 3 4 5 6 7 8
9 10 11 12
13
Aufgabe4 HashTable(16Punkte)
Gegeben sei die Klasse HashTable, die Elemente vom Typ Integer speichert.
• Dazu speichert sie ein Array table der Länge p von Records.
• Ein Record enthält das zu speichernde Attribut element des Typs Integer sowie einen Integer probePosition.
• Die Anzahl der aktuell in der Hashtabelle gespeicherten Elemente ist im Attribut numElements des Typs Integer gespeichert.
• Nehmen Sie an, dass jede Zuweisungsoperation die Daten kopiert. Außerdem seien die folgenden Funktionen gegeben:
Funktion int getLocation(Record r): gibt den Index zurück, an dem das Record eingefügt werden soll if r.probePosition mod 2 == 0 then
return (r.element + (Â r.probePosition / 2 Ê)) mod p; else
return (p + r.element ≠ (Â r.probePosition / 2 Ê + 1)) mod p;
Funktion void insert(int e): fügt den übergebenen Wert in die Hashtabelle ein
if table.size() == numElements then Abbruch des Programms mit Fehlermeldung ; Record record = new Record(element = e; probePosition = 0);
while true do
int location = getLocation(record); if table[location] == null then
table[location] = record; numElements++; return;
if table[location].probePosition < record.probePosition then Record tmp = table[location];
table[location] = record;
record = tmp;
record.probePosition = record.probePosition + 1;
a)* Fügen Sie die im Folgenden angegebenen Werte der Reihe nach in die Hashtabelle der Größe p = 11 ein und verwenden Sie in jedem Schritt genau die untenstehende vorgegebene Tabelle.
• Gehen Sie dabei genau so vor, wie oben in der Funktion insert skizziert.
• Die Schlüssel sollen dabei die Werte selbst sein.
• Geben Sie für jedes eingefügte Record auch dessen optimalen Index sowie die probePosition an. • Der optimale Index für ein einzufügendes Element e berechnet sich durch e mod p.
• Tragen Sie in jedem Schritt auch die in den vorherigen Schritten eingefügten Elemente ein.
• Folgende Zahlen sollen eingefügt werden: 1,44,65,33,10,78
Hinweis: Falls Sie die Aufgabe am Rechner bearbeiten, können Sie die in den Tabellen vorhandenen Textfelder verwenden.
1. Operation: insert(1) mit optimalem Index:
Index0 1 2 3 4 5 6 7 8 9 10
element probePosition
2. Operation: insert(44) mit optimalem Index:
Index0 1 2 3 4 5 6 7 8 9 10
element probePosition
0 1 2 3 4 5 6 7 8
IN-GAD-8-20200803-E5378-06 – Seite 6 / 16 – Seite leer
3. Operation: insert(65) mit optimalem Index:
Index0 1 2 3 4 5 6 7 8 9 10
element probePosition
4. Operation: insert(33) mit optimalem Index:
Index0 1 2 3 4 5 6 7 8 9 10
element probePosition
5. Operation: insert(10) mit optimalem Index:
Index0 1 2 3 4 5 6 7 8 9 10
element probePosition
6. Operation: insert(78) mit optimalem Index:
Index0 1 2 3 4 5 6 7 8 9 10
element probePosition
b)* Vergleichen Sie das hier gezeigte Hash-Verfahren mit Linearem Sondieren. Nennen und erklären Sie einen Vorteil des hier gezeigten Verfahrens.
0 1 2
Seite leer – Seite 7 / 16 – IN-GAD-8-20200803-E5378-07
0 1 2 3 4 5 6
c)* Implementieren Sie in Pseudocode (in etwa so detailliert wie der oben skizzierte insert-Algorithmus, dies sollte nicht mehr als 9 Zeilen Code benötigen) die Funktion boolean find(int e), die den gesuchten Wert in der Hashtabelle effizient suchen soll. Falls der Wert gefunden wird, so soll true zurückgegeben werden. Andernfalls wird false zurückgegeben. Sie dürfen außerdem annehmen, dass in die Tabelle nur neue und duplikatfreie Werte hinzugefügt, aber keine eingefügten Elemente entfernt werden.
IN-GAD-8-20200803-E5378-08 – Seite 8 / 16 – Seite leer
Aufgabe5 AlgorithmischeProblemstellungen(5Punkte)
Für jedes der folgenden Probleme dürfen Sie alle in der Vorlesung behandelten Algorithmen und Datenstrukturen verwenden. Wenn Sie beispielsweise einen (2,4)-Baum verwenden wollen, schreiben Sie ABBaum<2,4>. Wichtig ist hier, dass Sie eindeutig spezifizieren, welche Datenstruktur Sie verwenden möchten und falls nötig, auch die Parameter mit anzugeben. Sie dürfen bekannte Datenstrukturen auch abändern, beispielsweise können Sie in den meisten Datenstrukturen statt Schlüssel-Wert Tupel auch ausschließlich die Schlüssel speichern und umgekehrt. Erklären Sie für jede Teilaufgabe in natürlicher Sprache, wie Sie das Problem lösen können und welche Datenstrukturen Sie in welchem Schritt einsetzen. Formulieren Sie Ihre Lösungen präzise und eindeutig.
a)* Gegeben sei ein mit Zahlen befülltes Array der Länge n. Geben Sie einen Algorithmus an, der die Häufigkeit aller Elemente im Array zählt. Ihre Lösung darf die asymptotische Laufzeit von O(n) nicht überschreiten. Begründen Sie, warum Ihr Algorithmus diese Bedingung erfüllt.
0 1 2
b)* Gegeben sei eine Sequenz numbers bestehend aus einer unbekannten Anzahl von aufsteigend sortierten natürlichen Zahlen. Erklären Sie, wie Sie eine Funktion search(int e) implementieren können, die überprüft, ob das übergebene Element in der Sequenz existiert, sodass die asymptotische Laufzeit von O(log |numbers|) nicht überschritten wird. Begründen Sie Ihre Antwort.
0 1 2
Sie können auf jeden Index i innerhalb der Sequenz numbers mit numbers[i] in O(1) zugreifen. Wenn Sie auf einen
Index zugreifen, der außerhalb der Sequenz liegt, so wird Œ zurückgegeben. 3
Seite leer – Seite 9 / 16 – IN-GAD-8-20200803-E5378-09
0 1
0
1 2 3 4 5
0 1 2 3
0 1 2
Aufgabe7 Sortieren(11Punkte)
Gegeben sei der folgende Algorithmus f mit der Vorbedingung i Æ j:
Funktion int f(int[] a, int i, int j): Algorithmus f
1 intres=0;
2 forintk=itojdores=res+a[k];
3 if a[i] > a[j] then swap(a[i], a[j]);
4 if i == j then return a[i];
5 if i+1 Ø j then return a[i]+a[j];
6 int k=(j-i+1)/3;
7 f(a, i, j-k);
8 f(a, i+k, j);
9 f(a, i, j-k);
10 return res;
a)* Was gibt dieser Algorithmus f als Ergebnis zurück?
b)* Zeigen Sie mittels Induktion, dass dieser Algorithmus f als Nebeneffekt das Array a im Bereich a[i] bis a[j]
sortiert.
c)* Berechnen Sie die Komplexität des Algorithmus f in Bezug auf Laufzeit und Speicherbedarf.
d) Vergleichen Sie Algorithmus f mit dem in der Vorlesung behandelten MergeSort Algorithmus bezüglich Laufzeit und Speicherbedarf.
IN-GAD-8-20200803-E5378-12 – Seite 12 / 16 – Seite leer