From fc8a61e6be6141ae3cbe9c1801484cf02eb30e00 Mon Sep 17 00:00:00 2001
From: Camil Staps
Date: Sat, 3 Oct 2015 12:34:57 +0200
Subject: Assignment 5

---
 assignment5.tex | 120 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 120 insertions(+)
 create mode 100644 assignment5.tex

(limited to 'assignment5.tex')

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}
+
-- 
cgit v1.2.3

