1.1 --- a/tex/theory1_ex6.tex Sun Jun 26 19:46:12 2011 +0200
1.2 +++ b/tex/theory1_ex6.tex Mon Jun 27 01:01:33 2011 +0200
1.3 @@ -18,58 +18,82 @@
1.4 \maketitle
1.5
1.6 \section*{Exercise 6.1}
1.7 -\[\Phi(T) = |2 \cdot num - size|\]
1.8 -\[a_i = \Phi_i - \Phi_{i-1} + t_i\]
1.9 -\[a_i = |2k_i - s_i| - |2k_{i-1} - s_{i-1}| + t_i\]
1.10 +\begin{align*}
1.11 +\Phi(T) &= |2 \cdot num - size|\\
1.12 +a_i &= \Phi_i - \Phi_{i-1} + t_i\\
1.13 +a_i &= |2k_i - s_i| - |2k_{i-1} - s_{i-1}| + t_i\\
1.14 +\end{align*}
1.15 We calculate the amortized costs for the two distinct cases.
1.16
1.17 \subsection*{case 1 (no contraction required)}
1.18 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.19 -\[a_i = |2k_i - s_i| - |2k_{i-1} - s_{i-1}| + t_i\]
1.20 -\[= |2k_i - s_i| - |2k_i + 2 - s_i| + 1\]
1.21 +\begin{align*}
1.22 +a_i &= |2k_i - s_i| - |2k_{i-1} - s_{i-1}| + t_i\\
1.23 +&= |2k_i - s_i| - |2k_i + 2 - s_i| + 1\\
1.24 +\end{align*}
1.25 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.26 -\[(k_i = \frac{s_i}{2}) \implies a_i = |s_i - s_i| - |s_i - s_i + 2| + 1\]
1.27 -\[= 0 - 2 + 1 = -1\]
1.28 -
1.29 -\[(k_i = \frac{s_i}{2} - 1) \implies a_i = |s_i - 2 - s_i| - |s_i - 2 - s_i + 2| + 1\]
1.30 -\[= 2 - 0 + 1 = 3\]
1.31 -
1.32 -\[\implies -1 \leq a_i \leq 3\]
1.33 +\begin{align*}
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 +(k_i = \frac{s_i}{2} - 1) \implies a_i &= |s_i - 2 - s_i| - |s_i - 2 - s_i + 2| + 1\\
1.37 +&= 2 - 0 + 1 = 3\\
1.38 +\implies &-1 \leq a_i \leq 3\\
1.39 +\end{align*}
1.40 +\newpage
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 +\begin{align*}
1.50 +a_i &= |2k_i - s_i| - |2k_{i-1} - s_{i-1}| + t_i\\
1.51 +&= |2k_i - \frac{2}{3}s_{i-1}| - |2k_i + 2 - s_{i-1}| + t_i\\
1.52 +&= |\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.53 +&= |-2| - |-\frac{1}{3}s_{i-1}| + \frac{1}{3}s_{i-1} + 1\\
1.54 +(\text{since } s_{i-1} > 0) \implies a_i &= 2 - \frac{1}{3}s_{i-1} + \frac{1}{3}s_{i-1} + 1\\
1.55 +&= 2 + 1 = 3 \leq 3\\
1.56 +\end{align*}
1.57 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.58
1.59 \section*{Exercise 6.2}
1.60 -\[\alpha = \frac{k}{s}\]
1.61 -\[\Phi(T) =
1.62 +\begin{align*}
1.63 +\alpha &= \frac{k}{s}\\
1.64 +\Phi(T) &=
1.65 \left\{
1.66 \begin{array}{l l}
1.67 2k-s & \text{if $\alpha \geq \frac{1}{2}$}\\
1.68 \frac{s}{2}-k & \text{if $\alpha < \frac{1}{2}$}\\
1.69 -\end{array} \right.\]
1.70 +\end{array} \right.\\
1.71 +\end{align*}
1.72
1.73 We show $\sum a_i \geq \sum t_i$.
1.74 -\[a_i = \Phi_i - \Phi_{i-1} + t_i\]
1.75 -\[\implies \sum_{i=1}^{n}a_i = \sum_{i=1}^{n}\Phi_i - \Phi_{i-1} + t_i\]
1.76 -\[= \sum_{i=1}^{n}\Phi_i - \sum_{i=0}^{n-1}\Phi_i + \sum_{i=1}^{n}t_i\]
1.77 -\[= \Phi_n - \Phi_0 + \sum_{i=1}^{n}t_i\]
1.78 -
1.79 +\begin{align*}
1.80 +a_i &= \Phi_i - \Phi_{i-1} + t_i\\
1.81 +\implies \sum_{i=1}^{n}a_i &= \sum_{i=1}^{n}\Phi_i - \Phi_{i-1} + t_i\\
1.82 +&= \sum_{i=1}^{n}\Phi_i - \sum_{i=0}^{n-1}\Phi_i + \sum_{i=1}^{n}t_i\\
1.83 +&= \Phi_n - \Phi_0 + \sum_{i=1}^{n}t_i\\
1.84 +\end{align*}
1.85 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.86 \[\implies \Phi_n - \Phi_0 + \sum_{i=1}^{n}t_i \geq \sum t_i\]\qed
1.87
1.88 \section*{Exercise 6.3}
1.89 -We show
1.90 -\[\sum_{k=2}^{n-1}k\,lg\,k \leq \frac{1}{2}n^2\,lg\,n - \frac{1}{8}n^2\]
1.91 -\[\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.92 -\[\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.93 -\[= 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.94 -\[= (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.95 -\[= 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.96 -\[= lg\,n \frac{(n-1)(n-2)}{2} - \]
1.97 +We show $\sum_{k=2}^{n-1}k\,lg\,k \leq \frac{1}{2}n^2\,lg\,n - \frac{1}{8}n^2$.
1.98 +\begin{align*}
1.99 +\sum_{k=2}^{n-1}k\,lg\,k &\leq \frac{1}{2}n^2\,lg\,n - \frac{1}{8}n^2\\
1.100 +\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.101 +\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\\
1.102 +&= 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.103 +&= (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.104 +&= 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.105 +&= lg\,n \sum_{k=2}^{n-1}k - \sum_{k=2}^{\lceil \frac{n}{2} \rceil - 1}k\\
1.106 +&\leq lg\,n \frac{(n-1)(n-2)}{2} - \frac{(\frac{n}{2} - 1)(\frac{n}{2} - 2)}{2}\\
1.107 +&= \frac{1}{2}lg\,n (n^2 - 3n + 2) - \frac{1}{2}(\frac{n^2}{4} - n - \frac{n}{2} + 2)\\
1.108 +&= \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)\\
1.109 +&= \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\\
1.110 +&= \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\\
1.111 +&\leq \frac{1}{2}n^2\,lg\,n - \frac{1}{8}n^2 + lg\,n - \frac{3}{2}n + \frac{3}{4}n - 1\\
1.112 +&= \frac{1}{2}n^2\,lg\,n - \frac{1}{8}n^2 + lg\,n - \frac{3}{4}n - 1\\
1.113 +\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\\
1.114 +\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\\
1.115 +\iff &lg\,n - \frac{3}{4}n - 1 \leq 0\\
1.116 +\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\\
1.117 +\end{align*}
1.118 +\qed
1.119 \end{document}