aboutsummaryrefslogtreecommitdiff
path: root/assignment5.tex
blob: 903b0e36ea7f5cfec06ed4caf5af548ca79182d2 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
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}