% LaTeX handouts by Will Monroe
% Based on B. E. Burr's CS 109 problem set template

\documentclass[12pt]{article}
\usepackage{newtxtext,newtxmath}

\usepackage{amsmath}
 \let\Bbbk\relax
\usepackage{amssymb}
  \let\openbox\relax
\usepackage{amsthm}
	% packages that allow mathematical formatting
\usepackage{comment}
  % comment out sections

\usepackage{graphicx}
\usepackage{float}
\usepackage{subcaption}
\usepackage{wrapfig}
\usepackage{multirow}
	% multi-row

\usepackage{import}
	% package that allows for relative imports

\usepackage{tikz}
\usetikzlibrary{arrows,positioning,automata}
	% package that allows you to include graphics

\usepackage[hidelinks]{hyperref}
	% and links
\usepackage{algpseudocode}
  % and algorithms
\usepackage{pythonhighlight}
%\usepackage[cachedir=_minted-caches]{minted} % minted doesn't work with macros
	% and code
\usepackage{listings} % supports escapechars for macros

\definecolor{mygreen}{rgb}{0,0.6,0}
\definecolor{mygray}{rgb}{0.5,0.5,0.5}
\definecolor{mymauve}{rgb}{0.58,0,0.82}
\lstset{ %
  basicstyle=\footnotesize\ttfamily, % Default font
  backgroundcolor=\color{white},   % choose the background color
  breaklines=true,                 % automatic line breaking only at whitespace
  captionpos=b,                    % sets the caption-position to bottom
  commentstyle=\color{mygreen},    % comment style
  escapeinside={\%*}{*)},          % if you want to add LaTeX within your code
  keywordstyle=\color{blue},       % keyword style
  stringstyle=\color{mymauve},     % string literal style
}

\usepackage[tmargin=1in,bmargin=1in,lmargin=0.8in,rmargin=1in]{geometry}
\frenchspacing
	% one space after periods
\raggedbottom
	% don't put extra space between sections

\usepackage{fancyhdr}
\pagestyle{fancy}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt} 
\setlength{\headheight}{14.5pt} 
	% allows custom headers

\lhead{}
\rhead{-- \thepage{} --}
\cfoot{}
	% page numbering

\usepackage{titlesec}
\titleformat*{\section}{\large\bfseries}
\titleformat*{\subsection}{\large\itshape\bfseries}
\titleformat*{\subsubsection}{\normalsize\bfseries}
\titleformat*{\paragraph}{\normalsize\bfseries}
\titleformat*{\subparagraph}{\normalsize\bfseries}
\setlength{\parindent}{0cm}
\setlength{\parskip}{3mm plus 3mm minus 1mm}
\titlespacing*{\section}{0pt}{2mm plus 4mm minus 1mm}{-2mm plus 1mm minus 0mm}
\titlespacing*{\subsection}{0pt}{0mm plus 4mm minus 1mm}{-2mm plus 1mm minus 0mm}
\titlespacing*{\subsubsection}{0pt}{0mm plus 4mm minus 1mm}{-2mm plus 1mm minus 0mm}
\titlespacing*{\paragraph}{0pt}{0mm plus 3mm minus 1mm}{1mm plus 1mm minus 0mm}
  % adjust fonts and spacing

\usepackage{framed}
\begin{comment}
\newenvironment{framed}
    {
    \hspace*{-3mm}
    \begin{tabular}{|p{\textwidth}|}
    \hline
    }
    { 
    \\[2mm]\hline
    \end{tabular} 
    \vspace*{-2mm}
    }
  % boxes around paragraphs with titles
\end{comment}

\usepackage{textpos}
\usepackage[super]{nth}
\usepackage{mathtools}
\usepackage{mathdots}

\usepackage{textcomp}
  % \textonehalf for '8 1/2" x 11"'

\usepackage{enumitem}
% \setlist{nolistsep}
  % configure display of enumerations [a), b), c)...]
\usepackage[normalem]{ulem}
  % \sout{} for strikethrough
\usepackage{booktabs}
\usepackage{diagbox}
  % configure display of tables
\usepackage[document]{ragged2e}

