End commit for the thursday session

3 hours worth of work, two days till deadline

1 files changed, 115 insertions, 23 deletions

diff --git a/main.tex b/main.tex
index 2676213..2803200 100644
--- a/main.tex
+++ b/main.tex
@@ -179,7 +179,7 @@ Whereas every college should arrange their preference list as;
 \section{Stable Matching Variation}%
 \label{sec:stable_matching_variation}
 
-% stable matching question TODO {{{1 %
+% stable matching question ALMOST {{{1 %
 
 \begin{question}
     Consider a Stable Matching problem with men and women.
@@ -188,24 +188,79 @@ Whereas every college should arrange their preference list as;
     Either give a proof that shows such an improvement is impossible, or give an example preference list for which an improvement for $w$ is possible.
 \end{question}
 
-TRUTH
-Matching x with a (a)
-Matching y with b (a)
-z is rejected by a because x is more preffered (c)
-z is rejected by b because y is more preffered (c)
-Matching z with c (a)
-[('x', 'a'), ('y', 'b'), ('z', 'c')]
-
-LIE
-
-Matching y with b (a)
-Matching z with a (a)
-x is rejected by a because z is more preffered (c)
-Matching x with b, y is now free (b)
-Matching y with a, z is now free (b)
-z is rejected by b because x is more preffered (c)
-Matching z with c (a)
-[('x', 'b'), ('y', 'a'), ('z', 'c')]
+Example preference list for men; $M = {x,y,z}$ and women: $W = {a,b,c}$.
+
+\begin{table}[!htb]
+    \caption{Preference lists of women.}
+    \begin{minipage}{.5\linewidth}
+        \caption{Everyone is being truthful}
+        \centering
+        \begin{tabular}{l|lll}
+            \textbf{a} & y & x & z \\
+            \textbf{b} & x & y & z \\
+            \textbf{c} & x & y & z
+        \end{tabular}
+    \end{minipage}%
+    \begin{minipage}{.5\linewidth}
+        \centering
+        \caption{a is lying about their preference}
+        \begin{tabular}{l|lll}
+            \textbf{a} & y & z & x \\
+            \textbf{b} & x & y & z \\
+            \textbf{c} & x & y & z
+        \end{tabular}
+        \begin{tikzpicture}[overlay]
+         \draw[red, line width=1pt] (-0.72,0.52) ellipse (0.70cm and 0.2cm);
+        \end{tikzpicture}
+    \end{minipage}
+\end{table}
+
+% TODO: final polish, highlight the lies <06-11-20, yigit> %
+
+\begin{table}[htb]
+    \centering
+    \begin{tabular}{l|lll}
+        \textbf{x} & a & b & c \\
+        \textbf{y} & b & a & c \\
+        \textbf{z} & a & b & c
+    \end{tabular}
+    \caption{The preference lists of the men.}%
+    \label{tab:men_pref}
+\end{table}
+
+The trace of \emph{Gale-Shapley} algorithm for the truth telling case;
+
+\begin{enumerate}
+    \item Matching x with a (a)
+    \item Matching y with b (a)
+    \item z proposes to a but gets rejected because a prefers x more (c)
+    \item z proposes to b but gets rejected because b prefers y more (c)
+    \item Matching z with c (a)
+\end{enumerate}
+
+\begin{align*}
+    x &\rightarrow a \\
+    y &\rightarrow b \\
+    z &\rightarrow c
+\end{align*}
+
+The trace of \emph{Gale-Shapley} algorithm when \emph{a} lies about their preferences;
+
+\begin{enumerate}
+    \item Matching y with b (a)
+    \item Matching z with a (a)
+    \item x proposes to a but gets rejected because a prefers z more (c)
+    \item Matching x with b, y is now free (b)
+    \item Matching y with a, z is now free (b)
+    \item z proposes to b but gets rejected because b prefers x more (c)
+    \item Matching z with c (a)
+\end{enumerate}
+
+\begin{align*}
+    x &\rightarrow b \\
+    y &\rightarrow a \\
+    z &\rightarrow c
+\end{align*}
 
 % 1}}} %
 
@@ -371,18 +426,55 @@ Finally, picking $c2 > 2$ proves the conjecture.
 
 % 1}}} %
 
-% question b FULL TODO {{{1 %
-% TODO: haven't started yet <05-11-20, yigit> %
+% question b {{{1 %
+% https://people.cs.umass.edu/~sheldon/teaching/cs311/hw/hw01.pdf
 
 \begin{question}
-    For each function $f(n)$ below, find (and prove that) (1) the smallest integer constant H such that $f(n) = \mathcal{O}(n^H)$, and (2) the largest positive real constant L such that $f(n) = \Omega(n^L)$.
-Otherwise, indicate that H or L do not exist.
+    For each function $f(n)$ below, find (and prove that)
+    \begin{enumerate}
+        \item the smallest integer constant H such that $f(n) = \mathcal{O}(n^H)$
+        \item the largest positive real constant L such that $f(n) = \Omega(n^L)$
+    \end{enumerate}
+    Otherwise, indicate that H or L do not exist.
 \end{question}
 
 \begin{info}[]
     $f(n) = \frac{n(n+1)}{2}$
 \end{info}
 
+(1) For $n_{0} \ge 1$; $\frac{n(n+1)}{2}$ is strictly smaller than $n^{2}$, yet $H=1$ is not possible since through the definition of Big-$\mathcal{O}$ notation it implies that for a \emph{constant} $c$;
+
+\begin{align*}
+    0 \le \frac{n(n+1)}{2} &\le c\cdot n \\
+    \frac{\cancel{n}(n+1)}{2} &\le c\cdot \cancel{n} \\
+    \frac{n+1}{2} &\cancel{\le} c
+\end{align*}
+
+Hence $f(n) = \mathcal{O}(n^{2})$ and $H=2$.
+
+% TODO: reread proof, strengthen? <06-11-20, yigit> %
+(2)$L=2$. We can pick the constant $c = \frac{1}{2}$ and write the Big-$\Omega$ notation;
+
+\begin{gather*}
+    c > 0 ~ \text{and} ~ n_{0} \ge 0 \\
+    \frac{n(n+1)}{2} \ge \frac{1}{2} n^{2} \\
+    \frac{\cancel{n}(n+1)}{\cancel{2}} \ge \frac{1}{\cancel{2}} n^{\cancel{2}} \\
+    n+1 \ge n
+\end{gather*}
+
+Does a $L>2$ work? Pick any $\ell > 2$;
+
+\begin{gather*}
+    c > 0 ~ \text{and} ~ n_{0} \ge 0 \\
+    \frac{n(n+1)}{2} \ge \frac{1}{2} n^{\ell} \\
+    \frac{n(n+1)}{\cancel{2}} \ge \frac{1}{\cancel{2}} n^{\ell} \\
+    n(n+1) \ge n^{\ell} \\
+    n+1 \ge n^{\ell - 1} \\
+    1 \ge n(n^{\ell - 2} - 1)
+\end{gather*}
+
+The final equation does not hold $n>1$ so $L>2$ cannot be true.
+
 \begin{info}[]
     $f(n) = \sum^{\lceil{\log{n}}\rceil}_{k=0} \frac{n}{2^{k}}$
 \end{info}