CS 310: Design and Analysis of Algorithms

All work should be done on your own. If you discuss this assignment in any way with anyone else, or find help for getting the answer from any source, you must state so clearly at the top of your submission. There should be no working together except to understand the question.

1. Consider the function:

   $$\begin{array}{ccc}f\left(x,y\right)& =& \left\{\begin{array}{ccc}f\left(\frac{x}{2},y\right)+f\left(x,\frac{y}{2}\right)& ;& x,y>1\\ 1& ;& x\le 1\vee y\le 1\end{array}\right.\end{array}$$

   1. Prove that a program which solves this recursively will always halt.

      Consider a similar function:

      $$\begin{array}{ccc}g\left(x\right)& =& \left\{\begin{array}{ccc}g\left(\frac{x}{2}\right)+1& ;& x>1\\ 1& ;& x\le 1\end{array}\right.\end{array}$$

      The expansion of this function will look like:

      $$\begin{array}{ccc}g\left(x\right)& =& g\left(\frac{x}{2}\right)+1\\ & =& g\left(\frac{x}{2^2}\right)+2\\ & =& g\left(\frac{x}{2^3}\right)+3\\ \dots & =& g\left(\frac{x}{2^i}\right)+i\end{array}$$

      This expansion will continue until 2ⁱ ≥ x. Since, by definition:

      $$\begin{array}{ccccccccccc}\frac{x}{y^a}& \le & 1& \Rightarrow & x& \le & y^a& \Rightarrow & a& \ge & {log}_{y}x\end{array}$$

      ∀ x ∃ log₂x ∋ the recursion will halt after $⌈{log}_{2}x⌉$ iterations. Since 1 is added each iteration with an extra 1 when x ≤ 2ⁱ, g(x) may also be expressed as:

      $$\begin{array}{ccc}g\left(x\right)& =& \left\{\begin{array}{ccc}⌈{log}_{2}x⌉+1& ;& x>1\\ 1& ;& x\le 1\end{array}\right.\end{array}$$

      The original function, f(x,y), reduces each of its recursive addends in a manner similar to g(x) and will eventually terminate.

      ---

      A more interesting proof was given in class:

      Assume that the pair (x, y) is the smallest pair of values for which the algorithm will not halt. The ordering of the pairs (x, y) is lexigraphical, that is:

      $$\begin{array}{ccccccc}\left(x,y\right)& <& \left(x,y+k\right)& <& \left(x+k,y\right)& \ni & k\in \mathbb{N},k\ge 1\end{array}$$

      The expansion then is:

      $$\begin{array}{ccc}f\left(x,y\right)& =& f\left(\frac{x}{2},y\right)+f\left(x,\frac{y}{2}\right)\end{array}$$

      As defined by the ordering:

      $$\begin{array}{ccccc}\left(\frac{x}{2},y\right)& <& \left(x,\frac{y}{2}\right)& <& \left(x,y\right)\end{array}$$

      Since (x, y) was the minmum value that f(x, y) would halt on, each of the addends will halt, f(x, y) will then halt, so (x, y) cannot exist.

   2. What is f(x,2)?

      $$\begin{array}{ccccc}f\left(x,2\right)& =& f\left(\frac{x}{2},2\right)+f\left(x,\frac{2}{2}\right)& =& f\left(\frac{x}{2},2\right)+1\\ & =& f\left(\frac{x}{2^2},2\right)+f\left(\frac{x}{2},\frac{2}{2}\right)+1& =& f\left(\frac{x}{2^2},2\right)+2\\ & =& f\left(\frac{x}{2^3},2\right)+f\left(\frac{x}{2^2},\frac{2}{2}\right)+2& =& f\left(\frac{x}{2^3},2\right)+3\\ \dots & =& f\left(\frac{x}{2^i},2\right)+i& =& g\left(x\right)\end{array}$$

      Support for this conclusion is given by a program which compares the recursive solution to log₂(x) + 1.

2. Suppose that you have a recurrence of the form $T\left(n\right)=\frac{n}{2}T\left(\frac{n}{2}\right)+1$. What is the solution in terms of order notation?

   Recall:

   $$\begin{array}{cccccccccccc}f\left(n\right)& =& O\left(g\left(n\right)\right)& \Rightarrow & \exists & c& \ni & T\left(f\left(n\right)\right)& \le & cg\left(n\right)& \forall & n\\ & & o\left(g\left(n\right)\right)& & & & & & <& & & \\ & & \Omega \left(g\left(n\right)\right)& & & & & & \ge & & & \\ & & \Theta \left(g\left(n\right)\right)& & & & & & =& & & \end{array}$$

   Consider the expansion of the expression:

   $$\begin{array}{ccccc}T\left(n\right)& =& \frac{n}{2}T\left(\frac{n}{2}\right)+1& & \\ & =& \frac{n}{2}\left(\frac{n}{2^2}T\left(\frac{n}{2^2}\right)+1\right)+1& =& \frac{n^2}{2^3}T\left(\frac{n}{2^2}\right)+\frac{n}{2}+1\\ & =& \frac{n^2}{2^3}\left(\frac{n}{2^3}T\left(\frac{n}{2^3}\right)+1\right)+\frac{n}{2}+1& =& \frac{n^3}{2^6}T\left(\frac{n}{2^3}\right)+\frac{n}{2^3}+\frac{n}{2}+1\\ & =& \frac{n^3}{2^6}\left(\frac{n}{2^4}T\left(\frac{n}{2^4}\right)+1\right)+\frac{n}{2^3}+\frac{n}{2}+1& =& \frac{n^4}{2^{10}}T\left(\frac{n}{2^4}\right)+\frac{n}{2^6}+\frac{n}{2^3}+\frac{n}{2}+1\\ \dots & =& \multicolumn{3}{c}{\left.\frac{n^m}{2^{\underset{j=1}{\overset{m+1}{\Sigma }}j}}T\left(1\right)+\left(\underset{i=1}{\overset{m}{\Sigma }}\frac{n}{2^{\underset{j=1}{\overset{i}{\Sigma }}j}}\right)+1\right|m=⌈{log}_{2}n⌉}\\ & =& \multicolumn{3}{c}{\frac{n^m}{2^{\frac{\left(m+1\right)\left(m+2\right)}{2}}}T\left(1\right)+\left(\underset{i=1}{\overset{m}{\Sigma }}\frac{n}{2^{\frac{i\left(i+1\right)}{2}}}\right)+1}\\ & =& \multicolumn{3}{c}{n^m{\sqrt{2}}^{-\left(m+1\right)\left(m+2\right)}T\left(1\right)+nm\underset{i=1}{\overset{m}{\Sigma }}{\sqrt{2}}^{-i\left(i+1\right)}+1}\\ & <& \multicolumn{3}{c}{n^m{\sqrt{2}}^{-m^2}T\left(1\right)+nm\underset{i=1}{\overset{m}{\Sigma }}{\sqrt{2}}^{-i^2}}\\ & =& \multicolumn{3}{c}{O\left(\frac{n^{{log}_{2}n}}{n^{\frac{{log}_{2}n}{2}}}\right)}\\ & =& \multicolumn{3}{c}{O\left(n^{{log}_{2}n-\frac{{log}_{2}n}{2}}\right)}\\ & =& \multicolumn{3}{c}{O\left(n^{\frac{{log}_{2}n}{2}}\right)}\\ & =& \multicolumn{3}{c}{O\left(n^{\frac{logn}{2}}\right)}\end{array}$$

   ---

   I originally ended up with $O\left(n^{logn}\right)$, and in all honesty don't entirely understand this solution.

   ---

   One option for determining the solution is not the "master theorem." Consider a general expression:

   $$\begin{array}{ccc}T\left(n\right)& =& aT\left(\frac{n}{b}\right)+f\left(n\right)\\ & =& b^{{log}_{b}a}T\left(\frac{n}{b}\right)+n^{{log}_{b}a}\frac{f\left(n\right)}{n^{{log}_{b}a}}\\ & =& \left.b^{p}T\left(\frac{n}{b}\right)+n^{p}g\left(n\right)\right|p={log}_{b}a,g\left(x\right)=\frac{f\left(n\right)}{n^p}\\ & =& n^{p}g\left(n\right)+n^{p}g\left(\frac{n}{b}\right)+b^{2p}T\left(\frac{n}{b^2}\right)\\ & =& n^{p}g\left(n\right)+n^{p}g\left(\frac{n}{b}\right)+n^{p}g\left(\frac{n}{b^2}\right)+b^{3p}T\left(\frac{n}{b^3}\right)\\ \dots & =& n^p\left(g\left(n\right)+g\left(\frac{n}{b}\right)+g\left(\frac{n}{b^2}\right)+\dots +g\left(\frac{n}{b^i}\right)\right)+b^{ip}T\left(\frac{n}{b^i}\right)\\ & =& n^p\underset{i=0}{\overset{{log}_{b}n}{\Sigma }}g\left(\frac{n}{b^i}\right)+b^{p{log}_{b}n}T\left(\frac{n}{b^{{log}_{b}n}}\right)\\ & =& n^p\underset{i=0}{\overset{{log}_{b}n}{\Sigma }}g\left(\frac{n}{b^i}\right)+n^{p}T\left(1\right)\end{array}$$

   There are three options for how g(n) will perform:

   • $g\left(n\right)$ is increasing • the $g\left(n\right)$ term will dominate the expression
   • $g\left(n\right)$ is constant • the $g\left(\frac{n}{b^i}\right)$ terms will all matter
   • $g\left(n\right)$ is decreasing • the $g\left(1\right)$ term will dominate the expression

   For this particular problem, T(n) is modified by a factor f(n) rather than a constant, so the solution cannot be applied.

3. In a certain set decomposition algorithm, a set is split into two non-intersecting subsets and the subsets are recursively subdivided. Each decomposition takes time propotional to the square of the number of elements in the current set being decomposed.

   1. Show that the worst case time for this decomposition is Θ(n³).

      The size of the subsets will be:

      $$\begin{array}{ccccc}n& =& n_1+n_2& =& \frac{an}{c}+\frac{\left(c-a\right)n}{c}\end{array}$$

      The time for generating each of these subsets is:

      $$\begin{array}{ccc}T\left(n\right)& =& c{n}^2+T\left(n_1\right)+T\left(n_2\right)\end{array}$$

      This combination has a minima when n₁ = n₂. The maximum is when one element is as large as possible. Because each subset must contain at least one element or the algorithm will not progress, this is:

      $$\begin{array}{ccc}{n}_1& =& n-1\end{array}$$ $$\begin{array}{ccccc}T\left(n\right)& =& c{n}^2+T\left(n_1\right)+T\left(n_2\right)& =& c{n}^2+T\left(n-1\right)+T\left(1\right)\\ & =& c{n}^2+\left(c{\left(n-1\right)}^2+T\left(n-2\right)+T\left(1\right)\right)+T\left(1\right)& =& c{n}^2+c{\left(n-1\right)}^2+T\left(n-2\right)+2T\left(1\right)\\ \dots & =& \underset{i=0}{\overset{k}{\Sigma }}c{\left(n-\mathrm{i}\right)}^2+T\left(n-k\right)+kT\left(1\right)& =& c\underset{i=0}{\overset{n-1}{\Sigma }}{\left(n-\mathrm{i}\right)}^2+nT\left(1\right)\\ & =& \Theta \left(n^3\right)& & \end{array}$$

   2. Show that if the decomposition has the property that neither subset of a decomposition step has more than $\frac{3}{4}$ of the elements from the set being decomposed, the worst case of the decomposition is Θ(n²).

      As before, the worst case scenario is when one element, n_i, is maximized. The exact nature of that decomposition is a bit tricky, however. The most obvious method for maximizing one quantity is to say:

      $$\begin{array}{ccc}n& =& \frac{3n}{4}+\frac{n}{4}\end{array}$$

      However, since $n,n_1,n_2\in \mathbb{N}$ there are times that it will not be posible to have a decomposition that divides evenly. The best case for maximization is:

      $$\begin{array}{ccccccc}{n}_1& \le & \frac{3n}{4}& ,& n_2& \le & \frac{n}{2}\end{array}$$

      Hypothesize that:

      $$\begin{array}{ccc}T\left(n\right)& \le & k{n}^2\end{array}$$ $$\begin{array}{ccccc}T\left(n\right)& =& c{n}^2+T\left(n_1\right)+T\left(n_2\right)& <& c{n}^2+T\left(\frac{3n}{4}\right)+T\left(\frac{n}{2}\right)\\ & \le & c{n}^2+k{\left(\frac{3n}{4}\right)}^2+k{\left(\frac{n}{2}\right)}^2& =& \multicolumn{3}{c}{c{n}^2+\frac{13k{n}^2}{16}}\end{array}$$

      I'm missing a step, then it's:

      $$\begin{array}{ccccccc}c{n}^2& \le & \frac{13k{n}^2}{16}& \iff & k& \ge & \frac{16c}{13}\end{array}$$