\newcommand{\vocab}[1]{\textbf{#1}}
\renewcommand{\|}{\mid}

\newcommand{\ra}[1]{\renewcommand{\arraystretch}{#1}}
\newcommand\tab[1][1cm]{\hspace*{#1}}
\newcommand\tabhead[1]{\small\textbf{#1}}

\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\E}{E}
\newcommand{\Var}{\operatorname{Var}}
\newcommand{\SD}{\operatorname{SD}}
\newcommand{\Cov}{\operatorname{Cov}}
\newcommand{\bigO}{O}

\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{\N}{\mathcal{N}}
\newcommand{\Exp}{\operatorname{Exp}}
\newcommand{\GammaRV}{\operatorname{Gamma}}

\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\argmax}{arg\,max}

\makeatletter
\newcommand{\ack}[1]{\def \@ack {#1}}
\newcommand{\handoutid}[1]{\def \@handoutid {#1}}
\newcommand{\spaceadjust}[1]{\def \@spaceadjust {#1}}
\makeatother

\ack{}
\handoutid{}
\spaceadjust{0mm}

\renewcommand{\labelenumi}{\arabic{enumi}.}
\renewcommand{\labelenumii}{\alph{enumii}.}

% needs to be included with template for signatures
\newcommand{\blank}{\hrulefill{}}
\newcommand{\ulfrule}{\xleaders\hbox{\underline{ }}\hfill\kern0pt}

% needs to be included with template for answer space                                                                                 
\theoremstyle{definition}                                                        
\newtheorem*{answer}{Answer}                                                     
                                                                                 
\definecolor{shadecolor}{gray}{0.95}                                             
                                                                                 
\setlength{\parindent}{0pt}                                                      
                                                                                 
\pagestyle{fancy}                                                                
\setlength{\headheight}{15pt}                                                    
                                                                                 
\renewcommand{\thefootnote}{\fnsymbol{footnote}}     
\title{CS109 Quiz \#1}
\handoutid{Quiz \#1}
\author{Chris Piech, Jerry Cain, Freya, and Doris}
\date{February 3-5, 2021}
\begin{document}

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

\begin{textblock*}{0.5\textwidth}(0\textwidth,5mm)
CS 109
\end{textblock*}

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

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

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

\vspace*{-4mm}
\hfill {\footnotesize \@ack}
\makeatother

%%%
\vspace*{-1em}
\section*{Take-Home Quiz information}
Each quiz will be a 46.5-hour open-book, open-note exam. We have designed this quiz to approximate about 1-2 hours of active work (\textit{before} typesetting). 
\vspace*{-1em}
\begin{itemize}[itemsep=0pt]
\item You can submit multiple times; we will only grade the last submission you submit before 1:00pm (Pacific time) on Friday, February 5$^\text{th}$. No late submissions can be accepted. When uploading, please assign pages to each question.
\item 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 may also find the CS109 Probability LaTeX reference useful: {\small \url{https://www.overleaf.com/project/5f650a577489e90001f065be}}
\item 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 as private posts via our discussion forum. We will not have any office hours for answering quiz questions during the quiz, and we can't answer any questions about course material while the quiz it out.
\item \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. If it's not fully clear how you arrived at your answer, you will not receive full credit.} It is fine for your answers to be a well-defined mathematical expression including summations, products, factorials, exponents, and combinations, unless the question \textit{specifically} asks for a numeric quantity or closed form. Where numeric answers are required, fractions are fine.
\end{itemize} 

\vspace*{-1em}
\section*{Honor Code Guidelines for Take-Home Quizzes}
\textbf{\textit{This exam must be completed individually.}} It is a violation of the Stanford Honor Code to communicate with any other humans about this exam (other than CS109 course staff), to solicit solutions to this exam, or to share your solutions with others.

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 sites like Chegg or Stack Overflow) 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 $X$ 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{\textbf{Please remember that there is no reason to violate your conscience to complete a take-home exam in CS109.}}

\vspace*{1em}

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

\vspace*{1.5em}
Name (typed or written): \blank{} % if in LaTeX, write your name in the curly braces

\setlist{nolistsep}
%%%%%%%%%%%%%%%%%%%%%% 1 %%%%%%%%%%%%%%%%%%%%%%
\newpage
\section{The Freya Checkers Invitational [30 points]}\label{sec:clt}

Don't tell Stanford, but Chris and Jerry each have side jobs as professional Checkers players, and they're set to compete against one another and play a total of 9 games in the Freya Checkers Invitational. Each game results in either a win for Chris, a win for Jerry, or a tie. A win is worth 2 points, a tie is worth 1 point, and a loss is worth 0.

\begin{enumerate}[label=\alph*.]

%%%%%%%%%%%%%%%%%%%%%%
\item (7 points) How many different ways can Chris arrive at 2 wins, 5 draws, and 2 losses if all 9 games are played?
    \begin{shaded}

    \begin{answer}

       % your answer here

    \end{answer}

    \begin{tabular}{l  p{.5in} p{2in} l}
    In addition to providing an expression above, \\
    please compute an integer answer:&
    &            % replace with & 9999 (keeping ampersand (&) on left, 9999 being your answer)
    &  \\
    \cline{3-3}
    \end{tabular}
    \end{shaded}

\item (8 points) What is the probability that Chris gets 10 points when all 9 games are played?  Assume that each game results in a win for Chris, a win for Jerry, or a tie with equal likelihood, and that all games are independent.

    \begin{shaded}

    \begin{answer}

       % your answer here

    \end{answer}

    \begin{tabular}{l  p{.5in} p{2in} l}
    In addition to providing an expression above, \\
    please compute a numeric answer:&
    &           % replace with & 9999 (keeping ampersand (&) on left, 9999 being your answer)
    &  \\
    \cline{3-3}
    \end{tabular}
    \end{shaded}


\item (7 points) Because Freya is in a hurry to get Chris home, Chris and arch-nemesis Jerry agree to play a best-of-9 tournament, where play stops when one accumulates 10 points, or they've played all 9 games, whichever comes first. How many different ways can Chris win the tournament by a score of 10 to 8?

    \begin{shaded}

    \begin{answer}

       % your answer here

    \end{answer}

    \begin{tabular}{l  p{.5in} p{2in} l}
    In addition to providing an expression above, \\
    please compute an integer answer:&
    &           % replace with & 0.9999 (keeping ampersand (&) on left, 0.9999 being your answer)
    &  \\
    \cline{3-3}
    \end{tabular}
    \end{shaded}

\item (8 points) Eager to get Chris home to Freya even more quickly, Jerry proposes they keep playing until one player's point total exceeds the other's by 3 or more points. Assume that Chris and Jerry each win a single game with probability of 0.25 and 0.15, respectively, and they tie with probability 0.6. What is the probability that Chris eventually wins?

    \begin{shaded}

    \begin{answer}

       % your answer here

    \end{answer}

    \begin{tabular}{l  p{.5in} p{2in} l}
    In addition to providing an expression above, \\
    please compute a numeric answer:&
    &           % replace with & 9999 (keeping ampersand (&) on left, 9999 being your answer)
    &  \\
    \cline{3-3}
    \end{tabular}
    \end{shaded}
    
\end{enumerate}%%%%%%%%%%%%%%%%%%%%%% 2 %%%%%%%%%%%%%%%%%%%%%%
\newpage
\section{Malware Detection [30 points]}\label{sec:skating}

Jerry's nephew, Andrew, just started high school this past September, and because all course instruction is online, his high school provided him with an old laptop so he could Zoom in for class. To better protect its own equipment from malware and viruses, the school installed two browser extensions to scrutinize all web downloads. Each download is either safe (event $S$) or unsafe (event $S^C$), and all downloads are examined by both extensions. The first extension marks the download as either safe (event $A$) or unsafe (event $A^C$), and the second extension marks the download as safe (event $B$) or unsafe (event $B^C$). \\
\,  \\
Assume that 94\% of Andrew's web downloads are safe, and that:

\begin{itemize}
\item the first browser extension accurately marks unsafe downloads as unsafe with probability 0.93, but improperly marks safe downloads as unsafe with probability 0.04.
\item the second browser extension accurately marks unsafe downloads as unsafe with probability 0.85, but improperly marks safe downloads as unsafe with probability 0.02.
\end{itemize}

Assume that given a download is safe, the two browser extensions independently mark that download as safe. Similarly, the two browser extensions independently mark unsafe downloads as unsafe.

\begin{enumerate}[label=\alph*.]

%%%%%%%%%%%%%%%%%%%%%%
\item (6 points) Assuming a downloaded document is safe, what is the probability that at least one of the two extensions marks the download as unsafe?
    \begin{shaded}

    \begin{answer}

       % your answer here

    \end{answer}

    \begin{tabular}{l  p{.5in} p{2in} l}
    In addition to providing an expression above, \\
    please compute an numeric answer:&
    &            % replace with & 0.9999 (keeping ampersand (&) on left, 0.9999 being your answer)
    &  \\
    \cline{3-3}
    \end{tabular}
    \end{shaded}
    
\item (6 points) Assuming a downloaded document is safe, what is the probability that exactly one of the two extensions marks the download as unsafe?
    \begin{shaded}

    \begin{answer}

       % your answer here

    \end{answer}

    \begin{tabular}{l  p{.5in} p{2in} l}
    In addition to providing an expression above, \\
    please compute an numeric answer:&
    &            % replace with & 0.9999 (keeping ampersand (&) on left, 0.9999 being your answer)
    &  \\
    \cline{3-3}
    \end{tabular}
    \end{shaded}
    
\item (10 points) Given that both extensions mark the download as safe, what is the probability that the download is unsafe?
    \begin{shaded}

    \begin{answer}

       % your answer here

    \end{answer}

    \begin{tabular}{l  p{.5in} p{2in} l}
    In addition to providing an expression above, \\
    please compute an numeric answer:&
    &            % replace with & 0.9999 (keeping ampersand (&) on left, 0.9999 being your answer)
    &  \\
    \cline{3-3}
    \end{tabular}
    \end{shaded}    
    
\item (8 points) Are the unconditioned events where the two extensions mark a download as safe independent? Why or why not?
    \begin{shaded}

    \begin{answer}
       % your answer here

    \end{answer}
    \end{shaded}   
    
\end{enumerate}

\section{Doris and Inventory Audits [30 points]}\label{sec:skating}

Jerry's Boston Terrier, Doris, is a San Francisco-based accountant, and much of her work has her auditing retail companies---literally showing up unannounced--to confirm their in-house inventory matches what their inventory software claims. If she finds evidence to suggest there are widespread discrepancies between physical in-store inventory and what's shared with the Internal Revenue Service (that's the U.S. Federal Tax Bureau) via inventory reports, she informs the IRS that a more thorough audit is warranted. \\
\, \\
Assume Doris is auditing a company that maintains separate records for 4500 different items, 4400 of which are accurate and 100 of which are inaccurate. Rather than examining all 4500 records, Doris arbitrarily samples 100 of them (without replacement, 25 per paw). Let $X$ be the random variable counting the number of inaccurate record found among all 100 samples, assuming all samples are equally likely. 

\begin{enumerate}[label=\alph*.]

%%%%%%%%%%%%%%%%%%%%%%
\item (10 points) Compute $p_X(x)$, which is the probability mass function of $X$ as defined above.

    \begin{shaded}
    \begin{answer}
       % your answer here
    \end{answer}
    \end{shaded} 
    
\item (6 points) Compute the expected value of X, i.e. E[X]. You should express your answer as a sum of a finite number of terms (which you share as part of your answer), but then write a short Python program (which need not be included) to compute the summation and present a single numeric value.
    \begin{shaded}
    \begin{answer}
       % your answer here
    \end{answer}
    \begin{tabular}{l  p{.5in} p{2in} l}
    In addition to providing an expression above, \\
    please compute an numeric answer:&
    &            % replace with & 2.99999 (keeping ampersand (&) on left, 2.9999 being your answer)
    &  \\
    \cline{3-3}
    \end{tabular}
    \end{shaded}
\end{enumerate}
To guard against some unlucky sampling, Doris stops if the first sample produces either 0 (she takes that as conclusive) or three or more inaccurate records. If she finds either one or two inaccurate records in her initial sample of 100, she draws a new sample of 100 from the original 4500, just as she did originally, and counts the number of inaccuracies the same exact way.

\begin{enumerate}[label=\alph*.,start=3]
\item (7 points) Let $Y$ be the random variable counting the number of inaccuracies counted between the first and, if needed, second audits. What is $P(Y = 2)$?
    \begin{shaded}

    \begin{answer}

       % your answer here

    \end{answer}

    \begin{tabular}{l  p{.5in} p{2in} l}
    In addition to providing an expression above, \\
    please compute an numeric answer:&
    &            % replace with & 0.9999 (keeping ampersand (&) on left, 0.9999 being your answer)
    &  \\
    \cline{3-3}
    \end{tabular}
    \end{shaded}    
    
\item (7 points) Compute $E[Y]$ in terms of $E[X]$. Your answer should be framed in terms of $E[X]$ instead of the exact value you computed for part b, just in case your answer to part b was incorrect.
    \begin{shaded}

    \begin{answer}
       % your answer here
    \end{answer}
    \end{shaded}   
    
\end{enumerate}
\end{document}