\documentclass[12pt]{article}
\usepackage{amsmath}
%\usepackage{fullpage}
\usepackage[top=1in, bottom=1in, left=0.8in, right=1in]{geometry}
\usepackage{multicol}
\usepackage{wrapfig}
\usepackage{listings}
\usepackage{enumerate}
\usepackage{comment}
\usepackage{tikz}
\usepackage[ruled,vlined]{algorithm2e}
\lstset{language=Java,
basicstyle={\small\ttfamily},
columns=flexible,
belowskip=0mm}
\setlength{\columnsep}{0.1pc}
\begin{document}
\noindent
CS 161 \hfill \textbf{Problem Set 2} \newline
{Spring 2017} \hfill \textbf{Due:} April 21, 2017, 3pm
\noindent
\rule{\linewidth}{0.4pt}
\noindent
Please answer each of the following problems. Refer to the course webpage for the \textbf{collaboration policy,} as well as for \textbf{helpful advice} for how to write up your solutions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Problems:
\begin{enumerate}
% Problem 1
\item \textbf{Probability refresher} (4 points)
\begin{enumerate}
\item (1 point) What is the cardinality of the set of all subsets of $\{1,2,...,n\}$? \textbf{[We are expecting a mathematical expression along with one or two sentences explaining why it is correct.]}
\item (1 point) Suppose we choose a subset of $\{1,...,n\}$ uniformly at
random: that is, every set has an equal probability of being chosen. Let
$X$ be a random variable denoting the cardinality (that is, the size) of a
set randomly chosen in this way. Calculate the expected value of $X$ and
show your work. \textbf{[We are expecting a mathematically rigorous
argument establishing your answer. Your solution should not include
summation signs.]}
\item (2 points) Let $rand(a,b)$ return an integer uniformly at random from the range $[a,b]$. Each call to $rand(a,b)$ is independent. Consider the following function:
\begin{verbatim}
f(k,n):
if k <= 1:
return rand(1,n)
return 2 * f(k/2, n)
\end{verbatim}
What is the expected value and variance of $f(k,n)$? Assume that $k$ is a power of 2. Please show your work. \textbf{[In addition to your answer, we are expecting a mathematical derivation along with a brief (1-2 sentence) analysis of what the pseudocode above does in order to explain why your derivation is the right thing to do.]}
\end{enumerate}
\item \textbf{Fun with Big-O notation.} (6 points; 1 point each) Mark the following as \texttt{True} or \texttt{False}. Briefly but convincingly justify all of your answers, using the definitions of $O(\cdot)$, $\Theta(\cdot)$ and $\Omega(\cdot)$. \textbf{[To see the level of detail we are expecting, the first question has been worked out for you.]}
\begin{enumerate}
\item[(z)] $n = \Omega(n^2)$. This statement is \texttt{False}. To see this, we will use a proof by contradiction. Suppose that, as per the definition of $\Omega(\cdot)$, there is some $n_0$ and some $c > 0$ so that for all $n \geq n_0$, $n \geq c \cdot n^2$. Choose $n = \max \{ 1/c, n_0 \} + 1$. Then $n \geq n_0$, but we have $n > 1/c$, which implies that $c \cdot n^2 > n$. This is a contradiction.
\item $n = O(n \log(n))$.
\item $n^{1/\log(n)} = \Theta(1)$.
\item If \[f(n) = \begin{cases} 5^n & \text{if}~ n < 2^{1000} \\ 2^{1000} n^2 & \text{if}~ n \geq 2^{1000}\end{cases}\] and $g(n) = \frac{n^2}{2^{1000}}$, then $f(n) = O(g(n))$.
\item For all possible functions $f(n), g(n) \geq 0$, if $f(n) = O(g(n))$, then $2^{f(n)} = O( 2^{g(n)} )$.
\item $5^{\log\log(n)} = O(\log(n)^2)$
\item $n = \Theta\left( 100^{\log(n)} \right)$
\item The following two problems \textbf{are not required} but might be fun to think about. We will give you feedback if you do them but they will not affect your grade.
\begin{enumerate}
\item\textbf{(bonus)} $n|\sin(\pi n/2)| = O( n|\cos(\pi n/2)| )$
\item\textbf{(bonus)} $n|\sin(\pi n/2)| = \Omega( n|\cos(\pi n/2)| )$
\end{enumerate}
\end{enumerate}
\item \textbf{n-naught not needed.} (3 points)
Suppose that $T(n) = O(n^d)$, and that $T(n)$ is never equal to $\infty$. Prove rigorously that there exists a $c$ so that $0 \leq T(n) \leq c \cdot n^d$ for all $n \geq 1$. That is, the definition of $O(\cdot)$ holds with $n_0 = 1$. \textbf{[We are expecting a rigorous proof using the definition of $O(\cdot)$].}
\item \textbf{Fun with recurrences.} (6 points; 1 point each)
Solve the following recurrence relations; i.e. express each one as $T(n) = O(f(n))$ for the tightest possible function $f(n)$, and give a short justification. Be aware that some parts might be slightly more involved than others. Unless otherwise stated, assume $T(1) = 1$. \textbf{[To see the level of detail expected, we have worked out the first one for you.]}
\begin{enumerate}[(a)]
\item[(z)] $T(n) = 6T(n/6) + 1$. We apply the master theorem with $a = b = 6$ and with $d = 0$. We have $a > b^d$, and so the running time is $O(n^{\log_6(6)}) = O(n)$.
\item $T(n) = 2 T(n/2) + 3n$
\item $T(n) = 3 T(n/4) + \sqrt{n}$
\item $T(n) = 7 T(n/2) + \Theta(n^3)$
\item $T(n) = 4 T(n/2) + n^2 \log n$
\item $T(n) = 2 T(n/3) + n^c$, where $c \geq 1$ is a constant (that is, it doesn't depend on $n$).
\item $T(n) = 2T(\sqrt{n}) + 1$, where $T(2) = 1$
\end{enumerate}
\item \textbf{Different-sized sub-problems.} (6 points) (Note: this problem will be easier to do after class on Monday 4/16.)
Solve the following recurrence relation.
\[T(n) = T(n/2) + T(n/4) + T(n/8) + n,\]
where $T(1) = 1$.
\textbf{[We are expecting a formal proof. You may state your final running time with $O(\cdot)$ notation, but do not use it in your proof.]}
\item \textbf{What's wrong with this proof?} (8 points)
Consider the following recurrence relation:
\[ T(n) = T(n - 5) + 10\cdot n \]
for $n \geq 5$, where
$T(0) = T(1) = T(2) = T(3) = T(4) = 1$.
Consider the following three arguments.
\begin{enumerate}
\item[1.] \textbf{Claim: $T(n) = O(n)$.} To see this, we will use strong induction. The inductive hypothesis is that $T(k) = O(k)$ for all $5 \leq k < n$. For the base case, we see $T(5) = T(0) + 10\cdot 5 = 51 = O(1)$. For the inductive step, assume that the inductive hypothesis holds for all $k < n$. Then
\[ T(n) = T(n - 5) + 10 n, \]
and by induction $T(n - 5) = O(n-5)$, so
\[ T(n) = O(n-5) + 10n = O(n). \]
This establishes the inductive hypothesis for $n$.
Finally, we conclude that $T(n) = O(n)$ for all $n$.
\item[2.] \textbf{Claim: $T(n) = O(n)$.} To see this, we will use the Master Method. We have $T(n) = a \cdot T(n/b) + O(n^d)$, for $a = d = 1$ and
\[ b = \frac{1}{1 - 5/n}. \]
Then we have that $a < b^d$ (since $1 < 1/(1 - 5/n)$ for all $n > 0$), and the master theorem says that this takes time $O(n^d) = O(n)$.
\item[3.] \textbf{Claim: $T(n) = O(n^2)$.} Imagine the recursion tree for this problem. (Notice that it's not really a ``tree," since the degree is 1). At the top level we have a single problem of size $n$. At the second level we have a single problem of size $n - 5$. At the $t$'th level we have a single problem of size $n - 5t$, and this continues for at most $t = \lfloor n / 5 \rfloor + 1$ levels. At the $t$'th level for $t \leq \lfloor n/5 \rfloor$, the amount of work done is $10(n - 5t)$. At the last level the amount of work is at most $1$. Thus the total amount of work done is at most
$$1 + \sum_{t=0}^{\lfloor n/ 5 \rfloor} 10(n - 5t) = O(n^2).$$
\end{enumerate}
\begin{enumerate}
\item(3 points) Which, if any, of these arguments are correct? \textbf{[We are expecting a single sentence stating which are correct.]}
\item(5 points) For each argument that you said was incorrect, explain why it is incorrect. If you said that all three were incorrect, then give a correct argument. \textbf{[We are expecting a few sentences of detailed reasoning for each incorrect algorithm; and if you give your own proof we are expecting something with the level of detail of the proofs above---except it should be correct!]}
\end{enumerate}
\end{enumerate}
\end{document}