Start assignment 4

1 files changed, 345 insertions, 0 deletions

diff --git a/assignment4.tex b/assignment4.tex
new file mode 100644
index 0000000..d478b7d
--- /dev/null
+++ b/assignment4.tex
@@ -0,0 +1,345 @@
+\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 %todo
+
+    \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. %todo proof
+        \end{enumerate}
+
+    \item %todo
+\end{enumerate}
+
+\end{multicols}
+
+\end{document}
+