aboutsummaryrefslogtreecommitdiffstats
path: root/main.tex
diff options
context:
space:
mode:
Diffstat (limited to 'main.tex')
-rw-r--r--main.tex350
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 @@
1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2% Lachaise Assignment
3% LaTeX Template
4% Version 1.0 (26/6/2018)
5%
6% This template originates from:
7% http://www.LaTeXTemplates.com
8%
9% Authors:
10% Marion Lachaise & François Févotte
11% Vel ([email protected])
12%
13% License:
14% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
15%
16%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
17
18\documentclass{article}
19\input{structure.tex}
20
21\title{CENG567: Homework \#1}
22\author{Yiğit Sever}
23\date{\today}
24
25%----------------------------------------------------------------------------------------
26
27\begin{document}
28
29\maketitle
30
31\section{Stable Matching}%
32\label{sec:stable_matching}
33
34% question a ✅ {{{1 %
35
36\begin{question}%
37 \label{q:1_a}
38 Use \emph{Gale-Shapley} algorithm to find a stable matching for the following set of four colleges, four students and their preference lists.
39\end{question}
40
41\begin{commandline}[Gale-Shapley algorithm, from lecture slides, edited for the context]
42
43 \begin{verbatim}
44 Initialize each person to be free.
45 while (some student is free and hasn't applied to every college) {
46 Choose such a student m
47 c = 1st college on m's list to whom m has not yet applied
48 if (c is free)
49 assign c to m for potential application (a)
50 else if (c prefers m to their current applicant m')
51 assign m and c for potential application, and m' to be free (b)
52 else
53 c rejects m (c)
54 }
55 \end{verbatim}
56
57 \end{commandline}
58
59A quick trace of the algorithm;
60
61\begin{enumerate}
62 \item $S_1$ is free;
63 \begin{enumerate}
64 \item applies to first college on their preference list $C_4$;
65 \item $C_4$ is free so it accepts and is matched with $S_1$ (a).
66 \end{enumerate}
67 \item $S_2$ is free
68 \begin{enumerate}
69 \item applies to first college on their preference list; $C_1$
70 \item $C_1$ is free so it accepts and is matched with $S_2$ (a).
71 \end{enumerate}
72 \item $S_3$ is free;
73 \begin{enumerate}
74 \item applies to first college on their preference list; $C_1$
75 \item $C_1$ rejects $S_3$ because it prefers $S_2$ to $S_3$ (c).
76 \item applies to second college on their preference list; $C_2$
77 \item $C_2$ is free so it accepts and is matched with $S_3$ (a).
78 \end{enumerate}
79 \item $S_4$ is free;
80 \begin{enumerate}
81 \item applies to first college on their preference list; $C_4$
82 \item $C_4$ rejects $S_4$ because it prefers $S_1$ to $S_4$ (c).
83 \item applies to second college on their preference list; $C_3$
84 \item $C_3$ is free so it accepts and is matched with $S_4$ (a).
85 \end{enumerate}
86 \item There are no more free students to match, algorithm terminates.
87\end{enumerate}
88
89The final matching and the answer to Question~\ref{sec:stable_matching}(a) is;
90
91\begin{align*}
92 S_1 &\rightarrow C_4 \\
93 S_2 &\rightarrow C_1 \\
94 S_3 &\rightarrow C_2 \\
95 S_4 &\rightarrow C_3
96\end{align*}
97
98% 1}}} %
99
100% question b ✅ {{{1 %
101
102\begin{question}
103 Find another stable matching with the same algorithm.
104\end{question}
105
106All 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.
107
108% 1}}} %
109
110% question c ✅ {{{1 %
111
112\begin{question}
113 Consider a pair of man $m$ and woman $w$ where $m$ has $w$ at the top of his preference list and $w$
114 has $m$ at the top of her preference list. Does it always have to be the case that the pairing $(m, w)$ exist
115 in every possible stable matching? If it is true, give a short explanation. Otherwise, give a counterexample.
116\end{question}
117
118\emph{Proof by contradiction}.
119Assume that in the resulting matching of \emph{Gale-Shapley}, we have $S'$, where $m$ is matched with $w'$ and $w$ is matched with $m'$.
120
121The 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'$.
122
123$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$.
124
125% 1}}} %
126
127% question d TODO {{{1 %
128
129\begin{question}
130 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.
131\end{question}
132
133% TODO: you abused n and now they're both fucked <05-11-20, yigit> %
134
135Arrange the preference lists such as every $m^{\text{th}}$ student arranges their preference list such as;
136
137\begin{equation}
138 \label{eq:student_prefs}
139 C_n, C_{n-1}, C_{n-2}, \dots, C_{1}
140\end{equation}
141
142Whereas every college can arrange their preference list as;
143
144\begin{equation}
145 \label{eq:college_prefs}
146 S_n, S_{n-1}, S_{n-2}, \dots, S_{1}
147\end{equation}
148
149The arrangement in (\ref{eq:college_prefs}) is not crucial since no college will be given a chance to \enquote{trade up}.
150
151Every proposer applies to colleges in decreasing order from their preference list.
152For $n=1$, $S_1$ applies to $C_1$ and the algorithm terminates in $n=1$ steps.
153For $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.
154
155% 1}}} %
156
157% question e TODO {{{1 %
158
159\begin{question}
160 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.
161\end{question}
162
163Arrange the preference lists such as every student arranges their preference \emph{exactly the same};
164
165\begin{equation}
166 \label{eq:student_prefs_2}
167 C_1, C_2, \dots, C_{n}
168\end{equation}
169
170Whereas every college should arrange their preference list as;
171
172\begin{equation}
173 \label{eq:college_prefs_2}
174 S_n, S_{n-1}, S_{n-2}, \dots, S_{1}
175\end{equation}
176
177% 1}}} %
178
179\section{Stable Matching Variation}%
180\label{sec:stable_matching_variation}
181
182% stable matching question TODO {{{1 %
183
184\begin{question}
185 Consider a Stable Matching problem with men and women.
186 Consider a woman $w$ where she prefers man $m$ to $m'$, but both $m$ and $m'$ are low on her list of preferences.
187 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'$?
188 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.
189\end{question}
190
191TRUTH
192Matching x with a (a)
193Matching y with b (a)
194z is rejected by a because x is more preffered (c)
195z is rejected by b because y is more preffered (c)
196Matching z with c (a)
197[('x', 'a'), ('y', 'b'), ('z', 'c')]
198
199LIE
200
201Matching y with b (a)
202Matching z with a (a)
203x is rejected by a because z is more preffered (c)
204Matching x with b, y is now free (b)
205Matching y with a, z is now free (b)
206z is rejected by b because x is more preffered (c)
207Matching z with c (a)
208[('x', 'b'), ('y', 'a'), ('z', 'c')]
209
210% 1}}} %
211
212\section{Asymptotics}%
213\label{sec:asymptotics}
214
215% asymptotics TODO {{{1 %
216
217\begin{question}
218 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))$.
219\end{question}
220
221
222% 1}}} %
223
224\section{Big $\mathcal{O}$ and $\Omega$}%
225\label{sec:big_o_and_omega_}
226
227% question a ALMOST DONE {{{1 %
228
229\begin{question}
230 Let $f(n)$ and $g(n)$ be asymptotically positive functions. Prove or disprove the following conjectures.
231\end{question}
232
233\begin{info}[]
234 $f(n) = \mathcal{O}(g(n))$ implies $g(n) = \mathcal{O}(f(n))$
235\end{info}
236
237From the definition of Big $\mathcal{O}$ notation given in the lecture slides;
238
239\begin{equation}%
240 \label{eq:a_bigo}
241 \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}
242\end{equation}
243
244If we rearrange the right hand side of the Proposition~\ref{eq:a_bigo};
245
246\begin{equation*}%
247 0 \le \frac{1}{c} f(n) \le g(n) \\
248\end{equation*}
249
250or simply,
251
252\begin{equation}
253 \label{eq:a_bio_rearranged}
254 0 \le c' f(n) \le g(n)
255\end{equation}
256
257By the definition of Big $\mathcal{O}$ notation, in order for $g(n) = \mathcal{O}(f(n))$ to be true,
258
259\begin{equation*}
260 \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}'
261\end{equation*}
262
263Has 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}.
264
265\begin{info}[]
266 $f(n) = \mathcal{O}((f(n))^{2})$
267\end{info}
268
269% TODO: this is dumb ask this <05-11-20, yigit> %
270
271% https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/assignments/ps1sol.pdf
272
273The question text states that $f(n)$ is a positive function.
274
275By the definition of Big $\mathcal{O}$ notation, we have;
276
277\begin{equation*}%
278 \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}
279\end{equation*}
280
281For $c > 1$ and $n_{0} > 1$ we have;
282
283\begin{eqnarray*}%
284 f(n) \le f(n)^{2} \quad \forall n \ge n_{0} \\
285 g(n) = f(n)^{2} \\
286 f(n) \le c\cdot g(n) \quad \forall n \ge n_{0}
287\end{eqnarray*}
288
289\begin{info}[]
290 $f(n) + o(f(n)) = \Theta(f(n))$
291\end{info}
292
293From the definition of Big Theta notation, we are trying to prove a relation such that;
294
295\begin{equation}%
296 \label{eq:a_big_theta}
297 0 \le c_{1} \cdot f(n) \le f(n) + o(f(n)) \le c_{2} \cdot f(n)
298\end{equation}
299
300First, let's give the little-o notation to remove $o(f(n))$ from Equation~\ref{eq:a_big_theta};
301
302\begin{equation}%
303 \label{eq:a_little_o}
304 \forall ~ c > 0 \quad \exists ~ n_{0} > 0 \mid ~ 0 \le g(n) < c \cdot f(n) ~ \forall n \ge n_{0}
305\end{equation}
306
307So we can rewrite Equation~\ref{eq:a_big_theta} using Equation~\ref{eq:a_little_o};
308
309\begin{equation}%
310 \label{eq:a_rewritten}
311 c_1 \cdot f(n) \le f(n) + g(n) \le c_2 \cdot f(n)
312\end{equation}
313
314It's trivial to pick $c_1 < 1$ to deal with the left hand side of the inequality;
315
316\begin{equation*}
317 f(n) \le f(n) + g(n)
318\end{equation*}
319
320For 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)$.
321
322Finally, picking $c2 > 2$ proves the conjecture.
323
324
325% 1}}} %
326
327% question b FULL TODO {{{1 %
328% TODO: haven't started yet <05-11-20, yigit> %
329
330\begin{question}
331 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)$.
332Otherwise, indicate that H or L do not exist.
333\end{question}
334
335\begin{info}[]
336 $f(n) = \frac{n(n+1)}{2}$
337\end{info}
338
339\begin{info}[]
340 $f(n) = \sum^{\lceil{log n}\rceil}_{k=0} \frac{n}{2^{k}}$
341\end{info}
342
343\begin{info}[]
344 $f(n) = n(log n)^{2}$
345\end{info}
346
347
348% 1}}} %
349
350\end{document}