aboutsummaryrefslogtreecommitdiff
path: root/assignment4.tex
blob: 61aba7b6ea4e41501da34d0c5e4c20152eea45f4 (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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
\documentclass[10pt,a4paper]{article}

\usepackage[margin=2cm]{geometry}
\usepackage{multicol}

\usepackage{enumitem}
\setenumerate[1]{label=4.\arabic*.}
\setenumerate[2]{label=\textit{\alph*})}

\usepackage{hhline}

% 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{minted}

\usepackage{tikz}

\parindent0pt

\title{Algoritmen en Datastructuren - assignment 4}
\author{Camil Staps\\\small{s4498062}}

\tikzstyle{gray}=[fill=gray!20]
\tikzstyle{black}=[fill=gray!60]
\tikzstyle{active}=[draw=red]

\begin{document}

\maketitle
\thispagestyle{fancy}

\begin{multicols}{2}

\begin{enumerate}
    \item \begin{enumerate}
            \item See the figures below:\\[2pt]
                
                \begin{minipage}[b]{\linewidth}
                    \centering
                    \begin{tikzpicture}[->,node distance=15mm,every node/.style={shape=circle,draw,font=\scriptsize}]
                        \node (A) {$A$};
                        \node[right of=A] (B) {$B$};
                        \node[right of=B] (C) {$C$};
                        \node[right of=C] (D) {$D$};
                        \node[above of=A] (E) {$E$};
                        \node[right of=E] (F) {$F$};
                        \node[right of=F] (G) {$G$};
                        \node[right of=G] (H) {$H$};
                        \draw (A) -- (E); \draw (A) -- (B);
                        \draw (B) -- (C);
                        \draw (C) -- (G); \draw (C) -- (H);
                        \draw (E) -- (B); \draw (E) -- (F);
                        \draw (F) -- (B); \draw (F) -- (G);
                        \draw (G) -- (B); \draw (G) -- (H);
                        \draw (H) -- (D);
                    \end{tikzpicture}
                \end{minipage}\\

                \begin{minipage}[b]{\linewidth}
                    \centering
                    \begin{tikzpicture}[->,node distance=15mm,every node/.style={shape=circle,draw,font=\scriptsize}]
                        \node[active,gray] (A) {$0$};
                        \node[right of=A] (B) {$B$};
                        \node[right of=B] (C) {$C$};
                        \node[right of=C] (D) {$D$};
                        \node[above of=A] (E) {$E$};
                        \node[right of=E] (F) {$F$};
                        \node[right of=F] (G) {$G$};
                        \node[right of=G] (H) {$H$};
                        \draw (A) -- (E); \draw (A) -- (B);
                        \draw (B) -- (C);
                        \draw (C) -- (G); \draw (C) -- (H);
                        \draw (E) -- (B); \draw (E) -- (F);
                        \draw (F) -- (B); \draw (F) -- (G);
                        \draw (G) -- (B); \draw (G) -- (H);
                        \draw (H) -- (D);
                    \end{tikzpicture}
                \end{minipage}\\

                \begin{minipage}[b]{\linewidth}
                    \centering
                    \begin{tikzpicture}[->,node distance=15mm,every node/.style={shape=circle,draw,font=\scriptsize}]
                        \node[active,black] (A) {$0$};
                        \node[active,gray,right of=A] (B) {$1$};
                        \node[right of=B] (C) {$C$};
                        \node[right of=C] (D) {$D$};
                        \node[active,gray,above of=A] (E) {$1$};
                        \node[right of=E] (F) {$F$};
                        \node[right of=F] (G) {$G$};
                        \node[right of=G] (H) {$H$};
                        \draw (A) -- (E); \draw (A) -- (B);
                        \draw (B) -- (C);
                        \draw (C) -- (G); \draw (C) -- (H);
                        \draw (E) -- (B); \draw (E) -- (F);
                        \draw (F) -- (B); \draw (F) -- (G);
                        \draw (G) -- (B); \draw (G) -- (H);
                        \draw (H) -- (D);
                    \end{tikzpicture}
                \end{minipage}\\

                \begin{minipage}[b]{\linewidth}
                    \centering
                    \begin{tikzpicture}[->,node distance=15mm,every node/.style={shape=circle,draw,font=\scriptsize}]
                        \node[black] (A) {$0$};
                        \node[active,black,right of=A] (B) {$1$};
                        \node[active,gray,right of=B] (C) {$2$};
                        \node[right of=C] (D) {$D$};
                        \node[gray,above of=A] (E) {$1$};
                        \node[right of=E] (F) {$F$};
                        \node[right of=F] (G) {$G$};
                        \node[right of=G] (H) {$H$};
                        \draw (A) -- (E); \draw (A) -- (B);
                        \draw (B) -- (C);
                        \draw (C) -- (G); \draw (C) -- (H);
                        \draw (E) -- (B); \draw (E) -- (F);
                        \draw (F) -- (B); \draw (F) -- (G);
                        \draw (G) -- (B); \draw (G) -- (H);
                        \draw (H) -- (D);
                    \end{tikzpicture}
                \end{minipage}\\

                \begin{minipage}[b]{\linewidth}
                    \centering
                    \begin{tikzpicture}[->,node distance=15mm,every node/.style={shape=circle,draw,font=\scriptsize}]
                        \node[black] (A) {$0$};
                        \node[black,right of=A] (B) {$1$};
                        \node[gray,right of=B] (C) {$2$};
                        \node[right of=C] (D) {$D$};
                        \node[active,black,above of=A] (E) {$1$};
                        \node[active,gray,right of=E] (F) {$2$};
                        \node[right of=F] (G) {$G$};
                        \node[right of=G] (H) {$H$};
                        \draw (A) -- (E); \draw (A) -- (B);
                        \draw (B) -- (C);
                        \draw (C) -- (G); \draw (C) -- (H);
                        \draw (E) -- (B); \draw (E) -- (F);
                        \draw (F) -- (B); \draw (F) -- (G);
                        \draw (G) -- (B); \draw (G) -- (H);
                        \draw (H) -- (D);
                    \end{tikzpicture}
                \end{minipage}\\

                \begin{minipage}[b]{\linewidth}
                    \centering
                    \begin{tikzpicture}[->,node distance=15mm,every node/.style={shape=circle,draw,font=\scriptsize}]
                        \node[black] (A) {$0$};
                        \node[black,right of=A] (B) {$1$};
                        \node[active,black,right of=B] (C) {$2$};
                        \node[right of=C] (D) {$D$};
                        \node[black,above of=A] (E) {$1$};
                        \node[gray,right of=E] (F) {$2$};
                        \node[active,gray,right of=F] (G) {$3$};
                        \node[active,gray,right of=G] (H) {$3$};
                        \draw (A) -- (E); \draw (A) -- (B);
                        \draw (B) -- (C);
                        \draw (C) -- (G); \draw (C) -- (H);
                        \draw (E) -- (B); \draw (E) -- (F);
                        \draw (F) -- (B); \draw (F) -- (G);
                        \draw (G) -- (B); \draw (G) -- (H);
                        \draw (H) -- (D);
                    \end{tikzpicture}
                \end{minipage}\\

                \begin{minipage}[b]{\linewidth}
                    \centering
                    \begin{tikzpicture}[->,node distance=15mm,every node/.style={shape=circle,draw,font=\scriptsize}]
                        \node[black] (A) {$0$};
                        \node[black,right of=A] (B) {$1$};
                        \node[black,right of=B] (C) {$2$};
                        \node[right of=C] (D) {$D$};
                        \node[black,above of=A] (E) {$1$};
                        \node[active,black,right of=E] (F) {$2$};
                        \node[gray,right of=F] (G) {$3$};
                        \node[gray,right of=G] (H) {$3$};
                        \draw (A) -- (E); \draw (A) -- (B);
                        \draw (B) -- (C);
                        \draw (C) -- (G); \draw (C) -- (H);
                        \draw (E) -- (B); \draw (E) -- (F);
                        \draw (F) -- (B); \draw (F) -- (G);
                        \draw (G) -- (B); \draw (G) -- (H);
                        \draw (H) -- (D);
                    \end{tikzpicture}
                \end{minipage}\\

                \begin{minipage}[b]{\linewidth}
                    \centering
                    \begin{tikzpicture}[->,node distance=15mm,every node/.style={shape=circle,draw,font=\scriptsize}]
                        \node[black] (A) {$0$};
                        \node[black,right of=A] (B) {$1$};
                        \node[black,right of=B] (C) {$2$};
                        \node[right of=C] (D) {$D$};
                        \node[black,above of=A] (E) {$1$};
                        \node[black,right of=E] (F) {$2$};
                        \node[active,black,right of=F] (G) {$3$};
                        \node[gray,right of=G] (H) {$3$};
                        \draw (A) -- (E); \draw (A) -- (B);
                        \draw (B) -- (C);
                        \draw (C) -- (G); \draw (C) -- (H);
                        \draw (E) -- (B); \draw (E) -- (F);
                        \draw (F) -- (B); \draw (F) -- (G);
                        \draw (G) -- (B); \draw (G) -- (H);
                        \draw (H) -- (D);
                    \end{tikzpicture}
                \end{minipage}\\

                \begin{minipage}[b]{\linewidth}
                    \centering
                    \begin{tikzpicture}[->,node distance=15mm,every node/.style={shape=circle,draw,font=\scriptsize}]
                        \node[black] (A) {$0$};
                        \node[black,right of=A] (B) {$1$};
                        \node[black,right of=B] (C) {$2$};
                        \node[active,gray,right of=C] (D) {$4$};
                        \node[black,above of=A] (E) {$1$};
                        \node[black,right of=E] (F) {$2$};
                        \node[black,right of=F] (G) {$3$};
                        \node[active,black,right of=G] (H) {$3$};
                        \draw (A) -- (E); \draw (A) -- (B);
                        \draw (B) -- (C);
                        \draw (C) -- (G); \draw (C) -- (H);
                        \draw (E) -- (B); \draw (E) -- (F);
                        \draw (F) -- (B); \draw (F) -- (G);
                        \draw (G) -- (B); \draw (G) -- (H);
                        \draw (H) -- (D);
                    \end{tikzpicture}
                \end{minipage}\\

                \begin{minipage}[b]{\linewidth}
                    \centering
                    \begin{tikzpicture}[->,node distance=15mm,every node/.style={shape=circle,draw,font=\scriptsize}]
                        \node[black] (A) {$0$};
                        \node[black,right of=A] (B) {$1$};
                        \node[black,right of=B] (C) {$2$};
                        \node[active,black,right of=C] (D) {$4$};
                        \node[black,above of=A] (E) {$1$};
                        \node[black,right of=E] (F) {$2$};
                        \node[black,right of=F] (G) {$3$};
                        \node[black,right of=G] (H) {$3$};
                        \draw (A) -- (E); \draw (A) -- (B);
                        \draw (B) -- (C);
                        \draw (C) -- (G); \draw (C) -- (H);
                        \draw (E) -- (B); \draw (E) -- (F);
                        \draw (F) -- (B); \draw (F) -- (G);
                        \draw (G) -- (B); \draw (G) -- (H);
                        \draw (H) -- (D);
                    \end{tikzpicture}
                \end{minipage}\\

                The BFS tree is then:\\[2pt]
                
                \begin{minipage}[b]{\linewidth}
                    \centering
                    \begin{tikzpicture}[->,node distance=15mm,every node/.style={shape=circle,draw,font=\scriptsize}]
                        \node (A) {$0$};
                        \node[right of=A] (B) {$1$};
                        \node[right of=B] (C) {$2$};
                        \node[right of=C] (D) {$4$};
                        \node[above of=A] (E) {$1$};
                        \node[right of=E] (F) {$2$};
                        \node[right of=F] (G) {$3$};
                        \node[right of=G] (H) {$3$};
                        \draw (A) -- (E); \draw (A) -- (B);
                        \draw (B) -- (C);
                        \draw (C) -- (G); \draw (C) -- (H);
                        \draw (E) -- (F);
                        \draw (H) -- (D);
                    \end{tikzpicture}
                \end{minipage}\\

            \item This gives:\\[2pt]

                \begin{minipage}[b]{\linewidth}
                    \centering
                    \begin{tikzpicture}[->,level 1/.style={sibling distance=20mm},level 2/.style={sibling distance=15mm},node distance=15mm,every node/.style={shape=circle,draw,font=\tiny,align=center}]
                        \node {$A$\\$1/16$}
                            child { node {$B$\\$2/11$}
                                child { node {$C$\\$3/10$}
                                    child { node {$G$\\$4/9$}
                                        child { node {$H$\\$5/8$}
                                            child { node {$D$\\$6/7$} }
                                        }
                                        child { node[gray] {$B$} }
                                    }
                                    child { node[gray] {$H$} }
                                }
                            }
                            child { node {$E$\\$12/15$} 
                                child { node[gray] {$B$} }
                                child { node {$F$\\$13/14$}
                                    child { node[gray] {$B$} }
                                        child { node[gray] {$G$} }
                                }
                            };
                    \end{tikzpicture}
                \end{minipage}
        \end{enumerate}

    \item \begin{enumerate}[label=\arabic*)]
            \item Compute $\{(v,degree[v]) \mid v\in V\}$; this can be done in $\pazocal O(|V|+|E|)$.
            \item Using those vertex-degree pairs, compute for every vertex the sum of the degrees of its neighbours: also this is simply looping the vertices and their edges and can therefore be done in $\pazocal O(|V|+|E|)$.
        \end{enumerate}

        Since both parts of the algorithm are $\pazocal O(|V|+|E|)$, the whole algorithm is that as well.

    \item \begin{enumerate}[label=\arabic*)]
            \item Let $A = \emptyset$, $Q := \{(r,\emptyset)\}$.
            \item Choose a $(v,P)\in Q$, and remove it from the queue.
            \item For every child $c$ of $v$, add $(v',c)$ to $A$ for all $v'\in P\cup\{v\}$. Then, add $(c, P\cup\{v\})$ to $Q$.
            \item If $Q\neq\emptyset$, go back to 2.
        \end{enumerate}

        We keep a queue $Q$ of nodes $v$ that we have to check still and their ancestors $P$. Then for every child $c$ of a node $v$ in $Q$, we add $(c,v')$ to the list of child-ancestor pairs that is $A$. 

        We only visit every edge once, so this is done in linear time. 

    \item Place a pointer at the top left of the adjacency matrix, at the edge $(0,0)$. Then, walk towards the bottom right using the following rules:

        \begin{itemize}
            \item If I read a $0$ (there is no edge), I go right.
            \item If I read a $1$ (there is an edge), I go down.
        \end{itemize}

        This takes $\pazocal O(|V|)$ time (at most $2|V|-2$ steps). The rationale is that the row that we are belongs to the vertex we're currently checking if it could be a sink. If we read a zero, the vertex we're checking doesn't have that particular outgoing edge, so we stay in the same row. If we read a one, the vertex does have an outgoing edge, so we can go to the next one. 

        However, we don't check all edges for every vertex (that would require $\pazocal O(|V|^2)$ time). Therefore, in the final position we need to check that the row we are in is all-zero, and that the corresponding column has all-one (except on the diagonal) -- i.e., we need to verify that the vertex we end up in actually is a sink. This is also $\pazocal O(|V|)$.

    \item \begin{enumerate}
            \item \begin{proof}
                Suppose without loss of generality that we colour $v_1$ blue. Then $v_2$ must be red, $v_3$ blue, and in general every $v_i$ with odd $i$ is blue and every $v_j$ with even $j$ red. Then $v_k$ must be blue. However, then $c(v_1)=c(v_k)$ while $(v_k,v_1)\in E$. This is in contradiction with the definition of a 2-colouring. Hence, there exists no 2-colouring in a graph with an odd-length cycle.
                \end{proof}

            \item We apply BFS and colour every odd-distance vertex blue, while we colour every even-distance vertex red. 

                \begin{proof}
                    Suppose now there are two adjacent vertices $v_1,v_2$ with the same colour. Then say without loss of generality this is blue (and thus that they both have odd-distance to the root $r$). Then their distance to the root must be the same, because if the distances are $d,d+2k$ for some $k\in\mathbb N^+$, the distance $d+2k$ cannot be minimal: there is a shorter path from the root, through the other vertex, with length $d+1$.

                    Then if the distance to the root is the same and there is an edge in between, there is a cycle $(r,\dots,v_1,v_2,\dots,r)$. This cycle has length $d+d+1$ which is odd. But this is in contradiction with the assumption there are no odd-length cycles.

                    Therefore, there are no two adjacent vertices with the same colour, hence the colouring is correct.
                \end{proof}
        \end{enumerate}

    \item A possible way to write this down would be:

        \begin{enumerate}[label=\arabic*)]
            \item Let $S:=[]$, and compute $Q$ as all vertices without incoming edges.
            \item Take a vertex $v$ from $Q$, and add it to the tail of $S$.
            \item For every node $(v,v')$, remove it from the graph, and add $v'$ to $Q$ if it has no other incoming edges.
            \item If $Q$ is non-empty, go back to 2) -- otherwise, terminate.
        \end{enumerate}
        
        \begin{proof}
            A vertex with in-degree zero is (one of) the first vertex(ices) of the graph in topological order. Furthermore, there is always such a vertex, because otherwise there is a cycle (or $V=\emptyset$). Then by induction it follows that the same holds for every subgraph with the edges of that vertex with in-degree zero removed. Therefore, the algorithm is correct.
        \end{proof}
\end{enumerate}

\end{multicols}

\end{document}