diff options
| -rw-r--r-- | assignment5.tex | 120 |
1 files changed, 120 insertions, 0 deletions
diff --git a/assignment5.tex b/assignment5.tex new file mode 100644 index 0000000..903b0e3 --- /dev/null +++ b/assignment5.tex @@ -0,0 +1,120 @@ +\documentclass[10pt,a4paper]{article} + +\usepackage[margin=2cm]{geometry} +\usepackage{multicol} + +\let\assignment5 + +\usepackage{enumitem} +\setenumerate[1]{label=\assignment.\arabic*.} +\setenumerate[2]{label=\textit{\alph*})} + +% textcomp package is not available everywhere, and we only need the Copyright symbol +% taken from http://tex.stackexchange.com/a/1677/23992 +\DeclareTextCommandDefault{\textregistered}{\textcircled{\check@mathfonts\fontsize\sf@size\z@\math@fontsfalse\selectfont R}} + +\usepackage{fancyhdr} +\renewcommand{\headrulewidth}{0pt} +\renewcommand{\footrulewidth}{0pt} +\fancyhead{} +\fancyfoot[C]{Copyright {\textcopyright} 2015 Camil Staps} +\pagestyle{fancy} + +\usepackage{amsmath} +\usepackage{amsthm} +\usepackage{amsfonts} +\DeclareMathAlphabet{\pazocal}{OMS}{zplm}{m}{n} + +\usepackage{tikz} +\usepackage{array} +\usepackage{caption} +\usepackage[hidelinks]{hyperref} +\usepackage{url} + +\parindent0pt + +\title{Algoritmen en Datastructuren - assignment \assignment} +\author{Camil Staps\\\small{s4498062}} + +\begin{document} + +\maketitle +\thispagestyle{fancy} + +\begin{multicols}{2} + +\begin{enumerate} + \item See table \ref{tab:dijkstra}. + + \begin{minipage}{\linewidth} + \centering + \scriptsize + \begin{tabular}{r *{8}{| >{$}c<{$}}} + Relaxing & A & B & C & D & E & F & G & H \\\hline + -- & 0 & \infty & \infty & \infty & \infty & \infty & \infty & \infty \\ + A & 0 & 5 & \infty & \infty & 4 & \infty & \infty & \infty \\ + E & 0 & 5 & \infty & \infty & 4 & 15 & \infty & \infty \\ + B & 0 & 5 & 11 & \infty & 4 & 15 & 15 & \infty \\ + C & 0 & 5 & 11 & 12 & 4 & 15 & 15 & 28 \\ + D & 0 & 5 & 11 & 12 & 4 & 15 & 15 & 24 \\ + F & 0 & 5 & 11 & 12 & 4 & 15 & 15 & 24 \\ + G & 0 & 5 & 11 & 12 & 4 & 15 & 15 & 24 \\ + H & 0 & 5 & 11 & 12 & 4 & 15 & 15 & 24 + \end{tabular} + \captionof{table}{Running Dijkstra's algorithm} + \label{tab:dijkstra} + \end{minipage} + + \item See table \ref{tab:bellmanford}\footnote{NB: in the slides that were given to us I couldn't find the use of $\pi$ as a variable. I'm assuming $\pi[v]$ means the parent (predecessor) of $v$, as in \url{http://web.cs.ucdavis.edu/~bai/ECS122A/ShortPathAlgs.pdf}.}. We see that after three passes we cannot relax any edge any more. Therefore, there does not exist a negative-weight cycle. + + \begin{minipage}{\linewidth} + \centering + \scriptsize + \begin{tabular}{r *{5}{| >{$}c<{$}}} + Pass & s & t & x & y & z \\\hline + 0 & (\infty, \bot) & (\infty, \bot) & (\infty, \bot) & (\infty, \bot) & (0, \bot) \\ + 1 & (2, z) & (8, s) & (7, z) & (9, s) & (0, \bot) \\ + 2 & (2, z) & (5, x) & (6, y) & (9, s) & (0, \bot) \\ + 3 & (2, z) & (4, x) & (6, y) & (9, s) & (0, \bot) \\ + 4 & (2, z) & (4, x) & (6, y) & (9, s) & (0, \bot) \\ + \end{tabular} + \captionof{table}{Running the Bellman-Ford algorithm} + \label{tab:bellmanford} + \end{minipage} + + \item See figure \ref{fig:dijkstra-incorrect}. Dijkstra's algorithm does not take into account negative weights. While Bellman-Ford's algorithm will report the existence of a negative-weight cycle, Dijkstra's algorithm will not do this. It will report distance of $0$ and $1$ for the source vertex and the other vertex, while in fact both vertices have a distance of $-\infty$ from the source. + + \begin{minipage}{\linewidth} + \centering + \begin{tikzpicture}[node distance=2cm,->,>=stealth] + \node[draw,circle] (A) {A}; + \node[draw,circle,right of=A] (B) {B}; + \draw (A) edge[bend left] node[above] {-1} (B); + \draw (B) edge[bend left] node[below] {-1} (A); + \end{tikzpicture} + \captionof{figure}{A graph on which Dijkstra's algorithm produces incorrect results} + \label{fig:dijkstra-incorrect} + \end{minipage} + + \item In a directed graph with non-negative weights from $\{0,1,\dots,W\}$, we know every edge will at most have weight $W\cdot(|V|-1)$. We can thus use a $W\cdot(|V|-1)$-length array, and at index $i$ store a list of the vertices with maximum distance $i$. At the beginning, the source vertex is at index $0$ and all others are at index $W\cdot(|V|-1)-1$. Then, we iterate over the array starting at index $0$, and for every vertex, say at index $i$ we apply the relaxation step (which means moving vertices from their index $j$ to a lower index $j'\geq i$). + + Iterating the array takes $\pazocal O(W\cdot|V|)$, and every edge is visited only once, so that takes $\pazocal O(|E|)$. Therefore, this algorithm runs in $\pazocal O(W\cdot|V|+|E|)$. + + \item We can use Bellman-Ford, where we don't relax every edge $|V|-1$ times, but just $k$ times. We are then sure to have correct distances for the vertices that are at most $k$ edges away from the source vertex. Since Bellman-Ford runs in $\pazocal O(|V|\cdot|E|)$, this will run in $\pazocal O(k\cdot|E|)$. + + \item First, build a set $$D = \{(x,y,d(x,y)) \mid x,y\in \{s,t\}\cup C\},$$ where $$C=\{u \mid (u,\dots)\in E' \text{ or } (\dots,u)\in E'\}.$$ + + We then have all distances between $s$ and $u$, $u$ and $v$, $v$ and $t$, $s$ and $v$, $u$ and $t$, and $s$ and $t$. To build $C$ has complexity $\pazocal O(|E'|)$. To build $D$ takes $\pazocal O(|C|^2)\cdot p$, where $p$ is the complexity of the search algorithm you're using to find $d(x,y)$. + + Next, we let $r:=(\bot,\infty)$ and for every $(u,v) = e' \in E'$ we do $r:=(e',d(s,u) + d(u,v) + d(v,t))$ if $d(s,u)+d(u,v)+d(v,t) < \mathrm{snd}(r)$. We also do $r:=(e',d(s,v) + d(u,v) + d(u,t))$ if $d(s,v)+d(u,v)+d(u,t) < \mathrm{snd}(r)$. + + For this step we use $D$ (so that we don't calculate the same distance over and over again). This takes $\pazocal O(|E'|)\cdot a_D$, where $a_D$ is the complexity of the access function of $D$. + + Finally we return $\mathrm{fst}(r)$. + +\end{enumerate} + +\end{multicols} + +\end{document} + |