gistfile1.md

{ "metadata": { "name": "Algo HW3" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": "4-1" }, { "cell_type": "markdown", "metadata": {}, "source": "a. $T(n)=2T(n/2)+n^4$
\nLet $a=2$, $b=2$, $\epsilon=3$ and $f(n)=n^4=n^{\log_{b}{a}+\epsilon}$. We have $T(n)=a T(n/b)+f(n)$. And since $af(\frac{n}{b}) = 2 (\frac{n}{2})^4=\frac{1}{8}n^4=\frac{1}{8}f(n)$, we can apply case 3 of Master Theorem.
Therefore, $T(n)=\Theta(f(n))=\Theta(n^4)$." }, { "cell_type": "markdown", "metadata": {}, "source": "b. $T(n)=T(7n/10)+n$
\nLet $a=1$, $b=\frac{10}{7}$, $\epsilon=1$ and $f(n)=n=n^{\log_{b}{a}+\epsilon}$. We have $T(n)=a T(n/b)+f(n)$. And since $af(\frac{n}{b}) =\frac{7n}{10}=\frac{7}{10}f(n)$, we can apply case 3 of Master Theorem.
Therefore, $T(n)=\Theta(f(n))=\Theta(n)$." }, { "cell_type": "markdown", "metadata": {}, "source": "c. $T(n)=16T(n/4)+n^2$
\nLet $a=16$, $b=4$ and $f(n)=n^2=n^{\log_{b}{a}}$. We have $T(n)=a T(n/b)+f(n)$. We can apply case 2 of Master Theorem. Therefore, $T(n)=\Theta(n^{\log_{b}{a}} \lg{n}) = \Theta(n^2 \lg{n})$." }, { "cell_type": "markdown", "metadata": {}, "source": "d. $T(n)=7T(n/3)+n^2$
\nLet $a=7$, $b=3$, $\epsilon=2 - \log_{3}{7} > 0$ and $f(n)=n^2=n^{\log_{b}{a}+\epsilon}$. We have $T(n)=a T(n/b)+f(n)$. And since $af(\frac{n}{b}) =7 (\frac{n}{3})^2=\frac{7}{9}f(n)$, we can apply case 3 of Master Theorem. Therefore, $T(n)=\Theta(f(n))=\Theta(n^2)$." }, { "cell_type": "markdown", "metadata": {}, "source": "e. $T(n)=7T(n/2)+n^2$
\nLet $a=7$, $b=2$, $\epsilon=\log_{2}{7}-2 > 0$ and $f(n)=n^2=n^{\log_{b}{a}-\epsilon}$. We have $T(n)=a T(n/b)+f(n)$. We can apply case 1 of Master Theorem.
Therefore, $T(n)=\Theta(n^{\log_{b}{a}})=\Theta(n^{\lg{7}})$." }, { "cell_type": "markdown", "metadata": {}, "source": "f. $T(n)=2T(n/4)+\sqrt{n}$
\nLet $a=2$, $b=4$ and $f(n)=\sqrt{n}=n^{\log_{b}{a}}$. We have $T(n)=a T(n/b)+f(n)$. We can apply case 2 of Master Theorem. Therefore, $T(n)=\Theta(n^{\log_{b}{a}} \lg{n})=\Theta(\sqrt{n} \lg{n})$." }, { "cell_type": "markdown", "metadata": {}, "source": "g. $T(n)=T(n-2)+n^2$
\nAssume T(n) is constant if $n \leq 2$. Then for large enough $n$ be given, with some $\alpha = 1$ or $2$, we have $$T(n) = T(n-2) + n^2 = ... = T(\alpha) + \sum_{k=0}^{\lfloor \frac{n}{2} \rfloor -1}{(n-2k)^2} = T(\alpha) + \sum_{k=0}^{\lfloor \frac{n}{2} \rfloor -1}{(n^2 -4nk + 4k^2)}$$\n$= T(\alpha) + (\lfloor \frac{n}{2} \rfloor -1)n^2 + (-4n) \cdot \frac{\lfloor \frac{n}{2} \rfloor(\lfloor \frac{n}{2} \rfloor -1)}{2} + 4 \frac{(\lfloor \frac{n}{2} \rfloor -1)\lfloor \frac{n}{2} \rfloor(2\lfloor \frac{n}{2} \rfloor -1)}{6}$
\n$= T(\alpha) + (\lfloor \frac{n}{2} \rfloor -1)[n^2 - 2n\lfloor \frac{n}{2} \rfloor + \frac{2}{3} \lfloor \frac{n}{2} \rfloor(2\lfloor \frac{n}{2} \rfloor -1)] \dots ()$
\n$\implies \frac{n^3}{48} = (\frac{n}{4})[ \frac{2}{3}(\frac{n}{4})(\frac{n}{2})] \leq (\frac{n}{2} -2)[n^2 - 2n \frac{n}{2} + \frac{2}{3}(\frac{n}{2}-1)(n-3)] \leq () \leq (\frac{n}{2})[n^2 - 2n \frac{n}{4} + \frac{2}{3} \frac{n}{2} (2 \cdot \frac{n}{2})] \leq n^3$
\n(Because $T(\alpha)$ is a constant, it can be dropped when we are estimating upperbound by taking $n$ large enough.)
\nTherefore, we can conclude that $T(n) = \Omega(n^3)$ and $T(n) = O(n^3)$, hence $T(n) = \Theta(n^3)$." }, { "cell_type": "markdown", "metadata": {}, "source": "
4-3" }, { "cell_type": "markdown", "metadata": {}, "source": "a. $T(n)=4T(n/3)+n \lg{n}$
\nLet $a=4$, $b=3$ and $f(n)=n \lg{n}=O(n^{\log_{b}{a} - \epsilon})$ with $0< \epsilon < -1 + \log_{3}{4}$. (Note that $n\lg^k n = O(n^{k+\eta})$ for all $k \in \mathbb{N}$, $\eta > 0$.)
Then we have $T(n)=a T(n/b)+f(n)$, and we can apply case 1 of Master Theorem. Therefore, $T(n)=\Theta(n^{\log_{b}{a}})=\Theta(n^{\log_{3}{4}})$." }, { "cell_type": "markdown", "metadata": {}, "source": "j. $T(n)=\sqrt{n}T(\sqrt{n})+n$
\nAssume that $T(n)$ is constant if $n \leq N$ for some constant $N>1$. Let $n$ be given (and large enough), $m$ be the smallest natural number s.t. $T(n^{2^{-m}})$ is constant.
\nPut $b = n^{2^{-m}}$, then $1 < b \leq N$ and $m = \lg \log_{b}{n}$.
\n$T(n)=\sqrt{n} T(\sqrt{n}) + n$
\n$ = b^{2^{m-1}}T(b^{2^{m-1}}) + b^{2^{m}}$
\n$= b^{2^{m-1}} [ b^{2^{m-2}}T(b^{2^{m-2}}) + b^{2^{m-1}} ] + b^{2^{m}}$
\n$= \dots = T(b)\prod_{k=1}^{m}{b^{2^{m-k}}} + \sum_{k=1}^{m}{\prod_{h=1}^{k}(b^{2^{m-h}} b^{2^{m-k}})} + b^{2^{m}}$
\n$= T(b)b^{\sum_{k=1}^{m}{2^{m-k}}} + \sum_{k=1}^{m}{b^{2^{m-k}} b^{\sum_{h=1}^{k}{2^{m-h}}}} + b^{2^{m}}$
\n$= T(b)b^{2^{m}-1} + \sum_{k=1}^{m}{b^{2^{m-k}} b^{2^{m}-2^{m-k}}} + b^{2^{m}}$
\n$= T(b)b^{2^{m}-1} + m b^{2^{m}} + b^{2^{m}}$
\n$= T(b) \sqrt{n} + n \lg \log_{b}{n} + n$
\n$= \Theta(n \lg \lg n)$
\n" }, { "cell_type": "markdown", "metadata": {}, "source": "
4-5" }, { "cell_type": "markdown", "metadata": {}, "source": "<style type="text/css">\n.tg {border-collapse:collapse;border-spacing:0;}\n.tg td{font-family:Arial, sans-serif;font-size:14px;padding:10px 5px;border-style:solid;border-width:1px;overflow:hidden;word-break:normal;}\n.tg th{font-family:Arial, sans-serif;font-size:14px;font-weight:normal;padding:10px 5px;border-style:solid;border-width:1px;overflow:hidden;word-break:normal;}\n.tg .tg-s6z2{text-align:center}\n</style>\n<table class="tg">\n \n <th class="tg-s6z2">Result\n <th class="tg-s6z2">$\alpha$ says $\beta$ is\n <th class="tg-s6z2">$\beta$ says $\alpha$ is\n <th class="tg-s6z2">Actual state of ($\alpha$,$\beta$)\n \n \n <td class="tg-s6z2">1\n <td class="tg-s6z2">O\n <td class="tg-s6z2">O\n <td class="tg-s6z2">(O,O) or (X,X)\n \n \n <td class="tg-s6z2">2\n <td class="tg-s6z2">O\n <td class="tg-s6z2">X\n <td class="tg-s6z2">(X,O) or (X,X)\n \n \n <td class="tg-s6z2">3\n <td class="tg-s6z2">X\n <td class="tg-s6z2">O\n <td class="tg-s6z2">(O,X) or (X,X)\n \n \n <td class="tg-s6z2">4\n <td class="tg-s6z2">X\n <td class="tg-s6z2">X\n <td class="tg-s6z2">(X,O) or (O,X) or (X,X)\n \n\n\nLet $A$ be the initial chip set, with $n$ chips and more than $\lfloor \frac{n}{2} \rfloor$ chips are good. Partition $A$ into pairs $(a_1,a_1')$, $(a_2,a_2')$, $\dots$, $(a_j,a_j')$ (and one additional element $a_{j+1}$ if $n$ is odd), with $j = \lfloor \frac{n}{2} \rfloor$. Consider the following algorithm.
" }, { "cell_type": "markdown", "metadata": {}, "source": "\nFor each pair $(a_k,a_k')$:
\n  If we get testing result 2, 3 or 4, then remove $a_k$ and $a_k'$ from $A$.
\n  If we get testing result 1, then remove one of $a_k$, $a_k'$ from $A$ in arbitrariness.
\n\n
" }, { "cell_type": "markdown", "metadata": {}, "source": "Proof of Correctness:
\nClearly, we do $\lfloor \frac{n}{2} \rfloor$ tests and remove at least one chip from $A$ for each single test, so $A$ contains at most $\lceil \frac{n}{2} \rceil$ chips after all tests done. To complete the proof, we have to show that $A$ keeps more than good chips than bad chips. Consider a test for pair $(a_k,a_k')$. If the testing result is 2, 3 or 4, it means at least one of $a_k$, $a_k'$ is bad. Hence, there are still more good chips than bad chips in $A$ after removing $a_k$ and $a_k'$. If the testing result is 1, it means either both $a_k$ and $a_k'$ are good or both $a_k$ and $a_k'$ are bad. Since good chips are major in $A$, and note that result 1 is the only possibile outcome for (O,O) pair, thus we must have the same or more quantity of (O,O) pairs than (X,X) pairs with result 1. Therefore, after all tests done, it remains the same or more good chips from result 1 than bad chips from pairs with result 1 in $A$, hence $A$ still holds more good chips than bad chips, and this completes the proof." }, { "cell_type": "markdown", "metadata": {}, "source": "
" } ], "metadata": {} } ] }