Initial commit

1 files changed, 350 insertions, 0 deletions

diff --git a/main.tex b/main.tex
new file mode 100644
index 0000000..c885da8
--- /dev/null
+++ b/main.tex
@@ -0,0 +1,350 @@
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% Lachaise Assignment
+% LaTeX Template
+% Version 1.0 (26/6/2018)
+%
+% This template originates from:
+% http://www.LaTeXTemplates.com
+%
+% Authors:
+% Marion Lachaise & François Févotte
+% Vel ([email protected])
+%
+% License:
+% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
+%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\documentclass{article}
+\input{structure.tex}
+
+\title{CENG567: Homework \#1}
+\author{Yiğit Sever}
+\date{\today}
+
+%----------------------------------------------------------------------------------------
+
+\begin{document}
+
+\maketitle
+
+\section{Stable Matching}%
+\label{sec:stable_matching}
+
+% question a ✅ {{{1 %
+
+\begin{question}%
+    \label{q:1_a}
+    Use \emph{Gale-Shapley} algorithm to find a stable matching for the following set of four colleges, four students and their preference lists.
+\end{question}
+
+\begin{commandline}[Gale-Shapley algorithm, from lecture slides, edited for the context]
+
+    \begin{verbatim}
+    Initialize each person to be free.
+    while (some student is free and hasn't applied to every college) {
+        Choose such a student m
+        c = 1st college on m's list to whom m has not yet applied
+        if (c is free)
+            assign c to m for potential application (a)
+        else if (c prefers m to their current applicant m')
+            assign m and c for potential application, and m' to be free (b)
+        else
+            c rejects m (c)
+    }
+    \end{verbatim}
+
+ \end{commandline}
+
+A quick trace of the algorithm;
+
+\begin{enumerate}
+    \item $S_1$ is free;
+        \begin{enumerate}
+            \item applies to first college on their preference list $C_4$;
+            \item $C_4$ is free so it accepts and is matched with $S_1$ (a).
+        \end{enumerate}
+    \item $S_2$ is free
+        \begin{enumerate}
+            \item applies to first college on their preference list; $C_1$
+            \item $C_1$ is free so it accepts and is matched with $S_2$ (a).
+        \end{enumerate}
+    \item $S_3$ is free;
+        \begin{enumerate}
+            \item applies to first college on their preference list; $C_1$
+            \item $C_1$ rejects $S_3$ because it prefers $S_2$ to $S_3$ (c).
+            \item applies to second college on their preference list; $C_2$
+            \item $C_2$ is free so it accepts and is matched with $S_3$ (a).
+        \end{enumerate}
+    \item $S_4$ is free;
+        \begin{enumerate}
+            \item applies to first college on their preference list; $C_4$
+            \item $C_4$ rejects $S_4$ because it prefers $S_1$ to $S_4$ (c).
+            \item applies to second college on their preference list; $C_3$
+            \item $C_3$ is free so it accepts and is matched with $S_4$ (a).
+        \end{enumerate}
+        \item There are no more free students to match, algorithm terminates.
+\end{enumerate}
+
+The final matching and the answer to Question~\ref{sec:stable_matching}(a) is;
+
+\begin{align*}
+    S_1 &\rightarrow C_4 \\
+    S_2 &\rightarrow C_1 \\
+    S_3 &\rightarrow C_2 \\
+    S_4 &\rightarrow C_3
+\end{align*}
+
+% 1}}} %
+
+% question b ✅ {{{1 %
+
+\begin{question}
+    Find another stable matching with the same algorithm.
+\end{question}
+
+All executions of \emph{Gale-Shapley} yield the same stable matching (that is proposer-optimal) and cannot produce \emph{another} stable matching like the question text asks for.
+
+% 1}}} %
+
+% question c ✅ {{{1 %
+
+\begin{question}
+    Consider a pair of man $m$ and woman $w$ where $m$ has $w$ at the top of his preference list and $w$
+    has $m$ at the top of her preference list. Does it always have to be the case that the pairing $(m, w)$ exist
+    in every possible stable matching? If it is true, give a short explanation. Otherwise, give a counterexample.
+\end{question}
+
+\emph{Proof by contradiction}.
+Assume that in the resulting matching of \emph{Gale-Shapley}, we have $S'$, where $m$ is matched with $w'$ and $w$ is matched with $m'$.
+
+The definition of stable matching dictates that there is \emph{no incentive to exchange}, yet in $S'$ $m$ can trade up to $w$ since $m$ prefers $w$ to $w'$ and $w$ can trade up since $w$ prefers $m$ to $m'$.
+
+$S'$ could not have occurred since men propose in accordance to their preference list, which $w$ is on top of for $m$ and no other men that may propose to $w$ can make $w$ switch since they are not more preffered than $m$.
+
+% 1}}} %
+
+% question d TODO {{{1 %
+
+\begin{question}
+    Give an instance of $n$ colleges, $n$ students, and their preference lists so that the Gale-Shapley algorithm requires only $O(n)$ iterations, and prove this fact.
+\end{question}
+
+% TODO: you abused n and now they're both fucked <05-11-20, yigit> %
+
+Arrange the preference lists such as every $m^{\text{th}}$ student arranges their preference list such as;
+
+\begin{equation}
+    \label{eq:student_prefs}
+    C_n, C_{n-1}, C_{n-2}, \dots, C_{1}
+\end{equation}
+
+Whereas every college can arrange their preference list as;
+
+\begin{equation}
+    \label{eq:college_prefs}
+    S_n, S_{n-1}, S_{n-2}, \dots, S_{1}
+\end{equation}
+
+The arrangement in (\ref{eq:college_prefs}) is not crucial since no college will be given a chance to \enquote{trade up}.
+
+Every proposer applies to colleges in decreasing order from their preference list.
+For $n=1$, $S_1$ applies to $C_1$ and the algorithm terminates in $n=1$ steps.
+For $n=k$, $S_1$ applies to $C_1$ which is free, $S_2$ applies to $C_2$ which is again free up to $S_k$ which can freely apply to $C_k$ and the algorithm terminates in $k$ steps after every student applied to the college on top of their preference list which was guaranteed to be free.
+
+% 1}}} %
+
+% question e TODO {{{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{equation}
+    \label{eq:student_prefs_2}
+    C_1, C_2, \dots, C_{n}
+\end{equation}
+
+Whereas every college should arrange their preference list as;
+
+\begin{equation}
+    \label{eq:college_prefs_2}
+    S_n, S_{n-1}, S_{n-2}, \dots, S_{1}
+\end{equation}
+
+% 1}}} %
+
+\section{Stable Matching Variation}%
+\label{sec:stable_matching_variation}
+
+% stable matching question TODO {{{1 %
+
+\begin{question}
+    Consider a Stable Matching problem with men and women.
+    Consider a woman $w$ where she prefers man $m$ to $m'$, but both $m$ and $m'$ are low on her list of preferences.
+    Can it be the case that by switching the order of $m$ and $m'$ on her list of preferences (i.e., by falsely claiming that she prefers $m'$ to $m$) and running the algorithm with this modified preference list, $w$ will end up with a man $m''$ that she prefers to both $m$ and $m'$?
+    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')]
+
+% 1}}} %
+
+\section{Asymptotics}%
+\label{sec:asymptotics}
+
+% asymptotics TODO {{{1 %
+
+\begin{question}
+    What is the running time of this algorithm as a function of n? Specify a function f such that the running time of the algorithm is $\Theta(f(n))$.
+\end{question}
+
+
+% 1}}} %
+
+\section{Big $\mathcal{O}$ and $\Omega$}%
+\label{sec:big_o_and_omega_}
+
+% question a ALMOST DONE {{{1 %
+
+\begin{question}
+    Let $f(n)$ and $g(n)$ be asymptotically positive functions. Prove or disprove the following conjectures.
+\end{question}
+
+\begin{info}[]
+    $f(n) = \mathcal{O}(g(n))$ implies $g(n) = \mathcal{O}(f(n))$
+\end{info}
+
+From the definition of Big $\mathcal{O}$ notation given in the lecture slides;
+
+\begin{equation}%
+    \label{eq:a_bigo}
+    \exists ~ c > 0 \quad \text{and} \quad n_{0} \ge 0 \quad \mid \quad 0 \le f(n) \le c \cdot g(n) \quad \forall n \ge n_{0}
+\end{equation}
+
+If we rearrange the right hand side of the Proposition~\ref{eq:a_bigo};
+
+\begin{equation*}%
+    0 \le \frac{1}{c} f(n) \le g(n) \\
+\end{equation*}
+
+or simply,
+
+\begin{equation}
+    \label{eq:a_bio_rearranged}
+    0 \le c' f(n) \le g(n)
+\end{equation}
+
+By the definition of Big $\mathcal{O}$ notation, in order for $g(n) = \mathcal{O}(f(n))$ to be true,
+
+\begin{equation*}
+    \exists ~ k > 0 \quad \text{and} \quad n_{0}' \ge 0 \quad \mid \quad 0 \le g(n) \le k \cdot f(n) \quad \forall n' \ge n_{0}'
+\end{equation*}
+
+Has to be true, yet from Equation~\ref{eq:a_bio_rearranged} we know that $f(n)$ multiplied by some constant $c'$ is strictly smaller than $g(n)$. The conjecture is \emph{false}.
+
+\begin{info}[]
+    $f(n) = \mathcal{O}((f(n))^{2})$
+\end{info}
+
+% TODO: this is dumb ask this <05-11-20, yigit> %
+
+% https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/assignments/ps1sol.pdf
+
+The question text states that $f(n)$ is a positive function.
+
+By the definition of Big $\mathcal{O}$ notation, we have;
+
+\begin{equation*}%
+    \exists ~ c > 0 \quad \text{and} \quad n_{0} \ge 0 \mid ~ 0 \le f(n) \le c \cdot g(n) \quad \forall n \ge n_{0}
+\end{equation*}
+
+For $c > 1$ and $n_{0} > 1$ we have;
+
+\begin{eqnarray*}%
+    f(n) \le f(n)^{2} \quad \forall n \ge n_{0} \\
+    g(n) = f(n)^{2} \\
+    f(n) \le c\cdot g(n) \quad \forall n \ge n_{0}
+\end{eqnarray*}
+
+\begin{info}[]
+    $f(n) + o(f(n)) = \Theta(f(n))$
+\end{info}
+
+From the definition of Big Theta notation, we are trying to prove a relation such that;
+
+\begin{equation}%
+    \label{eq:a_big_theta}
+    0 \le c_{1} \cdot f(n) \le f(n) + o(f(n)) \le c_{2} \cdot f(n)
+\end{equation}
+
+First, let's give the little-o notation to remove $o(f(n))$ from Equation~\ref{eq:a_big_theta};
+
+\begin{equation}%
+    \label{eq:a_little_o}
+    \forall ~ c > 0 \quad \exists ~ n_{0} > 0 \mid ~ 0 \le g(n) < c \cdot f(n) ~ \forall n \ge n_{0}
+\end{equation}
+
+So we can rewrite Equation~\ref{eq:a_big_theta} using Equation~\ref{eq:a_little_o};
+
+\begin{equation}%
+    \label{eq:a_rewritten}
+    c_1 \cdot f(n) \le f(n) + g(n) \le c_2 \cdot f(n)
+\end{equation}
+
+It's trivial to pick $c_1 < 1$ to deal with the left hand side of the inequality;
+
+\begin{equation*}
+    f(n) \le f(n) + g(n)
+\end{equation*}
+
+For the right hand side, we can pick $n_{0} = 1$ and $c = 1$ in the Equation~\ref{eq:a_little_o}; keeping $g(n) < f(n)$.
+
+Finally, picking $c2 > 2$ proves the conjecture.
+
+
+% 1}}} %
+
+% question b FULL TODO {{{1 %
+% TODO: haven't started yet <05-11-20, yigit> %
+
+\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.
+\end{question}
+
+\begin{info}[]
+    $f(n) = \frac{n(n+1)}{2}$
+\end{info}
+
+\begin{info}[]
+    $f(n) = \sum^{\lceil{log n}\rceil}_{k=0} \frac{n}{2^{k}}$
+\end{info}
+
+\begin{info}[]
+    $f(n) = n(log n)^{2}$
+\end{info}
+
+
+% 1}}} %
+
+\end{document}