1. (a) Was ist ein Divide-and-Conquer-Algorithmus? Erklären Sie den allgemeinen Ansatz von Divide-and-Conquer-Algorithmen. (6 Punkte)

(b) Verwenden Sie den Divide-and-Conquer-Ansatz, um einen Algorithmus zu entwerfen, der das minimale Element in einem Array von n Elementen findet. Analysieren Sie die zeitliche Komplexität Ihres Algorithmus. (10 Punkte)

2. (a) Erklären Sie das Konzept von Hashing- und Kollisionsauflösungstechniken. (6 Punkte)

(b) Betrachten Sie eine Hash-Tabelle der Größe m und eine Menge von n Elementen, die gehasht werden sollen. Gehen Sie davon aus, dass die Elemente gleichmäßig auf die m Slots verteilt sind. Wie hoch ist die Wahrscheinlichkeit einer Kollision, wenn n =m/2? Analysieren Sie die durchschnittliche Anzahl der Vergleiche, die erforderlich sind, um mithilfe linearer Prüfungen alle Elemente erfolgreich in die Hash-Tabelle einzufügen. (10 Punkte)

3. (a) Beschreiben Sie das Konzept der dynamischen Programmierung und erklären Sie, wie es sich vom Divide-and-Conquer-Ansatz unterscheidet. (6 Punkte)

(b) Verwenden Sie dynamische Programmierung, um das Stabschneideproblem zu lösen, bei dem ein Stab der Länge n in kleinere Stäbe geschnitten werden kann und jeder Stab der Länge i einen Preis p[i] hat. Ziel ist es, den größtmöglichen Gewinn zu erzielen, der durch das Zerteilen der Rute in kleinere Stücke erzielt werden kann. Analysieren Sie die zeitliche und räumliche Komplexität Ihres Algorithmus. (10 Punkte)

4. (a) Erklären Sie das Konzept der NP-Vollständigkeit und seine Bedeutung bei der Analyse von Algorithmen. (6 Punkte)

(b) Beweisen Sie, dass das folgende Problem NP-vollständig ist:Bestimmen Sie bei einer gegebenen Menge von n Elementen mit ihren jeweiligen Gewichten und Werten, ob es eine Teilmenge dieser Elemente gibt, deren Gesamtgewicht kleiner oder gleich einem gegebenen Grenzwert ist und deren Gesamtgewicht kleiner oder gleich einem gegebenen Grenzwert ist Wert wird maximiert. (10 Punkte)

5. (a) Erklären Sie das Konzept einer amortisierten Analyse von Algorithmen. Warum wird es verwendet und welche Vorteile bietet es? (6 Punkte)

(b) Führen Sie eine amortisierte Analyse der Stapeldatenstruktur durch, wobei Push- und Pop-Operationen die einzigen zulässigen Operationen sind. Bestimmen Sie die durchschnittliche zeitliche Komplexität jeder Operation. (10 Punkte)

6. (a) Beschreiben Sie den Kruskal-Algorithmus zum Finden des minimalen Spannbaums eines gewichteten ungerichteten Graphen. (6 Punkte)

(b) Wenden Sie Kruskals Algorithmus auf den folgenden Graphen an und finden Sie den minimalen Spannbaum:

„

(1)---2---(3)

/ |

/ |

5 / 4

-----------

(4)---6---(5)

„

Berechnen Sie das Gesamtgewicht des minimalen Spannbaums. (10 Punkte)

7. (a) Erklären Sie das Konzept einer topologischen Sorte eines gerichteten azyklischen Graphen (DAG). (6 Punkte)

(b) Führen Sie eine topologische Sortierung für die folgende DAG durch:

„

(1) -> (2) -> (3)

\ /

-> (4)

„

Geben Sie die Reihenfolge der Eckpunkte in der topologischen Sortierung an. (10 Punkte)

8. (a) Beschreiben Sie das Konzept der binären Suchbäume (BSTs). Erklären Sie, wie BSTs für effiziente Such- und Einfügevorgänge verwendet werden. (6 Punkte)

(b) Fügen Sie die folgenden Elemente in eine zunächst leere BST ein:20, 10, 30, 5, 15, 25, 35. Zeichnen Sie die resultierende BST und analysieren Sie die zeitliche Komplexität der Suche nach einem Element in dieser BST. (10 Punkte)

Denken Sie daran, ein klares Verständnis der Konzepte nachzuweisen, korrekte Erklärungen bereitzustellen und bei Bedarf die zeitliche und räumliche Komplexität von Algorithmen zu analysieren.