Initial commit

2 files changed, 577 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}
diff --git a/structure.tex b/structure.tex
new file mode 100644
index 0000000..62deff6
--- /dev/null
+++ b/structure.tex
@@ -0,0 +1,227 @@
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% Lachaise Assignment
+% Structure Specification File
+% 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/)
+%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%----------------------------------------------------------------------------------------
+%       PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
+%----------------------------------------------------------------------------------------
+
+\usepackage{amsmath,amsfonts} % Math packages
+\usepackage{enumerate} % Custom item numbers for enumerations
+\usepackage[ruled]{algorithm2e} % Algorithms
+\usepackage[framemethod=tikz]{mdframed} % Allows defining custom boxed/framed environments
+\usepackage{listings} % File listings, with syntax highlighting
+\usepackage[super]{nth}
+\usepackage{csquotes}
+
+\lstset{
+        basicstyle=\ttfamily, % Typeset listings in monospace font
+}
+
+%----------------------------------------------------------------------------------------
+%       DOCUMENT MARGINS
+%----------------------------------------------------------------------------------------
+
+\usepackage{geometry} % Required for adjusting page dimensions and margins
+
+\geometry{
+        paper=a4paper, % Paper size, change to letterpaper for US letter size
+        top=2.5cm, % Top margin
+        bottom=3cm, % Bottom margin
+        left=2.5cm, % Left margin
+        right=2.5cm, % Right margin
+        headheight=14pt, % Header height
+        footskip=1.5cm, % Space from the bottom margin to the baseline of the footer
+        headsep=1.2cm, % Space from the top margin to the baseline of the header
+        % showframe, % Uncomment to show how the type block is set on the page
+}
+
+%----------------------------------------------------------------------------------------
+%       FONTS
+%----------------------------------------------------------------------------------------
+
+\usepackage[utf8]{inputenc} % Required for inputting international characters
+\usepackage[T1]{fontenc} % Output font encoding for international characters
+
+% \usepackage{XCharter} % Use the XCharter fonts
+
+%----------------------------------------------------------------------------------------
+%       COMMAND LINE ENVIRONMENT
+%----------------------------------------------------------------------------------------
+
+% Usage:
+% \begin{commandline}
+%       \begin{verbatim}
+%               $ ls
+%
+%               Applications    Desktop ...
+%       \end{verbatim}
+% \end{commandline}
+
+\mdfdefinestyle{commandline}{
+        leftmargin=10pt,
+        rightmargin=10pt,
+        innerleftmargin=15pt,
+        middlelinecolor=black!50!white,
+        middlelinewidth=2pt,
+        frametitlerule=false,
+        backgroundcolor=black!5!white,
+        frametitle={\ttfamily\cmdname},
+        frametitlefont={\normalfont\sffamily\color{white}\hspace{-1em}},
+        frametitlebackgroundcolor=black!50!white,
+        nobreak,
+}
+
+% Define a custom environment for command-line snapshots
+\newenvironment{commandline}[1][Cmd]{
+        \medskip
+        \newcommand{\cmdname}{#1}
+        \begin{mdframed}[style=commandline]
+}{
+        \end{mdframed}
+        \medskip
+}
+
+%----------------------------------------------------------------------------------------
+%       FILE CONTENTS ENVIRONMENT
+%----------------------------------------------------------------------------------------
+
+% Usage:
+% \begin{file}[optional filename, defaults to "File"]
+%       File contents, for example, with a listings environment
+% \end{file}
+
+\mdfdefinestyle{file}{
+        innertopmargin=1.6\baselineskip,
+        innerbottommargin=0.8\baselineskip,
+        topline=false, bottomline=false,
+        leftline=false, rightline=false,
+        leftmargin=2cm,
+        rightmargin=2cm,
+        singleextra={%
+                \draw[fill=black!10!white](P)++(0,-1.2em)rectangle(P-|O);
+                \node[anchor=north west]
+                at(P-|O){\ttfamily\mdfilename};
+                %
+                \def\l{3em}
+                \draw(O-|P)++(-\l,0)--++(\l,\l)--(P)--(P-|O)--(O)--cycle;
+                \draw(O-|P)++(-\l,0)--++(0,\l)--++(\l,0);
+        },
+        nobreak,
+}
+
+% Define a custom environment for file contents
+\newenvironment{file}[1][File]{ % Set the default filename to "File"
+        \medskip
+        \newcommand{\mdfilename}{#1}
+        \begin{mdframed}[style=file]
+}{
+        \end{mdframed}
+        \medskip
+}
+
+%----------------------------------------------------------------------------------------
+%       NUMBERED QUESTIONS ENVIRONMENT
+%----------------------------------------------------------------------------------------
+
+% Usage:
+% \begin{question}[optional title]
+%       Question contents
+% \end{question}
+
+\mdfdefinestyle{question}{
+        innertopmargin=1.2\baselineskip,
+        innerbottommargin=0.8\baselineskip,
+        roundcorner=5pt,
+        nobreak,
+        singleextra={%
+                \draw(P-|O)node[xshift=1em,anchor=west,fill=white,draw,rounded corners=5pt]{%
+                Question (\alph{Question})\questionTitle};
+        },
+}
+
+\newcounter{Question}[section] % Stores the current question number that gets iterated with each new question TODO reset after each section
+
+% Define a custom environment for numbered questions
+\newenvironment{question}[1][\unskip]{
+        \bigskip
+        \stepcounter{Question}
+        \newcommand{\questionTitle}{~#1}
+        \begin{mdframed}[style=question]
+}{
+        \end{mdframed}
+        \medskip
+}
+
+%----------------------------------------------------------------------------------------
+%       WARNING TEXT ENVIRONMENT
+%----------------------------------------------------------------------------------------
+
+% Usage:
+% \begin{warn}[optional title, defaults to "Warning:"]
+%       Contents
+% \end{warn}
+
+\mdfdefinestyle{warning}{
+        topline=false, bottomline=false,
+        leftline=false, rightline=false,
+        nobreak,
+        singleextra={%
+                \draw(P-|O)++(-0.5em,0)node(tmp1){};
+                \draw(P-|O)++(0.5em,0)node(tmp2){};
+                \fill[black,rotate around={45:(P-|O)}](tmp1)rectangle(tmp2);
+                \node at(P-|O){\color{white}\scriptsize\bf !};
+                \draw[very thick](P-|O)++(0,-1em)--(O);%--(O-|P);
+        }
+}
+
+% Define a custom environment for warning text
+\newenvironment{warn}[1][Warning:]{ % Set the default warning to "Warning:"
+        \medskip
+        \begin{mdframed}[style=warning]
+                \noindent{\textbf{#1}}
+}{
+        \end{mdframed}
+}
+
+%----------------------------------------------------------------------------------------
+%       INFORMATION ENVIRONMENT
+%----------------------------------------------------------------------------------------
+
+% Usage:
+% \begin{info}[optional title, defaults to "Info:"]
+%       contents
+%       \end{info}
+
+\mdfdefinestyle{info}{%
+        topline=false, bottomline=false,
+        leftline=false, rightline=false,
+        nobreak,
+        singleextra={%
+                \fill[black](P-|O)circle[radius=0.6em];
+                \node at(P-|O){\color{white}\scriptsize\bf Q};
+                \draw[very thick](P-|O)++(0,-0.8em)--(O);%--(O-|P);
+        }
+}
+
+% Define a custom environment for information
+\newenvironment{info}[1][Info:]{ % Set the default title to "Info:"
+        \medskip
+        \begin{mdframed}[style=info]
+                \noindent{\textbf{#1}}
+}{
+        \end{mdframed}
+}