%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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 (vel@LaTeXTemplates.com)
%
% 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 ALMOST {{{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}

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}}} %

\section{Asymptotics}%
\label{sec:asymptotics}

% asymptotics ✅ {{{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}

{\centering
    \begin{minipage}{.7\linewidth}
        \begin{algorithm}[H]
            \For(\tcc*[f]{outer loop}){$i = 2$; $i < n$; $i += 1$ }{
                \For(\tcc*[f]{inner loop}){$j=1$; $j < n$; $j * = i$}{
                    Some $\Theta(1)$ operation\;
                }
            }
            \caption{Equivalent algorithm to one given in Question 3, edited for brevity}%
            \label{alg:question_3}
\end{algorithm}
\end{minipage}
\par
}

The outer loop runs in linear time $\mathcal{O}(n)$ whereas the inner loop requires some deconstruction;

Take the first iteration of the inner loop, $i = 2$ and $j$ is initialized at $1$.

\begin{align*}%
    \label{eq:3_iterations}
    1^{\text{st}} ~ \text{iteration} &\rightarrow  j = j * i \implies  j = 2 \\
    2^{\text{nd}} ~ \text{iteration} &\rightarrow  j = 4 \\
    3^{\text{rd}} ~ \text{iteration} &\rightarrow  j = 8 \\
    \dots \\
    m^{\text{th}} ~ \text{iteration} &\rightarrow  j = i^{m} < n \\
\end{align*}

$m$ is the last iteration of the inner loop because it hit the stopping condition $i^{m} < n$.
Using the Equations above we can find the running time for the inner loop to hit stopping condition;

\begin{gather*}
    i^{m} < n \\
    m < \log_{i} n
\end{gather*}

In other words, the inner loop has a running time in the order of $\mathcal{O}(\log{n})$. By the product property of $\mathcal{O}$-notation we have the running time of $\mathcal{O}(n\log_{a}{n}), a > 1$ for the entire algorithm. The base $a$ is useful to answer the rest of the question;

We can specify a function $f$ such as $f = n \log_{b}(n)$ where $b > 1$. From the course slides;

\begin{equation*}
    \lim_{n \to \infty}\frac{n\log_{a}{n}}{n \log_{b}{n}} = c
\end{equation*}

And when the limit of two functions $f, g$ converge to some constant $c$, then $f(n) = \Theta(g(n))$.

% 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;

% TODO: this makes zero sense? <06-11-20, yigit> %

\begin{align*}%
    f(n) &\le f(n)^{2} \quad \forall n \ge n_{0} \\
    \text{take} ~ g(n) &= f(n)^{2} \\
    f(n) &\le c\cdot g(n) \quad \forall n \ge n_{0}
\end{align*}

\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 {{{1 %
% https://people.cs.umass.edu/~sheldon/teaching/cs311/hw/hw01.pdf

\begin{question}
    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}

\begin{info}[]
    $f(n) = n(\log n)^{2}$
\end{info}


% 1}}} %

\end{document}