From 613bf0c79519036cff1cd04afa323e9fc37ac9a2 Mon Sep 17 00:00:00 2001 From: Yigit Sever Date: Fri, 6 Nov 2020 05:22:38 +0300 Subject: End commit for the thursday session 3 hours worth of work, two days till deadline --- main.tex | 138 ++++++++++++++++++++++++++++++++++++++++++++++++---------- structure.tex | 16 +++---- 2 files changed, 121 insertions(+), 33 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} diff --git a/structure.tex b/structure.tex index e536c85..ae1765b 100644 --- a/structure.tex +++ b/structure.tex @@ -19,15 +19,20 @@ % PACKAGES AND OTHER DOCUMENT CONFIGURATIONS %---------------------------------------------------------------------------------------- +\usepackage[utf8]{inputenc} % Required for inputting international characters +\usepackage[T1]{fontenc} % Output font encoding for international characters +\usepackage{csquotes} \usepackage{amsmath,amsfonts} % Math packages \usepackage{enumerate} % Custom item numbers for enumerations \usepackage[ruled]{algorithm2e} % Algorithms +\usepackage[makeroom]{cancel} % \usepackage{algorithm} % \usepackage[noend]{algpseudocode} \usepackage[framemethod=tikz]{mdframed} % Allows defining custom boxed/framed environments \usepackage{listings} % File listings, with syntax highlighting \usepackage[super]{nth} -\usepackage{csquotes} +\usepackage{caption} +\usepackage{tikz} \lstset{ basicstyle=\ttfamily, % Typeset listings in monospace font @@ -51,15 +56,6 @@ % 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 %---------------------------------------------------------------------------------------- -- cgit v1.2.3-70-g09d2