\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}
