summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorYigit Sever2020-11-15 21:21:37 +0300
committerYigit Sever2020-11-15 21:21:37 +0300
commitaa1d726c5f26fec39f808b4722d8b180d87d7978 (patch)
treeb2536d13baa85baa973c91383a05662d285c235c
parent190240fc1bda361a45ad3c629ba3bb2fcdfeed00 (diff)
downloadhw2-master.tar.gz
hw2-master.tar.bz2
hw2-master.zip
Expand the answer to question 1HEADmaster
-rw-r--r--main.pdfbin204681 -> 207180 bytes
-rw-r--r--main.tex25
-rw-r--r--structure.tex2
3 files changed, 22 insertions, 5 deletions
diff --git a/main.pdf b/main.pdf
index 90b5044..738a4b4 100644
--- a/main.pdf
+++ b/main.pdf
Binary files differ
diff --git a/main.tex b/main.tex
index 96c5d5b..28c54bd 100644
--- a/main.tex
+++ b/main.tex
@@ -33,10 +33,9 @@
33\section{Checking Consistency of Judgements}% 33\section{Checking Consistency of Judgements}%
34\label{sec:checking_consistency_of_judgements} 34\label{sec:checking_consistency_of_judgements}
35 35
36Given 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. 36Given 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}, assuming $(i,j)$ is not judged again as $(j,i)$. 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.
37 37
38A 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. 38A modified graph traversal using either BFS or DFS 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 any node $s \in E$. If, due to ambiguous (i.e.\ missing) nodes, the graph is not connected, the algorithm should be run on a new undiscovered node until every connected component is discovered.
39% TODO: run until every cc is discovered is handwavey <15-11-20, yigit> %
40 39
41{\centering 40{\centering
42 \begin{minipage}{.7\linewidth} 41 \begin{minipage}{.7\linewidth}
@@ -82,6 +81,26 @@ A modified graph traversal using either BFS or DFS (since a node can be discover
82 81
83With 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)$. 82With 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)$.
84 83
84To give a short proof, consider the scenario below;
85
86\begin{tikzpicture}[auto]
87 \node [label={[red]left:$A$}] (a) at (90:1) {$a$};
88 \node [label={[red]right:$A$}] (b) at (45:2) {$b$};
89 \node [label={[red]right:$B$}] (c) at (0:2) {$c$};
90 \node [label={[red]left:$A$}] (d) at (240:1) {$d$};
91
92 \draw (a) to node {S} (b);
93 \draw (b) to node {D} (c);
94 \draw (c) to node {?} (d);
95 \draw (a) to node [swap] {S} (d);
96\end{tikzpicture}
97
98Consider the situation where we started at node $a$ with the label \texttt{A}, labelled $b$ with \texttt{A} due to \enquote{same} $(a,b)$ edge and labelled $d$ with \texttt{A} due to \enquote{same} $(a, d)$ edge.
99Node $c$ will be labelled with \texttt{B} due to \enquote{different} $(b, c)$ edge.
100Now, depending on the judgement on (or lack thereof) $(d,c)$ edge, the graph will be either consistent (if \enquote{different})
101or inconsistent (if \enquote{same}).
102Since the modified BFS above visits every node at least once and considers every edge at least once (property of BFS), an inconsistent path will be discovered or none will occur, meaning a consistent graph.
103
85\section{Reachability}% 104\section{Reachability}%
86\label{sec:reachability} 105\label{sec:reachability}
87 106
diff --git a/structure.tex b/structure.tex
index 3d039b4..1c33680 100644
--- a/structure.tex
+++ b/structure.tex
@@ -38,8 +38,6 @@
38\usetikzlibrary{arrows,fit,positioning} 38\usetikzlibrary{arrows,fit,positioning}
39\usepackage[style=authoryear]{biblatex} 39\usepackage[style=authoryear]{biblatex}
40 40
41
42
43\lstset{ 41\lstset{
44 basicstyle=\ttfamily, % Typeset listings in monospace font 42 basicstyle=\ttfamily, % Typeset listings in monospace font
45} 43}