\( \newcommand{\dist}{\textnormal{dist}} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\pfrac}[2]{\left(\frac{#1}{#2}\right)} \newcommand{\inneighbors}{\textnormal{inNeighbors}} \newcommand{\outneighbors}{\textnormal{outNeighbors}} \newcommand{\neighbors}{\textnormal{neighbors}} \newcommand{\indeg}{\textnormal{indeg}} \newcommand{\outdeg}{\textnormal{outdeg}} \newcommand{\scc}{\textnormal{scc}} \newcommand{\label}{\textnormal{label}} \newcommand{\union}{\textnormal{union}} \)

8. Testataufgaben

Abgabetermin: Donnerstag, 1. Februar 2024

Aufgaben: die Testataufgaben auf dieser Seite

Abgabeformat: Text, also vorzugsweise Latex.

Arithmetische Operationen

Im Kapitel 5 haben wir Algorithmen für arithmetische Operationen kennengelernt. Essenziell war dabei die Erkenntnis, dass für große natürliche Zahlen der Datentyp int nicht mehr ausreicht; wir müssen sie als Array von byte (oder int) darstellen. Somit können Operationen wie x*y auch nicht mehr in einem Prozessortakt ausgeführt werden. Man nennt eine solche Darstellung einen BigInteger-Datentyp. In Python werden große Zahlen intern bereits als BigInteger dargestellt, ohne das wir als Programmierer uns darum kümmern müssen.

Testataufgabe Wie würden Sie die Exponentialfunktion exp(a,b), die \(a^b\) für natürliche Zahlen berechnen, implementieren, z.B. in Python, wenn es die nicht bereits gäbe als a**b?

Schätzen Sie die Laufzeit Ihrer Implementierung mit der \(O\)-Notation ab!

Messen Sie empirisch die Laufzeit in Python: implementieren Sie 

# die Datei exp.py
from timeMyPrograms import *
def exp(a,b):                            
  return a*b

und messen dann die Laufzeit mit dem Modul timeMyPrograms.py: 

python3 -i exp.py                            
measure_alg(exp, 2 1000)

Legen Sie eine kleine Tabelle an (Exponent 1000 wird wohl zu klein sein, um aussagekräftig zu sein) und versuchen Sie, zu erraten, um welche Laufzeitkomplexität es sich hier handelt.

Eine alternative Union-Find-Datenstruktur

Im Kapitel über billigste Spannbäume haben wir Union-Find-Datenstrukturen kennengelernt. Zur Erinnerung: meine Folien zu Union-Find with Path Compression. Wir hatten in der Vorlesung auch eine alternative Datenstruktur diskutiert: jedes Element hat ein Label, das beschreibt, zu welcher Klasse es gehört. Wenn die Elemente die Zahlen \(0, \dots, n-1\) sind, können wir \(\label(x)\) einfach als Array implementieren.

  • Am Anfang setzen wir \(\label(x) := x\), jedes Element ist also in seiner eigenen Klasse.
  • Wir können feststellen, ob \(x\) und \(y\) in der gleichen Klasse sind, indem wir prüfen, ob \(\label(x) = \label(y)\) gilt.
  • Um \(\union(x,y)\) durchzuführen, setzen wir \(i := \label(x)\) und \(j := \label(y)\). Daraufhin gehen wir alle Elemente \(x'\) der Klasse \(i\) durch und setzen das Label auf \(j\), also: \(\label(x') := j\). Hierfür brauchen wir pro Klasse noch eine verkettete Liste, die uns einfaches Durchlaufen und Hinzufügen ermöglicht.

Testataufgabe Beschreiben Sie ein Szenario, in welchem die obige Datenstruktur Union-Find by Label schlechtes Laufzeitverhalten zeigt. Insbesondere eine Folge von \(n\) Union-Operationen, die eine Laufzeit von \(\Omega(n^2)\) zur Folge hat.

Ändern Sie nun die Implementierung der Union-Operation:

  • Für \(\union(x,y)\) setzen wir \(i := \label(x)\) und \(j := \label(y)\). Daraufhin benennen wir alle Elemente der kleineren Klasse um.

Testataufgabe Zeigen Sie, dass die Laufzeit bei \(n\) Elementen und \(m\) Union-Operationen bei dieser Datenstruktur höchstens \(O(n \log n + m)\) ist.

Billigste Wege in DAGs

Erinnern Sie sich: ein DAG, also directed acyclic graph, ist ein gerichteter Graph ohne Kreise. In der Vorlesung haben wir gesehen, wie das Problem der Edit Distance formuliert werden kann als die Suche nach einem billigsten Pfad in einem DAG. Der erste Algorithmus für Edit Distance hatte Komplexität \(O(n^2)\), wobei \(n\) die länge der beiden Wörter ist; \(n^2\) war allerdings auch die Anzahl der Knoten in dem daraus entstehenden DAG, so dass die Laufzeit doch wieder linear in der Anzahl der Knoten war.

Nun betrachten wir allgemeine DAGs \(G = (V,E)\) mit \(n\) Knoten und \(m\) Kanten und einer Kostenfunktion \(c : E \rightarrow \R\). Beachten Sie: die Kosten können sehr wohl negativ sein.

Testataufgabe Beschreiben Sie einen Algorithmus zum Finden billigster \(s-t\)-Pfade in DAGs mit Komplexität \(O(n+m)\).

Testataufgabe Wir betrachten ungewichtete DAGs, also \(G = (V,E)\) ohne Kantenkostenfunktion. Beschreiben Sie einen Algorithmus mit Laufzeit \(O(n+m)\), der einen längsten Pfad in \(G\) findet. Das Wort längsten bezieht sich hier ausschließlich auf die Anzahl der Kanten, da wir ja keine Kantenkosten haben.

Warum scheitert Ihr Algorithmus an allgemeinen (d.h. nicht azyklischen) Graphen?

Testataufgabe In der Vorlesung haben wir einen Algorithmus gesehen, der die Edit-Distanz zweier Wörter von Länge \(n\) in Zeit \(O(nk)\) berechent (also im Gegensatz zu \(O(n^2))\), wenn wir im Voraus bereits wissen, dass die Edit-Distanz höchstens \(k\) ist.

Verallgemeinern Sie diesen Algorithmus für für das Szenario, dass wir den wahren Wert \(k\) der Edit-Distanz nicht a priori kennen. Der Algorithmus soll trotzdem "schnell" sein, wenn \(k\) klein ist.