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

\newcommand{\ZETTELNUMMER}{14}
\newcommand{\ABGABEDATUM}{on 08. February~2019, 10:00, in the
respective TA's mailbox}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Problem \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{\R}{\mathbb{R}}

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


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Problem Set on

\smallskip
\noindent
\large
\textbf{Algorithms, Data Structures and Data 
Abstraction}\hfill WS 18/19 \\[0.5ex]
\normalsize
Wolfgang Mulzer

\medskip\hrule

\smallskip
\noindent
\textbf{Due} \ABGABEDATUM

\noindent
This is the final problem set.
\vskip 0.5cm

\begin{description}

\AUFGABE{The 8-Puzzle}{10 Points}

The \emph{8-puzzle} is 
a well-known puzzle. We are given a 
$3 \times 3$-grid that contains eight movable blocks that
are labeled with the numbers from 1 to 8.
One position in the grid is not occupied. The goal
is to bring the blocks into the right order,
with the minimum number of moves.
In each move, we can shift a block that is next to
the free position (horizontally or vertically) into
this position.
Here is an example:
\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 left         2 up           5 left         target
\end{verbatim}
%

\begin{enumerate}
\item Write a program that uses breadth-first-search
   to solve the 8-puzzle for a given instance. Note that
   the graph is not given explicitly. Which problems does 
   this create, and how do you solve them?

   Test your program. How well does it work (in terms of speed,
   effectiveness in finding a solution, etc)?
\item Use $A^*$-search to improve your program from (a).
  Use the \emph{Hamming-heuristic} that estimates
  the distance to the target by the number of blocks that
  are not in their target position.
  More precisely, for a given configuration $v$ of the
  $8$-puzzle, we define 
  $h(v)$ as the number of positions in the grid where
  the current block does not match the block in the
  target configuration
  (the free position is not counted).

  Argue that the heuristic is consistent. Implement $A^*$-search
  with the Hamming-heuristic, and test your program.
\end{enumerate}

\emph{Credits:} This program is based on Kevin Wayne's COS 226 lecture.\\
\texttt{http://www.cs.princeton.edu/courses/archive/fall18/cos226/\\
assignments/8puzzle/specification.php} 

\AUFGABE{The Bellman-Ford Algorithm}{10 Points}

Another algorithm for the single-source shortest-path
problem is due to Bellman and Ford.
Let $G = (V,E)$ be a directed, weighted graph with
positive edge weights, and let $s$ be a starting node.
The pseudo-code is as follows:
\begin{verbatim}
relax(e)
  let a be the startvertex and b the endvertex of e
  // check whether the path over a is shorter
  if a.d + e.length < b.d then
    b.d <- a.d + e.length
    b.pred <- a

bellman-ford(G, s)
  // initalize vertices
  for v in G.vertices() do
    v.d <- INFTY
    v.pred <- NULL
  s.d <- 0
  // call relax on all edges |V| times
  for i := 1 to |V| do
    for e in G.edges() do
      relax(e)
\end{verbatim}

The algorithm uses a function 
\texttt{relax} that checks for a given edge
$e = ab$ whether the current path from $s$
to $a$, followed by $b$, is shorter than the current path 
from $s$ to $b$. The function
\texttt{relax} is called $|V|$ times for all edges.
\begin{enumerate}
\item What is the running time of the algorithm?
How does this compare to Dijkstra's algorithm?
\item  Perform the algorithm on the following graph, with start node
  $s$.

  \begin{centering}
    \includegraphics[scale=2]{u14_bfGraph}
  \end{centering}

  What happens if we change the weight of the edge $ab$ to $-5$?
  What happens if we change the weight of the edge $ab$ to $-10$?
  Try to give an explanation.
\item (voluntary, 5 extra points) Prove that 
the algorithm is correct.

  \emph{Hint:} You must show for each node $v \in V$, that
  the algorithm finds a shortest path from $s$ to $v$.
  Use induction to prove the following statement:
  if there is a shortest path from $s$ to $v$ that uses $j$ 
  edges, then the algorithm of Bellman-Ford has found a shortest
  path from $s$ to $v$ after iteration $j$ of the \texttt{for}-loop.
\end{enumerate}

\AUFGABE{Minimum Spanning Trees}{10 Points}

\begin{enumerate}
\item Prove that if all the edge weights in a connected, weighted graph $G$
are pairwise distinct, then the MST of $G$ is uniquely determined.
\item Let $G$ be a connected, weighted graph, and let
$T$ be an MST for $G$.
  Let $e$ be an edge of $G$, so that $G \setminus e$ is connected.
  Give an algorithm that finds an MST for $G \setminus e$
  in $O(|V| + |E|)$ time,
  assuming $T$ is given. 
  Justify the correctness and running time of your algorithm.
\end{enumerate}

\end{description}

\end{document}
