\documentclass[letterpaper,11pt]{article}

\newcommand{\removefromfile}[1]{}

\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\usepackage{amsmath}
\usepackage{enumitem}
\usepackage{hyperref}
\usepackage[most]{tcolorbox}
\renewcommand{\theenumi}{\alph{enumi}}
\begin{document}
\title{{\bf Problem Set 3 Solutions} }
\author{Name: TODO}

\date{}
\maketitle

\section*{Collaborators}
\begin{tcolorbox}
    List collaborators, if any. 
\end{tcolorbox}

\section*{Use of 312 Learning Assistant}
\begin{tcolorbox}
    List which problems you used the 312 Learning Assistant on.
\end{tcolorbox}

\newpage
\section{Gradescope Problems (30 points)}
\begin{tcolorbox}
    Nothing to write for this question.
\end{tcolorbox}

\newpage

\section{Miscounting (10 points)}

Consider the question:  what is the probability of getting a \textbf{7-card} poker hand (order doesn't matter) that contains at least two 3-of-a-kind (3-of-a-kind means three cards of the same rank).
For example, this would be a valid hand: ace of hearts, ace of diamonds, ace of spades, 7 of clubs, 7 of spades, 7 of hearts and queen of clubs.
(Note that a hand consisting of all 4 aces and three of the 7s is also valid.) 

Here is how we might compute this:

\begin{quote} Each of the $\binom{52}{7} $ hands is equally likely.
Let $E$ be the event that the hand selected contains at least two 3-of-a-kinds.
Then \[\Pr(E) = \frac{|E|}{\binom{52 }{ 7}}\]
To compute $|E|$, apply the product rule.
First pick two ranks that have a 3-of-a-kind (e.g. ace and 7 in the example above).
For the lower rank of these, pick the suits of the three cards.
Then for the higher rank of these, pick the suits of the three cards.
Then out of the remaining $52-6 = 46$ cards, pick one.
Therefore \[|E|= \binom{13 }{ 2} \cdot \binom{4 }{ 3}\cdot \binom{4 }{ 3} \cdot \binom{46 }{ 1} \quad \quad  \text{ and hence }
\quad\quad \Pr(E) = \frac{\binom{13 }{ 2}\cdot 4^2 \cdot 46}{\binom{52 }{ 7}}.\]
\end{quote}

\textbf{Explain what is wrong with this solution}.
If there is over-counting in $|E|$, characterize all hands that are counted more than once, and how many times each such hand is counted.
If there is under-counting in $|E|$, explain which hands are not counted.
Also, \textbf{give the correct answer for $\Pr(E)$.}

\begin{tcolorbox}
    TODO: Your solution here.
\end{tcolorbox}

\newpage

\section{You knew it all along! (10 points)}
You are taking a multiple choice test that has 4 answer choices for each task.
In answering a task on this test, the probability you know the correct answer is $p$.
If you know the correct answer, you will definitely select it.
If you don't know the correct answer, you choose one (uniformly) at random.
What is the probability that you knew the correct answer to a task, given that you answered it correctly?
Use Bayes Theorem, and use the following names for the relevant events, e.g.
let $K$ be the event that you know the correct answer and let $C$ be the event that you answer the task correctly (whether you knew the answer or not).

\begin{tcolorbox}
    TODO: Your solution here.
\end{tcolorbox}

\newpage

\section{Doggone, Doggtwo, Doggthree\ldots  (10 points)}
A hunter has two hunting dogs.
One day, on the trail of some animal, the hunter comes to a place where the road diverges into two paths.
She knows that 
each dog, independent of the other, will choose the correct path with probability $p$.
The hunter decides to let each dog choose a path, and if they agree, take that one, and
if they disagree, to randomly pick a path.
What is the probability that she ends up taking the correct path?
Hint: Use the law of total probability, partitioning based on whether the dogs choose the same path or different paths.

\begin{tcolorbox}
    TODO: Your solution here.
\end{tcolorbox}

\newpage

\section{Aces (12 points)}
Suppose that an ordinary deck of 52 cards (which contains 4 aces) is randomly divided into 4 hands of 13 cards each.
We are interested in determining $p$, the probability that each hand has an ace.
Let $E_i$ be the event that the $i$-th hand has exactly one ace.
Determine \[p = \Pr
(E_1\cap E_2 \cap E_3 \cap E_4)\] using the chain rule.
\begin{enumerate}
    \item (3 points) What is $\Pr[E_1]$, the probability that our first hand has exactly one ace?

    \begin{tcolorbox}
    TODO: Your solution here.
    \end{tcolorbox}

    \item (3 points) Given that $E_1$ has occurred, there are now $39$ cards left in the deck, with $3$ of them aces. What is $\Pr[E_2\mid E_1]$?

    \begin{tcolorbox}
    TODO: Your solution here.
     \end{tcolorbox}
  
    \item (6 points) Continue this argument for $\Pr[E_3\mid E_1,E_2]$ and $\Pr[E_4\mid E_1,E_2,E_3]$, and use the chain rule to compute $p$.

    \begin{tcolorbox}
    TODO: Your solution here.
    \end{tcolorbox}

\end{enumerate}

\newpage

\section{Naive Bayes \textbf{[Coding]} (25 points)}
Use the Naive Bayes Classifier to implement a spam filter that learns
word spam probabilities from our pre-labeled training data and then
predicts the label (ham or spam) of a set of emails that it hasn't
seen before.

For an introduction to the Naive Bayes Classifier and details on implementation, see the video and slides (as well as some self-check questions) linked at \href{https://edstem.org/us/courses/96846/lessons/162350/slides/963143}{this edstem lesson}. Also check out Section 9.3 from \href{https://www.alextsun.com/files/Prob_Stat_for_CS_Book.pdf}{the book}.
To solve the task, we have set up an \href{https://edstem.org/us/courses/96846/lessons/162343/slides/954052}{edstem lesson}.
In particular, write your code to implement the functions {\tt fit} and {\tt predict} in the provided file, \href{https://edstem.org/us/courses/96846/lessons/162343/slides/954052}{\tt{cse312\_pset3\_nb.py}}.
\smallskip

You will be able to run your code directly within edstem, and to test it, using the ``Mark'' option.
This, however, will not evaluate your solution. Instead, once you're ready to submit, you can right-click the files in the directory to download them.
Please upload your completed {\tt cse312\_pset3\_nb.py } to Gradescope under ``PSet3 [Coding]''.
\medskip

    \textbf{ Some notes and advice:}
    
    \begin{itemize}
        \item Read about how to avoid floating point underflow using the log-trick as described in these     \href{https://courses.cs.washington.edu/courses/cse312/18sp/lectures/naive-bayes/naivebayesnotes.pdf}{notes}.
\item Make sure you understand how Laplace smoothing works.
        \item Remember to remove any debug statements that you are
          printing to the output.
\item \textbf{Do not directly manipulate file paths or use
          hardcoded file paths.}  A file path you have hardcoded into
          your program that works on your
          computer won't work on the computer we use to test your
          program.
\item Needless to say, you should practice what you've learned
          in other courses: 
        document your program, use good variable names, keep your code
        clean and straightforward, 
        etc.  Include comments outlining what your program does and
        how.
We will not spend time 
        trying to decipher obscure, contorted code.
Your score on Gradescope is your final score, as you have unlimited attempts.
\item We will evaluate your code on data you don't have access to, in addition to the data you are given.
\item Remember, it is not expected that Naive Bayes will classify every single
    test email correctly, but it should certainly do better than random chance!
As this algorithm is deterministic, you should get a certain specific test accuracy around 90-95\%, which we will be testing for to ensure your algorithm is correct.
Note that we will run your code on a test dataset you haven't seen, but you will know immediately if you got full score.
\item \textbf{Start early!}
\end{itemize}

\begin{tcolorbox}
    Nothing to write for this question.
\end{tcolorbox}

\newpage

\section{For Fun Problem (will not be graded)}
\textbf{This is a not-too-difficult problem for those of you that would enjoy proving a cool probabilistic fact. 
You will not be turning anything in for this. }  

\medskip
You are shown two envelopes and told the following facts:
\begin{itemize}
\item Each envelope has some number of dollars in it, but you don't know how many.
\item The amount in the first envelope is different from the amount in
the second.
\item Although you don't know exactly how much money is in each envelope, you are told that it is an integer number of dollars that is at least 1 and at most 100. 
\item You are told that you can pick an envelope, look inside, and then you will be given a one-time option to switch envelopes (without looking inside the new envelope). You will then be allowed to keep the money in envelope you end up with.

\end{itemize}

Your strategy is the following:
\begin{enumerate}
\item You pick an envelope uniformly at random.
\item You open it and count the amount of money inside. Say the result is $x$.
\item You then select an integer $y$ between 1 and 100 uniformly at random.
\item If $y > x$, you switch envelopes, otherwise you stay with the envelope you picked in step (a)
\end{enumerate}
Show that you have a better than 50-50 chance of taking home the envelope with the larger amount of money in it. More specifically, suppose the two envelopes have $i$ and $j$ dollars in them respectively, where $i < j$.
Calculate the probability that you take home the envelope with the larger amount of money.

\begin{tcolorbox}
    Nothing to write for this question.
\end{tcolorbox}

\end{document}