% This template was designed by Victor Lin (victorlin@cs.stanford.edu) with edits by Lisa Yan.
% You should compile this with PDFLaTeX (default), not XeLaTeX.

% This is a comment!

% This is the document declaration
\documentclass[12pt]{article}

% these are some useful packages. these add functionality to your document
\usepackage{newtxtext} % sets font
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{mathdots}
\usepackage{graphicx}
\usepackage{fancyhdr}
\thispagestyle{empty}
%\usepackage[margin=1in]{geometry}
\usepackage{multicol}
\usepackage{bm}
\usepackage{listings}
\PassOptionsToPackage{usenames,dvipsnames}{color}  %% Allow color names
\usepackage{pdfpages}
\usepackage{algpseudocode}
\usepackage{tikz}
\usepackage{enumitem}
\usepackage[T1]{fontenc}
\usepackage{inconsolata}
\usepackage{framed}
\usepackage[thinlines]{easytable}
\usepackage{minted}
\def\code#1{\texttt{#1}} % add some code in-line
\usepackage{mdframed}
\usepackage{colortbl}
\usepackage{makecell}
\usepackage{amsmath}  % math symbols
\usepackage{textpos}
\usepackage{wrapfig}  % in case you want to use a figure
\usepackage[hidelinks]{hyperref} % add hyper links

\usepackage{caption}
\captionsetup[figure]{labelformat=empty}% redefines the caption setup of the figures environment in the beamer class.


% This package controls the margins of the page.
\usepackage[top=1in, bottom=1in, left=0.8in, right=1in]{geometry}

\usepackage{multicol} % in case you want to use multiple columns
\setlength{\columnsep}{0.1pc}
\setlength{\parskip}{.5em}

