\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{clrscode3e}

\newcommand{\deq}{:=}

\begin{document}
\begin{center}
{\huge \textbf{CS49/Math59 Lab 1} }
\end{center}
\vspace{0.2in} This lab assignment is due {\bf before the start of
  class} on Wednesday, September 16.  Homework handed in during class
but after I begin the lecture will be counted as late submissions.
Some things to note:
\begin{itemize}
\item I encourage you to write your solution using \LaTeX, but you are not
required to.
\item You may have one partner for this assignment, but are not required to.
If you work with a partner, submit just one writeup.
%
\item Aside from your partner, you should not discuss problems in detail
with anyone.  It's OK to discuss approaches at a high level.  In fact,
I encourage you to discuss general strategies.  However, you should
not reveal specific details of a solution, nor should you show your
written solution to anyone else.
\end{itemize}
Make sure your names are on your submission.
\begin{enumerate}
\item \textbf{Conditional Probability.}  Let $A, B_1,\ldots, B_k$
  be events such that $\{B_1,\ldots, B_k\}$ partition\footnote{a
    \emph{partition} of $\Omega$ is a collection of pairwise disjoint
    subsets whose union equals $\Omega$.  For example, $\{1,3\}, \{2,
    5\}, \{4\}$ partition the set $\{1,2,3,4,5\}$} $\Omega$.  Show
  that $$\Pr[A] = \sum_{i=1}^k \Pr[B_i]\Pr[A|B_i]\ .$$
\item \textbf{The Chain Rule (Shoup, exercise 8.5)} For events $A_1,\ldots,A_n$, define
  $\alpha_1 \deq \Pr[A_1]$, and for $i = 2, \ldots, n$, define
  $\alpha_i \deq \Pr[A_i | A_1\cap A_2 \cap \cdots \cap A_{i-1}]$
  (assume that $\Pr[A_1\cap \cdots \cap A_{n-1}] \neq 0$).  Show that
  $\Pr[A_1\cap\cdots \cap A_n] = \alpha_1\cdots \alpha_n$.
\item \textbf{Probability vs.~Conditional Probability.}  Let $\Omega
  \deq \{1,\ldots, 8\}, A \deq \{1,3,5,7\}$, and $B \deq \{1,2,3,4\}$.
  \begin{enumerate}
  \item Define a probability distribution $P_1$ on $\Omega$ such that $P_1[A] < P_1[A|B]$.
  \item Define a probability distribution $P_2$ on $\Omega$ such that $P_2[A] = P_2[A|B]$.
  \item Define a probability distribution $P_3$ on $\Omega$ such that
    $P_3[A] > P_3[A|B]$.
  \end{enumerate}
\item \textbf{Random Variables (Shoup, exercise 8.16).}  Let $X,Y$ be
  independent random variables such that $X$ is uniformly distributed
  over a set $S$ and $Y$ is uniformly distributed over a set $T
  \subset S$.  Define a third random variable $Z$ as follows: if $X
  \in T$ then $Z \deq X$.  Otherwise, $Z \deq Y$.  Show that $Z$ is
  uniformly distributed over $T$.
\item \textbf{Algorithm Analysis.}  Order the following functions in
  ascending order of growth.  For example, if $f = O(g)$ then place
  $f$ before $g$ in your ordering.
  \begin{enumerate}
  \item $f_1(n) = 10n$.
  \item $f_2(n) = 5\sqrt{n} \log n$.
  \item $f_3(n) = 2^{n/3}$.
  \item $f_4(n) = 2(\log n)^2$.
  \item $f_5(n) = e^n/6$.
  \end{enumerate}
\item \textbf{Probabilistic Method} Solve one of the following problems:
  \begin{itemize}
  \item Three hundred students took an exam for CS21.  There were
    eight problems to solve.  It is known that each problem was
    correctly solved by at least 200 students.  Show that there must
    be two students such that every problem was solved by at least one
    of these two students.
  \item There are several circles inside a square of side length $1$.
    The total circumference of all the circles is $10$.  Show that
    there is a a line that intersects at least four of the circles.
  \end{itemize}
\item \textbf{Attribution.}  Did you get assistance on any of the
  problems on this assignment from anyone aside from me and/or your
  lab partner?  For example, did you discuss any problems at a high
  level with other students?  Did you accidentally stumble on
  solutions while doing a websearch on related material?  If so,
  descibe the nature of the assistance here.  (e.g. ``We briefly
  discussed problem 1 with X,Y, and Z'' or ``We saw a solution on
  $\langle$this website$\rangle$ before finding our own solution'') If you (and your
  partner) worked alone, please say so here.
\item \textbf{Lab Questionnaire.} (None of these questions will have
  an impact on your grade, this is to help provide the feedback I need
  to make the course the best it can be)
  \begin{enumerate}
  \item Approximately how many hours per partner did you spend on this
    lab?
  \item How difficult did you find this lab?  (enter a number 1-5,
    with 5 being very difficult and 1 being very easy)
  \item Describe the biggest challenge you faced on this lab.
  \end{enumerate}
\end{enumerate}
\end{document}
