From 4e978accd53ca8e368bf6adf6200a73d7ac5e4e1 Mon Sep 17 00:00:00 2001
From: Yigit Sever
Date: Sun, 15 Nov 2020 03:43:42 +0300
Subject: Type the first draft of answer to question 1

---
 main.tex | 49 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 49 insertions(+)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index fae7bf7..da46b2a 100644
--- a/main.tex
+++ b/main.tex
@@ -31,6 +31,55 @@
 \section{Checking Consistency of Judgements}%
 \label{sec:checking_consistency_of_judgements}
 
+Given the collection of $n$ butterflies and a potential judgement between every pair (or not if the judgement is ambiguous), we have a graph $G = (V, E)$ with $n = |V|$ vertices and $|E| = m \le \frac{n(n-1)}{2}$ edges, with every edge $(i, j) \in E$ labelled either \enquote{same} or \enquote{different}. At the end of our algorithm, the vertices should be \emph{consistently} labelled as either \texttt{A} and \texttt{B} or our algorithm should be able to prove that $G$ cannot be labelled as so.
+
+A modified graph traversal using either BFS or DFS (since a node can be discovered multiple times in both of them) will work. Here we will modify the graph traversal given on \emph{page 42} on our \nth{3} lecture slides that uses BFS. The input of the algorithm is a node $s \in E$. If, due to ambiguous (i.e.\ missing) nodes, the graph is not connected, the algorithm should be run until every connected component is discovered.
+% TODO: run until every cc is discovered is handwavey <15-11-20, yigit> %
+
+{\centering
+    \begin{minipage}{.7\linewidth}
+        \begin{algorithm}[H]
+            \SetKwProg{Fn}{function}{}{end}
+            \DontPrintSemicolon{}
+            \SetAlgoLongEnd{}
+            \Fn{consistency\_check(s: node)}{
+                \KwData{$K$ = data structure of discovered nodes}
+                \KwResult{boolean = whether $G$ is consistent or not}
+                \textbf{label} $s$ as \texttt{A} \tcc*[r]{the opposite label is B}
+                put $s$ in $K$\;
+                \While{$K$ is not empty}{
+                    take a node $v$ from $K$\;
+                    \If{$v$ is not marked \enquote{explored}}{
+                        mark $v$ \enquote{explored}\;
+                        \For{each edge $(v, w)$ incident to $v$}{
+                            \uIf{$w$ is labelled}{
+                                \If{the label of $w$ is not consistent with the label of $v$ with respect to the judgement $(v,w$)}{
+                                    terminate the algorithm; $G$ is \textbf{inconsistent}\;
+                                }
+                            }
+                            \Else{
+                                \uIf{$(v,w)$ is labelled \enquote{same}}{
+                                    \textbf{label} $w$ with the label of $v$\;
+                                }
+                                \Else(\tcc*[f]{$(v,w)$ is labelled \enquote{different}}){
+                                    \textbf{label} $w$ with the opposite label of $v$\;
+                                }
+                            }
+                            put $w$ in $K$\;
+                        }
+                    }
+                }
+                the spanned connected component is \textbf{consistent}
+            }
+            \caption{Modified graph traversal algorithm so solve judgement consistency checking problem}%
+            \label{alg:question_1}
+        \end{algorithm}
+    \end{minipage}
+    \par
+}
+
+With the assumption that accessing the labels $(u, w)$ takes $\mathcal{O}(1)$ time this algorithm has the same running time as BFS; $\mathcal{O}(m+n)$.
+
 
 \section{Reachability}%
 \label{sec:reachability}
-- 
cgit v1.2.3-70-g09d2