\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{amstext}
\usepackage{ngerman}
\usepackage{fullpage}
\usepackage{graphicx}

\newcommand{\ZETTELNUMMER}{12}
\newcommand{\ABGABEDATUM}{am 23. Januar 2014 vor der Vorlesung in 
                          die jeweiligen Tutorenf\"acher}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe \arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}



\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}

\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung

\smallskip
\noindent
\large
\textbf{Algorithmen und Programmierung III} \\[0.5ex]
\normalsize
Wolfgang Mulzer \hfill WiSe 2013/14

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm

\begin{description}

\AUFGABE{Implementierung von Tries}{10 Punkte}

\begin{enumerate}
\item Beschreiben Sie kurz, wie man konkret die
  Operationen \texttt{put}$(s,v)$, \texttt{get}$(s)$,
  \texttt{remove}$(s)$ und \texttt{succ}$(s)$ auf
  unkomprimierten Tries implementieren kann.
  Dabei ist $s$ jeweils eine nichtleere Zeichenkette
  und $v$ ein Wert aus einer endlichen Wertemenge $V$.
  Geben Sie die Laufzeiten an.
\item
  Implementieren Sie unkomprimierte Tries mit den Operationen
  aus (a) in Java.
\end{enumerate}

\AUFGABE{Collections in Java}{10 Punkte}

\begin{enumerate}
\item In der Vorlesung haben Sie verschiedene abstrakte
  Datentypen kennengelernt, mit denen sich Mengen von Objekten
  bzw.~von Paaren von Objekten speichern lassen.
  Nennen Sie vier solche ADTs, und nennen Sie
  jeweils zwei substantiell unterschiedliche Implementierungen.

\item Informieren Sie sich \"uber das \emph{Java Collections Framework}.
  Wie ist dieses grob strukturiert? Wo und wie finden sich die ADTs 
  aus (a) wieder?
  Welche Implementierungen bietet das Framework f\"ur die ADTs?
\end{enumerate}

\emph{Anmerkung:} Falls es Ihnen lieber ist und falls Ihr Tutor nichts
dagegen hat, k\"onnen Sie (b) nat\"urlich auch f\"ur eine
andere Programmiersprache oder Laufzeitbibliothek Ihrer Wahl bearbeiten, wie 
zum Beispiel die STL von C++, das .Net Framework oder die Python standard
library.

\AUFGABE{Tiefensuche}{10 Punkte}

\begin{enumerate}

\item
Benutzen Sie Tiefensuche, um in  
einem zusammenh\"angenden, ungerichteten Graphen einen Weg zu 
finden, der jede
Kante genau einmal in jeder Richtung durchl\"auft.

\item
Sei $G = (V,E)$ ein kreisfreier gerichteter Graph.
Ein solcher Graph hei\ss{}t DAG (f\"ur 
\textbf{d}irected \textbf{a}cyclic \textbf{g}raph).
Eine \emph{topologische Sortierung} von $G$ ist eine Anordnung der
Knoten von $G$, so dass keine Kante in $G$ von einem sp\"ateren 
zu einem fr\"uheren Knoten verl\"auft.
Betrachten Sie den folgenden Algorithmus:

\newpage
\begin{verbatim}

dfs(v, topoOrder)
  v.found <- true
  for e in v.outgingEdges() do
    w <- e.opposite(v)
    if !w.found then
      dfs(w, topoOrder)
  topoOrder.push(v)

topoSort(G)
  topoOrder <- new Stack
  for v in G.vertices() do
    v.found <- false
  for v in G.vertices() do
    if !v.found do
      dfs(v, topoOrder)
\end{verbatim}


F\"uhren Sie den Algorithmus auf dem folgenden Graphen
aus. Gehen Sie dabei davon aus, dass die Knoten in \texttt{vertices}
und \texttt{outgoingEdges} gem\"a\ss{} der Knotennummern angeordnet sind.
Zeigen Sie die einzelnen Schritte. Wie erh\"alt man im Anschluss
die topologische Sortierung?

\begin{figure*}[h]
  \begin{center}
    \includegraphics[scale=2]{u12_topoGraph}
  \end{center}
\end{figure*}

\item 
  (\emph{freiwillig}, 5 Zusatzpunkte)
  Beweisen Sie, dass der Algorithmus aus (b) funktioniert.

  \emph{Hinweis:} F\"uhren Sie einen Widerspruchsbeweis.
    Nehmen Sie an, es g\"abe eine Kante $e$ von einem  sp\"ateren zu einem
    fr\"uheren Knoten in \texttt{topoSort}, und \"uberlegen Sie sich, was
    passiert, wenn $\texttt{dfs}$ die Kante $e$ untersucht.
    Beachten Sie dabei, dass es einen Unterschied macht, ob die 
    Tiefensuche f\"ur den Endpunkt von $e$ noch aktiv ist.
\end{enumerate}

\end{description}
\end{document}
