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

\newcommand{\ZETTELNUMMER}{10}
\newcommand{\ABGABEDATUM}{am 5. Juli 2016 bis 12 Uhr in die
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{Informatik B}\hfill SoSe 2016 \\[0.5ex]
\normalsize
Wolfgang Mulzer

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm


\begin{description}

\AUFGABE{Stapel und Schlangen}{10 Punkte}

\begin{enumerate}
\item
Beschreiben Sie, wie man den ADT \emph{Schlange} mit 
zwei Stapeln implementieren kann. 
Was ist die Laufzeit der Methoden \texttt{enqueue} und 
\texttt{dequeue} in diesem Fall?
\item 
Beschreiben Sie, wie man den ADT \emph{Stapel} mit 
zwei Schlangen implementieren kann.
Was ist die Laufzeit der Methoden \texttt{pop} und 
\texttt{push} in diesem Fall?
\item Setzen Sie beides in Java um.
\end{enumerate}

\AUFGABE{Suchb\"aume}{10 Punkte}

\begin{enumerate}
\item 
Zeichnen Sie den bin\"aren Suchbaum, der entsteht, 
wenn man die ganzen Zahlen 
\[
23;\, 35;\, 8;\, 57;\, 54;\, 31;\, 3;\, 10;\, 15
\]
in dieser Reihenfolge einf\"ugt. Zeigen Sie die 
einzelnen Schritte.
\item 
Entfernen Sie in dieser Reihenfolge die Elemente 
\[ 
35;\, 10;\, 3
\]
aus dem Suchbaum. Zeigen Sie die einzelnen
Schritte.
\item Wiederholen Sie die beiden Teilaufgaben (a) und
(b) mit einem AVL-Baum.
\end{enumerate}

\AUFGABE{Ein Graph}{10 Punkte}

Die W\"orter einer festen L\"ange $n$ \"uber dem 
Alphabet $\{A, C, G, T\}$ bilden die Knotenmenge
$V_n$ eines ungerichteten Graphen $G_n = (V_n, E_n)$. 
Zwei solche W\"orter seien adjazent,
wenn sie sich an genau einer Stelle unterscheiden (und sonst gleich sind), also
Hamming-Abstand 1 haben.
\begin{enumerate}
\item Zeichnen Sie den Graphen $G_1$.  
\item Welchen Grad haben die Knoten von $G_n$? Wieviele Knoten und wieviele Kanten
hat $G_n$? Begr\"unden Sie Ihre Antwort!
\item
Wie lang ist ein k\"urzester Weg zwischen zwei Knoten h\"ochstens?
Begr\"unden Sie Ihre Antwort kurz.
\item Ein Kreis in einem Graphen hei\ss{}t \emph{Hamiltonkreis}, wenn er jeden Knoten
genau einmal besucht. Argumentieren Sie, dass $G_n$ einen
Hamiltonkreis besitzt.
\end{enumerate}
\end{description}
\end{document}
