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

\newcommand{\ZETTELNUMMER}{14}
\newcommand{\ABGABEDATUM}{am 6. Februar 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\\
Dies ist das letzte Aufgabenblatt.

\vskip 0.5cm


\begin{description}

\AUFGABE{Bellman-Ford und negative Kreise}{10 Punkte}

Die folgende Variante des Algorithmus von Bellman-Ford
findet negative Kreise.
\begin{verbatim}
improve(e = uv)
  if u.d + e.length < v.d then
    v.d <- u.d + e.length; v.pred <- u
    return true
  else
    return false

bellman-ford(G, s)
  for v in G.vertices() do
    v.d <- INFTY; v.pred <- NULL
  s.d <- 0
  for i := 1 to |V|-1 do
    for e in G.edges() do
      improve(e)
  for e in G.edges() do
    if improve(e) then
      return "Negative cycle found."
  return "There is no negative cycle."
\end{verbatim}

\begin{enumerate}
  \item F\"uhren Sie den Algorithmus auf den folgenden 
    Graphen aus. Nehmen Sie dabei an, dass die Kanten
    in lexikographischer Reihenfolge durchlaufen werden
    (mit $s$ als erstem Knoten). Zeigen Sie die einzelnen Schritte.

  \begin{center}
    \includegraphics[scale=1.5]{u14_bfgraph}
  \end{center}
  \item Beweisen Sie, dass der Algorithmus korrekt ist.
    
    \emph{Hinweis}: Nehmen Sie an, dass es einen negativen
      Kreis $C$ gibt und dass \texttt{improve} in der letzten Schleife
      f\"ur keine Kante von $C$ \texttt{true}
      liefert. Leiten Sie einen Widerspruch ab.

  \item (freiwillig, 5 Zusatzpunkte)
    Modifizieren Sie den Algorithmus so, dass er auch die
    Knoten eines negativen Kreises liefert. Begr\"unden
    Sie die Korrektheit und analysieren Sie die Laufzeit.
\end{enumerate}

\AUFGABE{Der Algorithmus von Floyd-Warshall}{10 Punkte}

Sei $G$ ein gerichteter gewichteter Graph ohne negative Kreise. 

\begin{enumerate}
 \item Geben Sie detaillierten Pseudocode f\"ur den 
   Algorithmus von Floyd-Warshall, um die \emph{L\"angen}
   aller paarweisen k\"urzesten Wege in $G$ zu bestimmen.
   Begr\"unden Sie, dass Ihr Algorithmus $O(|V|^3)$ Zeit und
   $O(|V|^2)$ Platz ben\"otigt.
\item \"Andern Sie Ihren Algorithmus so, dass er auch
  die k\"urzesten Wege selbst findet.
\end{enumerate}

\AUFGABE{Minimale aufspannende B\"aume}{10 Punkte}

\begin{enumerate}
\item Zeigen Sie: Sei $G$ ein ungerichteter
  gewichteter zusammenh\"angender Graph mit
  paarweise verschiedenen Kantengewichten. 
  Dann ist der MST von $G$ eindeutig.
\item Sei $G$ ein ungerichteter gewichteter 
  zusammenh\"angender Graph und $T$ ein MST f\"ur $G$.
  Sei $e$ eine Kante von $T$, so dass $G \setminus e$ zusammenh\"angend
  ist. Geben Sie einen Algorithmus,
  der in Zeit $O(|V| + |E|)$ einen MST f\"ur $G \setminus e$
  findet, wenn $T$ bekannt ist. Beweisen Sie, dass Ihr 
  Algorithmus korrekt ist.
\end{enumerate}

\AUFGABE {Das 8-Puzzle} {freiwillig, 10 Zusatzpunkte}

Das \emph{8-Puzzle} ist 
ein bekanntes Schiebespiel. Gegeben ist ein
3x3-Gitter, das acht verschiebbare Bl\"ocke enth\"alt,
die mit den Zahlen von 1 bis 8 beschriftet sind.
Eine Position des Gitters ist frei. Ziel ist es,
die Bl\"ocke mit so wenig Z\"ugen wie m\"oglich
in die richtige Reihenfolge zu bringen.
Dabei kann in jedem Zug ein Block,
der zu der freien Position benachbart ist (horizontal
oder vertikal), in diese Position geschoben werden.
Hier ein Beispiel:
\begin{verbatim}
    1  3        1     3        1  2  3        1  2  3        1  2  3
 4  2  5   =>   4  2  5   =>   4     5   =>   4  5      =>   4  5  6
 7  8  6        7  8  6        7  8  6        7  8  6        7  8 

  start         1 links         2 hoch        5 links          ziel
\end{verbatim}
%

\begin{enumerate}
\item Schreiben Sie ein Programm in Java, welches 
   das 8-Puzzle f\"ur eine gegebene Eingabe mit Breitensuche l\"ost. 
   Bedenken Sie,
   dass der Graph nicht explizit gegeben ist. Welche Probleme entstehen
   dadurch, und wie kann man sie l\"osen?

   Testen Sie Ihr Programm. Wie gut eignet es sich, um das 8-Puzzle zu l\"osen?
\item Verbessern Sie Ihr Programm mit $A^*$-Suche.
  Benutzen Sie dazu den \emph{Hamming-Sch\"atzer},
  welcher den Abstand zum Ziel durch die Anzahl der Bl\"ocke absch\"atzt,
  die nicht am richtigen Platz liegen.  Genauer: f\"ur eine
  gegebene Konfiguration des 8-Puzzles $v$ definieren wir den
  Sch\"atzer $h(v)$ als die Anzahl der Positionen im Gitter, an denen
  der aktuelle Block nicht der Zielkonfiguration entspricht (die freie
  Position wird hierbei nicht gez\"ahlt).

  Begr\"unden Sie, dass der Hamming-Sch\"atzer konsistent ist.
  Implementieren Sie $A^*$-Suche mit dem Sch\"atzer und testen
  Sie Ihr Programm.
\end{enumerate}

\emph{Credits:} Diese Aufgabe ist von Kevin Waynes COS 226 Vorlesung inspiriert.\\
\texttt{http://www.cs.princeton.edu/courses/archive/fall13/cos226/\\
assignments/8puzzle.html} 


\end{description}
\end{document}
