1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/tex/theory1_ex6.tex Sun Jun 26 19:46:12 2011 +0200
1.3 @@ -0,0 +1,75 @@
1.4 +\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
1.5 +\usepackage{graphicx}
1.6 +%\usepackage[latin1]{inputenc}
1.7 +\usepackage{amsmath, amsthm, amssymb}
1.8 +\usepackage{typearea}
1.9 +\usepackage{algorithm}
1.10 +\usepackage{algorithmic}
1.11 +\usepackage{fullpage}
1.12 +\usepackage{mathtools}
1.13 +\usepackage[all]{xy}
1.14 +\title{Theory I, Sheet 6 Solution}
1.15 +\author{Eugen Sawin}
1.16 +\renewcommand{\familydefault}{\sfdefault}
1.17 +\include{pythonlisting}
1.18 +
1.19 +\pagestyle{empty}
1.20 +\begin{document}
1.21 +\maketitle
1.22 +
1.23 +\section*{Exercise 6.1}
1.24 +\[\Phi(T) = |2 \cdot num - size|\]
1.25 +\[a_i = \Phi_i - \Phi_{i-1} + t_i\]
1.26 +\[a_i = |2k_i - s_i| - |2k_{i-1} - s_{i-1}| + t_i\]
1.27 +We calculate the amortized costs for the two distinct cases.
1.28 +
1.29 +\subsection*{case 1 (no contraction required)}
1.30 +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.
1.31 +\[a_i = |2k_i - s_i| - |2k_{i-1} - s_{i-1}| + t_i\]
1.32 +\[= |2k_i - s_i| - |2k_i + 2 - s_i| + 1\]
1.33 +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.
1.34 +\[(k_i = \frac{s_i}{2}) \implies a_i = |s_i - s_i| - |s_i - s_i + 2| + 1\]
1.35 +\[= 0 - 2 + 1 = -1\]
1.36 +
1.37 +\[(k_i = \frac{s_i}{2} - 1) \implies a_i = |s_i - 2 - s_i| - |s_i - 2 - s_i + 2| + 1\]
1.38 +\[= 2 - 0 + 1 = 3\]
1.39 +
1.40 +\[\implies -1 \leq a_i \leq 3\]
1.41 +\subsection*{case 2 (contraction required)}
1.42 +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.
1.43 +\[a_i = |2k_i - s_i| - |2k_{i-1} - s_{i-1}| + t_i\]
1.44 +\[= |2k_i - \frac{2}{3}s_{i-1}| - |2k_i + 2 - s_{i-1}| + t_i\]
1.45 +\[= |\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\]
1.46 +\[= |-2| - |-\frac{1}{3}s_{i-1}| + \frac{1}{3}s_{i-1} + 1\]
1.47 +\[(\text{since } s_{i-1} > 0) \implies a_i = 2 - \frac{1}{3}s_{i-1} + \frac{1}{3}s_{i-1} + 1\]
1.48 +\[= 2 + 1 = 3 \leq 3\]
1.49 +By calculating the amortized costs for both Table-Delete cases, we have have shown that the amortized costs are bounded by constant 3. \qed
1.50 +
1.51 +\section*{Exercise 6.2}
1.52 +\[\alpha = \frac{k}{s}\]
1.53 +\[\Phi(T) =
1.54 +\left\{
1.55 +\begin{array}{l l}
1.56 + 2k-s & \text{if $\alpha \geq \frac{1}{2}$}\\
1.57 + \frac{s}{2}-k & \text{if $\alpha < \frac{1}{2}$}\\
1.58 +\end{array} \right.\]
1.59 +
1.60 +We show $\sum a_i \geq \sum t_i$.
1.61 +\[a_i = \Phi_i - \Phi_{i-1} + t_i\]
1.62 +\[\implies \sum_{i=1}^{n}a_i = \sum_{i=1}^{n}\Phi_i - \Phi_{i-1} + t_i\]
1.63 +\[= \sum_{i=1}^{n}\Phi_i - \sum_{i=0}^{n-1}\Phi_i + \sum_{i=1}^{n}t_i\]
1.64 +\[= \Phi_n - \Phi_0 + \sum_{i=1}^{n}t_i\]
1.65 +
1.66 +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 >= 0$.
1.67 +\[\implies \Phi_n - \Phi_0 + \sum_{i=1}^{n}t_i \geq \sum t_i\]\qed
1.68 +
1.69 +\section*{Exercise 6.3}
1.70 +We show
1.71 +\[\sum_{k=2}^{n-1}k\,lg\,k \leq \frac{1}{2}n^2\,lg\,n - \frac{1}{8}n^2\]
1.72 +\[\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\]
1.73 +\[\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\]
1.74 +\[= 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\]
1.75 +\[= (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\]
1.76 +\[= 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\]
1.77 +\[= lg\,n \frac{(n-1)(n-2)}{2} - \]
1.78 +\end{document}