path: root/assignment4.tex

\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}