% document headers!
\title{CS 109: Probability for Computer Scientists\\Quiz \#1}
\author{author} % Change this to your name!
\date{\today} % today does the right thing

\makeatletter
\lhead{\@author}
\chead{CS109 Quiz \#1}
\rhead{\today}
\makeatother

\newcommand{\abs}[1]{\lvert #1 \rvert}
\newcommand{\absfit}[1]{\left\lvert #1 \right\rvert}
\newcommand{\norm}[1]{\left\lVert #1 \right\rVert}
\newcommand{\eval}[3]{\left[#1\right]_{#2}^{#3}}
\renewcommand{\(}{\left(}
\renewcommand{\)}{\right)}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\pd}[1]{\frac{\partial}{\partial #1}}
\newcommand{\inner}[1]{\langle#1\rangle}
\newcommand{\cond}{\bigg|}
\newcommand{\rank}[1]{\mathbf{rank}(#1)}
\newcommand{\range}[1]{\mathbf{range}(#1)}
\newcommand{\nullsp}[1]{\mathbf{null}(#1)}
\newcommand{\repr}[1]{\left\langle#1\right\rangle}

\DeclareMathOperator{\Var}{Var}
\newcommand{\SD}{\operatorname{SD}}
\newcommand{\Cov}{\operatorname{Cov}}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\Tr}{\mathbf{Tr}}
\DeclareMathOperator{\diag}{\mathbf{diag}}
\DeclareMathOperator{\dist}{\mathbf{dist}}
\DeclareMathOperator{\prob}{\mathbf{prob}}
\DeclareMathOperator{\dom}{\mathbf{dom}}
\DeclareMathOperator{\E}{\mathbf{E}}
\DeclareMathOperator{\R}{\mathbb{R}}
\DeclareMathOperator{\var}{\mathbf{var}}
\DeclareMathOperator{\quartile}{\mathbf{quartile}}
\DeclareMathOperator{\conv}{\mathbf{conv}}
\DeclareMathOperator{\VC}{VC}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\newcommand{\Uni}{\operatorname{Uni}}
\newcommand{\Ber}{\operatorname{Ber}}
\newcommand{\Bin}{\operatorname{Bin}}
\newcommand{\Geo}{\operatorname{Geo}}
\newcommand{\NegBin}{\operatorname{NegBin}}
\newcommand{\Zipf}{\operatorname{Zipf}}
\newcommand{\HypG}{\operatorname{HypG}}
\newcommand{\Poi}{\operatorname{Poi}}
\newcommand{\Beta}{\operatorname{Beta}}
\newcommand{\Normal}{\operatorname{\mathcal{N}}}
\newcommand{\N}{\operatorname{\mathcal{N}}}
\newcommand{\Exp}{\operatorname{Exp}}
\DeclareMathOperator{\NP}{\mathbf{NP}}
\DeclareMathOperator{\coNP}{\mathbf{coNP}}
\DeclareMathOperator{\TIME}{\mathsf{TIME}}
\DeclareMathOperator{\polytime}{\mathbf{P}}
\DeclareMathOperator{\PH}{\mathbf{PH}}
\DeclareMathOperator{\SIZE}{\mathbf{SIZE}}
\DeclareMathOperator{\ATIME}{\mathbf{ATIME}}
\DeclareMathOperator{\SPACE}{\mathbf{SPACE}}
\DeclareMathOperator{\ASPACE}{\mathbf{ASPACE}}
\DeclareMathOperator{\NSPACE}{\mathbf{NSPACE}}
\DeclareMathOperator{\Z}{\mathbb{Z}}
\DeclareMathOperator{\EXP}{\mathbf{EXP}}
\DeclareMathOperator{\NEXP}{\mathbf{NEXP}}
\DeclareMathOperator{\NTIME}{\mathbf{NTIME}}
\DeclareMathOperator{\DTIME}{\mathbf{DTIME}}
\DeclareMathOperator{\poly}{poly}
\DeclareMathOperator{\BPP}{\mathbf{BPP}}
\DeclareMathOperator{\ZPP}{\mathbf{ZPP}}
\DeclareMathOperator{\RP}{\mathbf{RP}}
\DeclareMathOperator{\coRP}{\mathbf{coRP}}
\DeclareMathOperator{\BPL}{\mathbf{BPL}}
\DeclareMathOperator{\IP}{\mathbf{IP}}
\DeclareMathOperator{\PSPACE}{\mathbf{PSPACE}}
\DeclareMathOperator{\NPSPACE}{\mathbf{NPSPACE}}
\DeclareMathOperator{\SAT}{\mathsf{SAT}}
\DeclareMathOperator{\NL}{\mathbf{NL}}
\DeclareMathOperator{\PCP}{\mathbf{PCP}}
\DeclareMathOperator{\PP}{\mathbf{PP}}
\DeclareMathOperator{\cost}{cost}
\let\Pr\relax
\DeclareMathOperator*{\Pr}{\mathbf{Pr}}

\usepackage{booktabs}
\usepackage{diagbox}
  % configure display of tables
\newcommand{\ra}[1]{\renewcommand{\arraystretch}{#1}}
\newcommand\tab[1][1cm]{\hspace*{#1}}
\newcommand\tabhead[1]{\small\textbf{#1}}

\theoremstyle{definition}
\newtheorem*{answer}{Answer}

\definecolor{shadecolor}{gray}{0.95}

\setlength{\parindent}{0pt}

\pagestyle{fancy}
\setlength{\headheight}{15pt}

\renewcommand{\thefootnote}{\fnsymbol{footnote}}

% begin the document
\begin{document}

% actually insert the title.
\makeatletter
% the handout title goes here
\begin{textblock*}{0.5\textwidth}(0\textwidth,0mm)
\@author
\end{textblock*}

\begin{textblock*}{0.5\textwidth}(.5\textwidth,0mm)
\hfill
\@date
\end{textblock*}

\begin{center}
\vspace*{2mm}
{\Large \@title} \\
\end{center}
\vskip -7mm
\rule{\textwidth}{0.5pt}
\makeatother

%%%

%%%

\vspace*{-2em}
\subsection*{Take-Home Quiz information}
\vspace*{-1em}
Each quiz will be a 24-hour open-book, open-note exam. Quiz material will approximate about 2 hours of active work (\textit{before} typesetting), though it may be more depending on how you prepare your submission. Unlike the problem sets, the take-home quizzes are \textbf{\textit{strictly individual work}}. Even course staff assistance will be limited to clarifying questions of the kind that might be allowed on a traditional, in-person exam. If you have questions during the exam, please ask them via our discussion forum. We will not have any office hours for answering quiz questions during the quiz.

\textbf{For each problem, briefly explain/justify how you obtained your answer} at a level such that a future CS109 student would be able to understand how to solve the problem. It is fine for your answers to be a well-defined mathematical expression including summations (but not integrals), products, factorials, exponentials, and combinations, unless the question \textit{specifically} asks for a numeric quantity or closed form. Where numeric answers are required, the use of fractions is fine. 


\vspace*{-1em}
\subsection*{Honor Code Guidelines for Take-Home Quizzes}
\vspace*{-1em}
The take-home exams are open-book (open lecture notes, handouts, textbooks, course lecture videos, and internet searches for conceptual information, e.g., Wikipedia). Consultation of other humans in any form or medium (e.g., communicating with classmates, asking questions on forum websites such as StackOverflow) is prohibited. All work done with the assistance of any external material in any way (other than provided CS109 course materials) must include citation (e.g., ``Referred to Wikipedia page on DeMorgan's Law for Question 2.''). Copying solutions is unacceptable, even with citation. If by chance you encounter solutions to the problem, navigate away from that page before you feel tempted to copy. If you become aware of any honor code violations by any student in the class, your commitments under the Stanford Honor Code obligate you to inform course staff. \textit{Because of the S/NC nature of this quarter, as well as the many opportunities available to you to make up this material with extra credit and contest work, please remember that there is no reason to violate your conscience to complete a take-home exam.}


\vspace*{-1em}
\subsection*{Submission}
\vspace*{-1em}
You should upload your submission as a PDF to Gradescope. We provide a LaTeX template if you find it useful, but we will accept any legible submission. You can submit multiple times; we will only grade the last submission you submit before 11:59pm (Pacific time) on Thursday April 30$^\text{th}$. No exam submissions will be accepted late.  \textit{\textbf{Please double-check that you submit the right file.}} When uploading, please assign pages to each question. Failure to do so will result in a 2-point deduction.

\vspace*{1em}

I acknowledge and accept the letter and spirit of the Honor Code:

\newcommand{\blank}{\hrulefill{}}
\newcommand{\ulfrule}{\xleaders\hbox{\underline{ }}\hfill\kern0pt}

\vspace*{1.5em}
\makeatletter
Name (typed or written): \ulfrule{}\underline{\@author}\ulfrule{} % LaTeX will automatically populate your name here
% Name (typed or written): \blank{} % uncomment this line if you would like a blank line
\makeatother

\setlist{nolistsep}

%%%%%%%%%%%%%%%%%%%%%% 1 %%%%%%%%%%%%%%%%%%%%%%
\newpage
\section{Academic Planning [25 points]}

You have just been elected social chair for the student organization PRoB (Probability Revolution or Bust) for the coming academic year 2020--2021. As new social chair, you would like to hold 10 (indistinct) socials over the next 3 quarters (Autumn, Winter, and Spring). Each social is equally likely to be assigned to any of the quarters, and it is possible that a quarter has no socials.  Order of socials within a quarter doesn't matter.

\begin{itemize}
\item[a.] (5 points) In how many distinct ways can the 10 (indistinct) socials be allocated to the 3 quarters?

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}

\item[b.] (5 points) In how many distinct ways can the 10 (indistinct) socials be allocated to the 3 quarters if you must hold at least 2 socials each quarter?

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}

\item[c.] (3 points) Let your answer to part (a) be $n$. Consider the event where you hold 3 socials in Autumn, 3 socials in Winter, and 4 socials in Spring. Is the probability of this event $\frac{1}{n}$? Briefly explain in a few sentences why or why not.

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}

\item[d.] (12 points) You are also planning your courseload for next year. You have 10 courses to schedule over 3 quarters (Autumn, Winter, and Spring). All of the courses are distinct and offered every quarter; order of courses within a quarter doesn't matter. In how many distinct ways can you allocate 10 (distinct) courses to the 3 quarters if you can take at most 4 courses in any quarter?

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}

\end{itemize}


%%%%%%%%%%%%%%%%%%%%%% 2 %%%%%%%%%%%%%%%%%%%%%%
\newpage
\section{More Sensors, More Data [25 points]}
A home robot has two different sensors for motion detection. If there is a moving object, sensor $V$ (video camera) will detect motion with probability 0.95, and sensor $L$ (laser) will detect motion with probability 0.8. If there is no moving object, there is a 0.1 probability that sensor $V$ will detect motion (even though there is no object), and a 0.05 probability that sensor $L$ will detect motion.

\vspace*{.5em}
Based on empirical evidence, the probability that there is a moving object is 0.7. Note that these sensors use independent detection algorithms to identify motion, so that \textbf{conditioned} on there being a moving object (or not), the events of detecting motion (or not) for each Sensor is \textbf{independent}. 

\begin{itemize}
\item[a.] (3 points) Given that there is a moving object and that sensor $V$ does not detect motion, what is the probability that sensor $L$ detects motion? Give a numerical answer.

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}

\item[b.] (5 points) Given that there is a moving object, what is the probability that \textbf{at least one} of the two sensors detects motion? Give a numerical answer. \\
{\small Note: You can use WolframAlpha as a calculator (it also accepts LaTeX equations). Example:
\url{https://www.wolframalpha.com/input/?i=sum+x%5Ek%2Fk%21%2C+k%3D0+to+infinity}}

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}
    
\item[c.] (5 points) Given that there is a moving object, what is the probability that \textbf{exactly one} of the two sensors detects motion? Give a numerical answer.

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}
	
\item[d.] (8 points) What is the probability that there is a moving object given that \textbf{both} sensors detect motion? Give a numerical answer.


    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}
	
\item[e.] (4 points) The probabilities that sensor $V$ detects motion given a moving object and that sensor $V$ detects motion given no moving object do not sum up to $1$. Briefly explain in a few sentences why this is okay.

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}

\end{itemize}


%%%%%%%%%%%%%%%%%%%%%% 3 %%%%%%%%%%%%%%%%%%%%%%
\newpage
\section{Mittens and Kittens [30 points]}
\vspace*{-2em}

\begin{figure}[h]
% Please check the quiz PDF on the website for this image.
% to include this image with your code:
% 1) download the website image: http://web.stanford.edu/class/cs109/exams/quiz1/mittens.jpg
% 2) save the image to the same folder as this file (e.g., upload to overleaf)
% otherwise just comment out everything from \begin{figure} to \end{figure}.
\centering
\includegraphics[width=\textwidth]{mittens}
\vspace*{-2em}
\caption*{\small  (Left: A modified General Mills promotion (1963) showing three distinct mittens. Right: 16 distinct mittens.)} 
\end{figure}

You have 8 pairs of mittens, each a different pattern. Left and right mittens are also distinct. Suppose that you are fostering (possibly imaginary) kittens, and you leave them alone for a few hours with your mittens. When you return, you discover that they have hidden 4 mittens! Suppose that your kittens are equally likely to hide any 4 of your 16 distinct mittens. Let $X$ be the number of complete, distinct \textbf{\textit{pairs}} of mittens that you have left.

\begin{itemize}
\item[a.] (15 points) Compute the probability mass function of $X$, $p_X(x)$.  (Hint: Note the support of $X$ is $\{4, 5, 6\}$; only 4, 5, or 6 complete pairs are possible after the kitten fiasco.)

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}
    
\item[b.] (5 points) Compute $E[X]$ using the definition of expectation and your answer to (a).


    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}
    
\item[c.] (10 points) Define the random variable $X_i$ to be $1$ if your $i^{\text{th}}$ pair of mittens is complete after the kitten fiasco, and $0$ otherwise, Using this definition of $X_i$ for $i = 1, \dots, 8$ and the linearity of expectation, compute $E[X]$ again. \textbf{Do not use your answer to part (a)}.

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}

\end{itemize}


%%%%%%%%%%%%%%%%%%%%%% 4 %%%%%%%%%%%%%%%%%%%%%%
\newpage
\section{DashDoor: Food Delivery [30 points]}
A food takeout and delivery company, DashDoor (like DoorDash, but better) wants to understand how busy their employees are each month. In metropolitan areas, employees receive on average 8 customer requests each day.  Regardless of where they work, each employee spends exactly 0.5 hours to make deliveries for each request (one at a time); for example, an employee who receives exactly 4 requests on a particular day will spend exactly 2 hours making deliveries.

\begin{itemize}

\item[a.] (4 points) What is the variance of the number of hours that a metropolitan employee spends on making deliveries in a day?

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}

\item[b.] (6 points) What is the probability that a metropolitan employee has a ``very busy day,'' defined as spending at least 5 hours making deliveries from requests received that day? Give a numerical answer. \\
{\small Note: You can use WolframAlpha as a calculator (it also accepts LaTeX equations). Example:
\url{https://www.wolframalpha.com/input/?i=sum+x%5Ek%2Fk%21%2C+k%3D0+to+infinity}}

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}

\item[c.] (6 points) The company estimates that $0.6$ of their employees work in metropolitan areas, and the rest in suburban areas. Suburbs have different customer demand: in suburban areas, employees receive on average 6 customer requests each day. What is the probability that a randomly chosen employee has a very busy day? \\
{\small (You do not need to give a numerical answer; a well-defined mathematical expression is fine.)}

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}

\item[d.] (14 points) Consider a metropolitan employee. The event that they have a very busy day on a particular day is independent of their business on other days. Let $p$ be your answer from part (b), the probability that they have a very busy day.
\begin{itemize}
	\item[i.] (6 points) What is the probability that this employee has more than 10 busy days in the next 20 working days? Leave your answer in terms of $p$.

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}
	
	
	\item[ii.] (4 points) What is the expected number of very busy days that this employee has over the next 20 working days? Leave your answer in terms of $p$.

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}
	
	\item[iii.] (4 points) Would it be reasonable to approximate the probability you computed in part (d)(i) using a Poisson random variable? Briefly explain in a few sentences why or why not.

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}
	
	\end{itemize}

\end{itemize}

\end{document}