sawine@7
|
1 |
\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
|
sawine@7
|
2 |
\usepackage{graphicx}
|
sawine@7
|
3 |
%\usepackage[latin1]{inputenc}
|
sawine@7
|
4 |
\usepackage{amsmath, amsthm, amssymb}
|
sawine@7
|
5 |
\usepackage{typearea}
|
sawine@7
|
6 |
\usepackage{algorithm}
|
sawine@7
|
7 |
\usepackage{algorithmic}
|
sawine@7
|
8 |
\usepackage{fullpage}
|
sawine@7
|
9 |
\usepackage{mathtools}
|
sawine@7
|
10 |
\usepackage[all]{xy}
|
sawine@7
|
11 |
\title{Theory I, Sheet 6 Solution}
|
sawine@7
|
12 |
\author{Eugen Sawin}
|
sawine@7
|
13 |
\renewcommand{\familydefault}{\sfdefault}
|
sawine@7
|
14 |
\include{pythonlisting}
|
sawine@7
|
15 |
|
sawine@7
|
16 |
\pagestyle{empty}
|
sawine@7
|
17 |
\begin{document}
|
sawine@7
|
18 |
\maketitle
|
sawine@7
|
19 |
|
sawine@7
|
20 |
\section*{Exercise 6.1}
|
sawine@8
|
21 |
\begin{align*}
|
sawine@8
|
22 |
\Phi(T) &= |2 \cdot num - size|\\
|
sawine@8
|
23 |
a_i &= \Phi_i - \Phi_{i-1} + t_i\\
|
sawine@8
|
24 |
a_i &= |2k_i - s_i| - |2k_{i-1} - s_{i-1}| + t_i\\
|
sawine@8
|
25 |
\end{align*}
|
sawine@7
|
26 |
We calculate the amortized costs for the two distinct cases.
|
sawine@7
|
27 |
|
sawine@7
|
28 |
\subsection*{case 1 (no contraction required)}
|
sawine@7
|
29 |
Since there was no contraction we know that $s_i = s_{i-1}$ and it follows that $\frac{1}{3}s_i \leq k_i \leq s_i - 1$. Since we have deleted an element we know that $k_i = k_{i-1} - 1$. Because we have only removed an element it follows that $t_i = 1$. We reduce the formula using these substitutions.
|
sawine@8
|
30 |
\begin{align*}
|
sawine@8
|
31 |
a_i &= |2k_i - s_i| - |2k_{i-1} - s_{i-1}| + t_i\\
|
sawine@8
|
32 |
&= |2k_i - s_i| - |2k_i + 2 - s_i| + 1\\
|
sawine@8
|
33 |
\end{align*}
|
sawine@7
|
34 |
Now we look for the minimum and maximum value of the above formula. We choose the obvious values for $k_i$ which are within valid range.
|
sawine@8
|
35 |
\begin{align*}
|
sawine@8
|
36 |
(k_i = \frac{s_i}{2}) \implies a_i &= |s_i - s_i| - |s_i - s_i + 2| + 1\\
|
sawine@8
|
37 |
&= 0 - 2 + 1 = -1\\
|
sawine@8
|
38 |
(k_i = \frac{s_i}{2} - 1) \implies a_i &= |s_i - 2 - s_i| - |s_i - 2 - s_i + 2| + 1\\
|
sawine@8
|
39 |
&= 2 - 0 + 1 = 3\\
|
sawine@8
|
40 |
\implies &-1 \leq a_i \leq 3\\
|
sawine@8
|
41 |
\end{align*}
|
sawine@8
|
42 |
\newpage
|
sawine@7
|
43 |
\subsection*{case 2 (contraction required)}
|
sawine@7
|
44 |
Since there was a contraction we know that $s_i = \frac{2}{3}s_{i-1}$ and it follows that $k_i = \frac{1}{3}s_{i-1} - 1$. Since we have deleted an element we know that $k_i = k_{i-1} - 1$. Because we have removed an element and additionally copied all previously contained elements it follows that $t_i = \frac{1}{3}s_{i-1} + 1$. We reduce the formula again using these substitutions.
|
sawine@8
|
45 |
\begin{align*}
|
sawine@8
|
46 |
a_i &= |2k_i - s_i| - |2k_{i-1} - s_{i-1}| + t_i\\
|
sawine@8
|
47 |
&= |2k_i - \frac{2}{3}s_{i-1}| - |2k_i + 2 - s_{i-1}| + t_i\\
|
sawine@8
|
48 |
&= |\frac{2}{3}s_{i-1} - 2 - \frac{2}{3}s_{i-1}| - |\frac{2}{3}s_{i-1} - 2 + 2 - s_{i-1}| + \frac{1}{3}s_{i-1} + 1\\
|
sawine@8
|
49 |
&= |-2| - |-\frac{1}{3}s_{i-1}| + \frac{1}{3}s_{i-1} + 1\\
|
sawine@8
|
50 |
(\text{since } s_{i-1} > 0) \implies a_i &= 2 - \frac{1}{3}s_{i-1} + \frac{1}{3}s_{i-1} + 1\\
|
sawine@8
|
51 |
&= 2 + 1 = 3 \leq 3\\
|
sawine@8
|
52 |
\end{align*}
|
sawine@7
|
53 |
By calculating the amortized costs for both Table-Delete cases, we have have shown that the amortized costs are bounded by constant 3. \qed
|
sawine@7
|
54 |
|
sawine@7
|
55 |
\section*{Exercise 6.2}
|
sawine@8
|
56 |
\begin{align*}
|
sawine@8
|
57 |
\alpha &= \frac{k}{s}\\
|
sawine@8
|
58 |
\Phi(T) &=
|
sawine@7
|
59 |
\left\{
|
sawine@7
|
60 |
\begin{array}{l l}
|
sawine@7
|
61 |
2k-s & \text{if $\alpha \geq \frac{1}{2}$}\\
|
sawine@7
|
62 |
\frac{s}{2}-k & \text{if $\alpha < \frac{1}{2}$}\\
|
sawine@8
|
63 |
\end{array} \right.\\
|
sawine@8
|
64 |
\end{align*}
|
sawine@7
|
65 |
|
sawine@7
|
66 |
We show $\sum a_i \geq \sum t_i$.
|
sawine@8
|
67 |
\begin{align*}
|
sawine@8
|
68 |
a_i &= \Phi_i - \Phi_{i-1} + t_i\\
|
sawine@8
|
69 |
\implies \sum_{i=1}^{n}a_i &= \sum_{i=1}^{n}\Phi_i - \Phi_{i-1} + t_i\\
|
sawine@8
|
70 |
&= \sum_{i=1}^{n}\Phi_i - \sum_{i=0}^{n-1}\Phi_i + \sum_{i=1}^{n}t_i\\
|
sawine@8
|
71 |
&= \Phi_n - \Phi_0 + \sum_{i=1}^{n}t_i\\
|
sawine@8
|
72 |
\end{align*}
|
sawine@9
|
73 |
By definition we know that $\Phi_0 = -1$ and since $2k-s \geq 0$ for $\alpha \geq \frac{1}{2}$ and $\frac{s}{2}-k \geq 0$ for $\alpha < \frac{1}{2}$ it follows that $\Phi_n - \Phi_0 \geq 0$.
|
sawine@7
|
74 |
\[\implies \Phi_n - \Phi_0 + \sum_{i=1}^{n}t_i \geq \sum t_i\]\qed
|
sawine@7
|
75 |
|
sawine@7
|
76 |
\section*{Exercise 6.3}
|
sawine@8
|
77 |
We show $\sum_{k=2}^{n-1}k\,lg\,k \leq \frac{1}{2}n^2\,lg\,n - \frac{1}{8}n^2$.
|
sawine@8
|
78 |
\begin{align*}
|
sawine@8
|
79 |
\sum_{k=2}^{n-1}k\,lg\,k &\leq \frac{1}{2}n^2\,lg\,n - \frac{1}{8}n^2\\
|
sawine@8
|
80 |
\sum_{k=2}^{n-1}k\,lg\,k &= \sum_{k=2}^{\lceil \frac{n}{2} \rceil - 1}k\,lg\,k\ + \sum_{k=\lceil \frac{n}{2} \rceil}^{n-1}k\,lg\,k\\
|
sawine@8
|
81 |
\sum_{k=2}^{n-1}k\,lg\,k &\leq \sum_{k=2}^{\lceil \frac{n}{2} \rceil - 1}k\,lg\,\lceil\frac{n}{2}\rceil + \sum_{k=\lceil \frac{n}{2} \rceil}^{n-1}k\,lg\,n\\
|
sawine@8
|
82 |
&= lg\,\lceil \frac{n}{2} \rceil \sum_{k=2}^{\lceil \frac{n}{2} \rceil - 1}k + lg\,n \sum_{k=\lceil \frac{n}{2} \rceil}^{n-1}k\\
|
sawine@8
|
83 |
&= (lg\,n - lg\,2) \sum_{k=2}^{\lceil \frac{n}{2} \rceil - 1}k + lg\,n \sum_{k=\lceil \frac{n}{2} \rceil}^{n-1}k\\
|
sawine@8
|
84 |
&= lg\,n \sum_{k=2}^{\lceil \frac{n}{2} \rceil - 1}k - \sum_{k=2}^{\lceil \frac{n}{2} \rceil - 1}k + lg\,n \sum_{k=\lceil \frac{n}{2} \rceil}^{n-1}k\\
|
sawine@8
|
85 |
&= lg\,n \sum_{k=2}^{n-1}k - \sum_{k=2}^{\lceil \frac{n}{2} \rceil - 1}k\\
|
sawine@8
|
86 |
&\leq lg\,n \frac{(n-1)(n-2)}{2} - \frac{(\frac{n}{2} - 1)(\frac{n}{2} - 2)}{2}\\
|
sawine@8
|
87 |
&= \frac{1}{2}lg\,n (n^2 - 3n + 2) - \frac{1}{2}(\frac{n^2}{4} - n - \frac{n}{2} + 2)\\
|
sawine@8
|
88 |
&= \frac{1}{2}n^2\,lg\,n - \frac{3}{2}n\,lg\,n + lg\,n - \frac{1}{2}(\frac{n^2}{4} - n - \frac{n}{2} + 2)\\
|
sawine@8
|
89 |
&= \frac{1}{2}n^2\,lg\,n - \frac{3}{2}n\,lg\,n + lg\,n - \frac{1}{8}n^2 + \frac{n}{2} + \frac{n}{4} - 1\\
|
sawine@8
|
90 |
&= \frac{1}{2}n^2\,lg\,n - \frac{1}{8}n^2 + lg\,n - \frac{3}{2}n\,lg\,n + \frac{3}{4}n - 1\\
|
sawine@8
|
91 |
&\leq \frac{1}{2}n^2\,lg\,n - \frac{1}{8}n^2 + lg\,n - \frac{3}{2}n + \frac{3}{4}n - 1\\
|
sawine@8
|
92 |
&= \frac{1}{2}n^2\,lg\,n - \frac{1}{8}n^2 + lg\,n - \frac{3}{4}n - 1\\
|
sawine@8
|
93 |
\implies \sum_{k=2}^{n-1}k\,lg\,k &\leq \frac{1}{2}n^2\,lg\,n - \frac{1}{8}n^2 + lg\,n - \frac{3}{4}n - 1 \leq \frac{1}{2}n^2\,lg\,n - \frac{1}{8}n^2\\
|
sawine@8
|
94 |
\implies &\frac{1}{2}n^2\,lg\,n - \frac{1}{8}n^2 + lg\,n - \frac{3}{4}n - 1 \leq \frac{1}{2}n^2\,lg\,n - \frac{1}{8}n^2\\
|
sawine@8
|
95 |
\iff &lg\,n - \frac{3}{4}n - 1 \leq 0\\
|
sawine@8
|
96 |
\text{since } \forall{n \in \mathbb{N}}:\, lg\,n - \frac{3}{4}n \leq 0 &\implies \, lg\,n - \frac{3}{4}n - 1 \leq -1 \leq 0\\
|
sawine@8
|
97 |
\end{align*}
|
sawine@8
|
98 |
\qed
|
sawine@7
|
99 |
\end{document}
|