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

\newcommand{\ZETTELNUMMER}{13}
\newcommand{\ABGABEDATUM}{am 2. Februar~2018 bis 10 Uhr 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}}
\newcommand{\N}{\mathbb{N}}

\renewcommand{\labelenumi}{(\alph{enumi})}


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

\smallskip
\noindent
\large
\textbf{Algorithmen, Datenstrukturen und Datenabstraktion}\hfill WS 17/18 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Katharina Klost


\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM\\
Dies ist das vorletzte Aufgabenblatt.

\vskip 0.5cm
\noindent

\begin{description}
\AUFGABE{Tries}{10 Punkte}

\begin{enumerate}
  \item Zeichnen Sie einen unkomprimierten und einen komprimierten Trie 
	f\"ur die W\"orter \{ALGORITHMUS, TRIE, BAUM, 
	TORUS, BAHN, TORPEDO\}.
  \item Entwickeln Sie einen Algorithmus, der alle W\"orter in einem 
  unkomprimierten Trie ausgibt und dabei jede Kante h\"ochstens zweimal 
  besucht.
\end{enumerate}

\AUFGABE{Implementierung von Tries}{10 Punkte}

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.

\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]{u13_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}


\AUFGABE{Collections in Java}{freiwillig, 10 Zusatzpunkte}

\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\_e Tutor\_in 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.



\end{description}

\noindent
\emph{Hinweis}:
Bitte formatieren Sie Ihre Abgaben mit \LaTeX\xspace oder einem
vergleichbaren elektronischen Textverarbeitungssystem. Ansonsten droht
der Abzug von bis zu 10\% der erreichbaren Punkte.



\end{document}
