Algorithmik

Es gibt einen Algorithmische mit Worst-Case-Laufzeit in \(\mathcal{o}(n^3)\) zur Berechnung des Produkts zweier Boolescher  \(n\times n\)  Matrizen

Es ist kein Algorithmus zur Multiplikation zweier n-Bit Zahlen bekannt, der Laufzeit \(\mathcal{o}(n^2)\) hat.

Sei \(k \in \mathbb{N}\) fest. Jeder Algorithmus der in einem Feld mit n Elementen das k-kleinste Element bestimmt, benötigt im Worst-Case \(\Omega(n \ log(n))\) Vergleiche.

Die mittlere Laufzeit von Bubblesort liegt in \(\Theta(n^2)\).

Quickselect benötigt im Worst-Case nicht mehr als 4n Vergleiche um den Median eines Feldes von n Elementen zu finden.

Quicksort mit Median-aus-3 benötigt im Mittel nicht mehr als 3n Vergleiche um ein Feld von n Elementen zu sortieren.

Mergesort benötigt im Worst-Case \(\Theta(n^2)\) Vergleiche um ein Feld von n Elementen zu sortieren.

Durch Verwendung von Fibonacci-Heaps hat Prims Algorithmus eine Laufzeit von \(\mathcal{O}(m + n \ log(n))\) um den minimalen Spannbaum eines Graphen mit m Kanten und n Knoten zu berechnen.

Jede Insert Operation in ein Fibonacci Heap kann im Worst-Case in \(\mathcal{O}(1)\) Schritten durchgeführt werden.

Sei L eine kontext-freie Sprache. Das Wortproblem (gegeben ein Wort w, entscheide ob w in L) für L kann mit Hilfe des CYK-Algorithmus in kubischer Zeit entschieden werden.

Die Ausgabe des Algorithmus von Karger und Stein ist immer ein korrekter minimaler Schnitt

Der Algorithmus von Stoer und Wagner hat eine Laufzeit von \(\mathcal{O}(n\ log(n))\) auf einem Graphen mit n Knoten.

Bei Union-Find mit Pfadverkürzung auf einer n-elementigen Menge ist die Höhe der einstehenden Bäume durch die inverse Ackermannfunktion \(\alpha(n)\) beschränkt.

Es gilt \(3^n \in \mathcal{O}(2^n)\)

Es gilt \(n \log(n) \in \mathcal{O}(\sqrt{n^3})\).

Die in der Vorlesung behandelte Algorithmus von Stoer und Wagner berechnet einen minimalen Schnitt eines Graphen.

Es ist kein subkubischer Algorithmus zur Berechnung optimaler Suchbäume bekannt.

Sei \(M \subseteq \mathbb{Z}\) mit \(3 \le |M| < \infty\). Der Median von M kann gleich dem Minimum von M sein.

Quickselect benötigt im Durchschnitt nicht mehr als 4n Vergleiche auf einem Feld mit n Elementen.

Prims Algorithmus zur Berechnung eines minimalen Spannbaumes folgt dem Entwurfsprinzip "Union Find".

Ein Fibonacci-Heap mit n Knoten kann eine Höhe von n erreichen.

Verwendet man Fibonacci-Heaps zur Implementierung von Dijkstras Algorithmus zur Berechnung kürzester Wege, so ist die Laufzeit in \(\mathcal{O}(|E|+ |V|\log|V|)\) für einen Graphen \(G=(V,E,\gamma)\).

Seien S,TU feste Mengen mit \(S \subseteq U\) und \(|T|=|S|^2\). Sei \(\mathcal{H}\) eine universelle Familie von Hashfunktionen von U nach T. Dann ist mehr als die Hälfte der Hashfunktionen aus \(\mathcal{H}\) injektiv auf S.

Sei T ein beliebiger Baum mit einem ausgezeichneten Wurzelknoten. Sei B die Menge der Blätter von T und für \(i\in B\) sei t, die Tiefe von Blatt i. Dann ist \(\sum_{i\in B} 2^{-t_i}\le1\).

Es existiert ein Linearzeit-Algorithmus, der auf Eingabe eines Feldes mit n Elementen und einer Zahl \(k\in\{1,..,n\}\) die k kleinsten Elemente des Feldes ausgibt.

Es existiert ein vergleichsbasierter Sortieralgorithmus mit einer sublinearen Best-Case-Laufzeit und einer quadratischen Worst-Case Laufzeit.

Die mittleren Laufzeiten von HeapSort und Quicksort liegen in \(\Theta(n \log(n))\).

Die Laufzeit des Dijkstra-Algorithmus liegt bei Verwendung eines Min-Heaps in \(\mathcal{O}(n^2 \log(n))\), wobei n  die Anzahl der Knoten ist.

Der Warshall-Algorithmus berechnet die transitive Hülle eines Graphen

Es ist kein subkubischer Algorithmus zur Multiplikation von booleschen Matrizen bekannt.

Für alle \(n \in \mathbb{N}\) existiert eine Sequenz von Union-Find-Operationen (auf einer Union-Find-Datenstruktur mit Pfadverkürzung), die einen Baum der Höhe n mit n+1 Knoten erzeugt.

Durch Iteration des Algorithmus von Karger und Stein können alle minimalen Schnitte eines Graphen bestimmt werden; die Worst-Case-Laufzeit  dieser Iteration liegt in \(\mathcal{O}(n^2 \log^3 (n))\).

Wie viele Vergleiche benötigt ein Sortieralgorithmus, der ausschließlich auf Schlüsselvergleiche basiert? (im Mittel und im schlechtesten Fall)

Welche Größe müssen Hashtabellen haben, damit nicht mit Kollisionen zu rechnen sind?

Welche Laufzeitkomplexität hat der Huffman-Code unter Verwendung von Heap?

Wie teuer ist das Einsinken beim Heapaufbau?

Mit wie vielen Vergleichen ist der Heapaufbau möglich?

Wie viele Vergleiche benötigt der Standard-Heapsort?

Wie groß ist der Aufwand bei Dijkstra unter Verwendung eines Fibonacci-Heaps

Wie ist der Aufwand beim Bellman-Ford-Algorithmus? Was berechnet dieser?