1 files changed, 129 insertions, 8 deletions

diff --git a/main.tex b/main.tex
index 0fa91ec..3778cd4 100644
--- a/main.tex
+++ b/main.tex
@@ -1,4 +1,4 @@
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 % Lachaise Assignment
 % LaTeX Template
 % Version 1.0 (26/6/2018)
@@ -158,26 +158,147 @@ The algorithm in this instance runs in $\mathcal{O}(n)$ iterations, every propos
 
 % 1}}} %
 
-% question e TODO {{{1 %
+% question e ✅ {{{1 %
 
 \begin{question}
     Give another instance for which the algorithm requires $\Omega(n^{2})$ iterations (that is, it requires at least $cn^{2}$ iterations for some constant $0 < c \le 1)$, and prove this fact.
 \end{question}
 
-Arrange the preference lists such as every student arranges their preference \emph{exactly the same};
+\begin{infor}
+    We have collaborated with CENG567 student Manolya Atalay for this question and used the answers and explanations given in the linked Mathematics Stack Exchange question\footnote{\url{https://math.stackexchange.com/questions/1410898/worst-case-for-the-stable-marriage-problem}}.
+\end{infor}
+
+The worst problem instance for the algorithm (the instance that requires the largest number of steps) can be inferred as follows;
+
+The highest number of times a man $m$ can \emph{propose} (every iteration has one proposal in it) to $n$ many women is $n-1$. It cannot be $n$ because it would mean that $m$ did not find a suitable partner (rejected by everyone), which is contradictory with the algorithm's perfect matching guarantee.
+
+For $n$ men, in the worst case, each one can propose $n-1$ times; $n(n-1)$. One man has to propose one last time after getting rejected by $n-1$ women, giving the total number of proposals;
+
+\begin{equation}
+    n (n-1) + 1
+\end{equation}
+
+As the theoretical highest number of iterations \emph{Gale-Shapley} can have.
+
+As for the instance that produces this run time;
+
+Men have to arrange their preference list as follows for $n>2$.
 
 \begin{equation}
-    \label{eq:student_prefs_2}
-    C_1, C_2, \dots, C_{n}
+    M_{k} \rightarrow
+    \begin{cases}
+        W_{k}, W_{k+1}, \dots, W_{n-1}, W_{1}, W_{2}, \dots, W_{n} &\mbox{if } k \ne n \\
+        W_{k-1}, W_{k}, \dots, W_{n-1}, W_{1}, W_{2}, \dots, W_{n} &\mbox{if } k = n \\
+    \end{cases}
 \end{equation}
 
-Whereas every college should arrange their preference list as;
+In other words, the \emph{last} man's preference list is identical to one above them.
+
+Women have to arrange their preference list as follows for $n>2$;
 
 \begin{equation}
-    \label{eq:college_prefs_2}
-    S_n, S_{n-1}, S_{n-2}, \dots, S_{1}
+    W_{k} \rightarrow
+    \begin{cases}
+        M_{k+1}, M_{k}, \dots &\mbox{if } k \ne n-1 \\
+        M_{1}, M_{n}, \dots &\mbox{if } k = n-1 \\
+    \end{cases}
 \end{equation}
 
+The preference list of the last women $W_{n}$ does not matter neither does the order of the rest of the men in the preference list of the women given.
+
+We have implemented \emph{Gale-Shapley} and an instance set creation script to test our findings;
+
+\begin{commandline}[n=3]
+    \begin{verbatim}
+    n: Men Preference Table
+    A | 1 2 3
+    B | 2 1 3
+    C | 2 1 3
+    ----
+    Women Preference Table
+     1| B A C
+     2| A C B
+     3| A B C
+    ----
+    Matching B with 2 (a)
+    Matching C with 2, B is now free (b)
+    Matching A with 1 (a)
+    Matching B with 1, A is now free (b)
+    Matching A with 2, C is now free (b)
+    C is rejected by 1 because B is more preffered (c)
+    Matching C with 3 (a)
+    Final pairings:
+    A - 2
+    B - 1
+    C - 3
+
+    A proposed 2 times
+    B proposed 2 times
+    C proposed 3 times
+    total of 7 times with n(n-1) + 1 = 7
+    \end{verbatim}
+\end{commandline}
+
+\begin{commandline}[n=6]
+    \begin{verbatim}
+    n: Men Preference Table
+    A | 1 2 3 4 5 6
+    B | 2 3 4 5 1 6
+    C | 3 4 5 1 2 6
+    D | 4 5 1 2 3 6
+    E | 5 1 2 3 4 6
+    F | 5 1 2 3 4 6
+    ----
+    Women Preference Table
+     1| B A C D E F
+     2| C B A D E F
+     3| D C A B E F
+     4| E D A B C F
+     5| A F B C D E
+     6| A B C D E F
+    ----
+    Matching D with 4 (a)
+    Matching A with 1 (a)
+    Matching F with 5 (a)
+    E is rejected by 5 because F is more preffered (c)
+    Matching C with 3 (a)
+    Matching B with 2 (a)
+    // --- edited out for space ---
+    C is rejected by 1 because A is more preffered (c)
+    Matching C with 2, B is now free (b)
+    B is rejected by 3 because D is more preffered (c)
+    B is rejected by 4 because E is more preffered (c)
+    B is rejected by 5 because F is more preffered (c)
+    Matching B with 1, A is now free (b)
+    A is rejected by 2 because C is more preffered (c)
+    A is rejected by 3 because D is more preffered (c)
+    A is rejected by 4 because E is more preffered (c)
+    Matching A with 5, F is now free (b)
+    F is rejected by 1 because B is more preffered (c)
+    F is rejected by 2 because C is more preffered (c)
+    F is rejected by 3 because D is more preffered (c)
+    F is rejected by 4 because E is more preffered (c)
+    Matching F with 6 (a)
+    Final pairings:
+    E - 4
+    B - 1
+    A - 5
+    D - 3
+    C - 2
+    F - 6
+
+    A proposed 5 times
+    B proposed 5 times
+    C proposed 5 times
+    D proposed 5 times
+    E proposed 5 times
+    F proposed 6 times
+    total of 31 times with n(n-1) + 1 = 31
+   \end{verbatim}
+\end{commandline}
+
+
+
 % 1}}} %
 
 \section{Stable Matching Variation}%