From 5ec601c489f943c45d7df967e9d5f1490a0db62a Mon Sep 17 00:00:00 2001
From: Yigit Sever
Date: Sat, 7 Nov 2020 03:26:40 +0300
Subject: Added answer 1.e fully

---
 main.tex      | 137 ++++++++++++++++++++++++++++++++++++++++++++++++++++++----
 structure.tex |  32 ++++++++++++++
 2 files changed, 161 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}%
diff --git a/structure.tex b/structure.tex
index ae1765b..5f53a93 100644
--- a/structure.tex
+++ b/structure.tex
@@ -23,6 +23,8 @@
 \usepackage[T1]{fontenc} % Output font encoding for international characters
 \usepackage{csquotes}
 \usepackage{amsmath,amsfonts} % Math packages
+\usepackage{url}
+\usepackage{hyperref}
 \usepackage{enumerate} % Custom item numbers for enumerations
 \usepackage[ruled]{algorithm2e} % Algorithms
 \usepackage[makeroom]{cancel}
@@ -223,3 +225,33 @@
 }{
 	\end{mdframed}
 }
+
+%----------------------------------------------------------------------------------------
+%	NOT FUCKED UP INFORMATION ENVIRONMENT
+%----------------------------------------------------------------------------------------
+
+
+% Usage:
+% \begin{info}[optional title, defaults to "Info:"]
+% 	contents
+% 	\end{info}
+
+\mdfdefinestyle{infor}{%
+        topline=false, bottomline=false,
+        leftline=false, rightline=false,
+        nobreak,
+        singleextra={%
+                \fill[black](P-|O)circle[radius=0.4em];
+                \node at(P-|O){\color{white}\scriptsize\bf i};
+                \draw[very thick](P-|O)++(0,-0.8em)--(O);%--(O-|P);
+        }
+}
+
+% Define a custom environment for information
+\newenvironment{infor}[1][Disclaimer:]{ %
+        \medskip
+        \begin{mdframed}[style=infor]
+                \noindent{\textbf{#1}}
+}{
+        \end{mdframed}
+}
-- 
cgit v1.2.3-61-g4310