% This template was designed by Victor Lin.
% Please contact victorlin@cs.stanford.edu if you have any questions or feedback!

% This is a comment!

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

% these are some useful packages. these add functionality to your document
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{mathdots}
\usepackage[pdftex]{graphicx}
\usepackage{fancyhdr}
%\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}
\usepackage{amsmath}  % math symbols
\usepackage{wrapfig}  % in case you want to use a figure
\usepackage{hyperref} % add hyper links

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

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

\lhead{author}
\chead{Problem Set \#1}
\rhead{\today}

\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}
\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}
\DeclareMathOperator{\Ber}{Bernoulli}
\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{\N}{\mathbb{N}}
\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}}

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

\definecolor{shadecolor}{gray}{0.95}

\setlength{\parindent}{0pt}

\pagestyle{fancy}

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

% begin the document
\begin{document}

% actually insert the title.
\maketitle
  
\begin{enumerate}
\large{
    %1
    \item A substitution cipher is derived from an ordering of the letters in the alphabet. How many ways can the 26 letters be ordered if each letter appears exactly once and:
    \begin{enumerate}
        \item There are no other restrictions?
        \item The letters Q and U must be next to each other (but in any order)?
    \end{enumerate}
    
    \begin{shaded}
    \begin{answer}
    % Write your answer here!
    \end{answer}
    \end{shaded}
    \newpage
    %2
    \item You are counting cards in a card game that uses \textbf{four} standard decks of cards. There are 208 cards total. Each deck has 52 cards (13 values each with 4 suits). Cards are only distinguishable based on their suit and value, not which deck they came from.
    \begin{enumerate}
        \item In how many distinct ways can the cards be ordered?
        \item You are dealt two cards. How many distinct pairs of cards can you be dealt? Note: the order of the two cards you are dealt does not matter.
    \end{enumerate}
    
    \begin{shaded}
    \begin{answer}
    
    \end{answer}
    \end{shaded}
    \newpage
    %3
    \item Imagine you have a robot that lives on an $n \times m$ grid (it has $n$ rows and $m$ columns): \\
    \begin{center}
    \begin{tabular}{c|c|c|c|c|c|}
        \cline{2-6}
         & & & & & D \\
        \cline{2-6}
         & & & & & \\
        \cline{2-6}
        \textbf{n} & & & & & \\
        \cline{2-6}
         & $\Theta$ & & & & \\
        \cline{2-6}
        \multicolumn{1}{c}{} & \multicolumn{5}{c}{\textbf{m}}
    \end{tabular} \\
    \end{center}
    The robot starts in cell (1, 1) and can take steps either to the right or up (no left or down steps). How many distinct paths can the robot take to the destination in cell ($n$, $m$):
    \begin{enumerate}
        \item If there are no additional constraints?
        \item The robot must start by moving to the right?
        \item If the robot changes direction exactly 3 times? As an example: moving up two times in a row is not changing directions but switching from moving up to moving right is. Moving (Up, Right, Right, Up) would count as having two direction switches.
    \end{enumerate}
    
    \begin{shaded}
    \begin{answer}
    
    \end{answer}
    \end{shaded}
    \newpage
    %4
    \item Given all the start-up activity going on in high-tech, you realize that applying combinatorics to investment strategies might be an interesting idea to pursue. Say you have \$20 million that must be invested among 4 possible companies. Each investment must be in integral units of \$1 million, and there are minimal investments that need to be made if one is to invest in these companies. The minimal investments are \$1, \$2, \$3, and \$4 million dollars, respectively for company 1, 2, 3, and 4. How many different investment strategies are available if
    \begin{enumerate}
        \item an investment must be made in each company?
        \item investments must be made in at least 3 of the 4 companies?
        \item an investment must be made in each company, but not all of the money needs to be invested? (Hint: see example 8 on lecture notes 2.)
    \end{enumerate}
    
    \begin{shaded}
    \begin{answer}
    
    \end{answer}
    \end{shaded}
    \newpage
    %5
    \item If we assume that all possible poker hands (comprised of 5 cards from a standard 52 card deck) are equally likely, what is the probability of being dealt:
    \begin{enumerate}
        \item a flush? (A hand is said to be a flush if all 5 cards are of the same suit. Note that this definition means that straight flushes (five cards of the same suit in numeric sequence) are also considered flushes.)
        \item one pair? (This occurs when the cards have numeric values $a$, $a$, $b$, $c$, $d$, where $a$, $b$, $c$, and $d$ are all distinct.)
        \item two pairs? (This occurs when the cards have numeric values $a$, $a$, $b$, $b$, $c$, where $a$, $b$ and $c$ are all distinct.)
        \item three of a kind? (This occurs when the cards have numeric values $a$, $a$, $a$, $b$, $c$, where $a$, $b$ and $c$ are all distinct.)
        \item four of a kind? (This occurs when the cards have numeric values $a$, $a$, $a$, $a$, $b$.)
    \end{enumerate}
    
    \begin{shaded}
    \begin{answer}
    
    \end{answer}
    \end{shaded}
    \newpage
    %6
    \item Say we roll a fair 6-sided die six times, what is the probability that:
    \begin{enumerate}
        \item we will roll three different numbers, \textit{twice} each?
        \item we will roll some number \textit{exactly} 4 times?
    \end{enumerate}

    
    \begin{shaded}
    \begin{answer}
    
    \end{answer}
    \end{shaded}
    \newpage
    %7
    \item To get good performance when working binary search trees (BST), we must consider the probability of producing completely degenerate BSTs (where each node in the BST has at most one child).
    \begin{enumerate}
        \item If the integers 1 through $n$ are inserted in arbitrary order into a BST (where each possible order is equally likely), what is the probability (as an expression in terms of $n$) that the resulting BST will have completely degenerate structure?
        \item Using your expression from part (a), determine the smallest value of $n$ for which the probability of forming a completely degenerate BST is less than 0.01 (i.e., 1\%). Feel free to just plug increasing/decreasing numbers into your expression from part a.
    \end{enumerate}
    
    \begin{shaded}
    \begin{answer}
    
    \end{answer}
    \end{shaded}
    \newpage
    %8
    \item Say a hacker has a list of $n$ distinct password candidates, only one of which will successfully log her into a secure system.
    \begin{enumerate}
        \item If she tries passwords from the list at random, deleting those passwords that do not work, what is the probability that her first successful login will be (exactly) on her $k$-th try?
        \item Now say the hacker tries passwords from the list at random, but does \textbf{not} delete previously tried passwords from the list. She stops after her first successful login attempt. What is the probability that her first successful login will be (exactly) on her $k$-th try?
    \end{enumerate}
    
    \begin{shaded}
    \begin{answer}
    
    \end{answer}
    \end{shaded}
    \newpage
    %9
    \item Say a university is offering 3 programming classes: one in Java, one in C++, and one in Python. The classes are open to any of the 100 students at the university. There are:
    \begin{itemize}
        \item a total of 27 students in the Java class
        \item a total of 26 students in the C++ class
        \item a total of 18 students in the Python class
        \item 12 students in both the Java and C++ classes
        \item 5 students in both the Java and Python classes
        \item 7 students in both the C++ and Python classes
        \item 3 students in all three classes (note: these students are also counted as being in each pair of classes in the numbers above).
    \end{itemize}
    
    \begin{enumerate}
        \item If a student is chosen randomly at the university, what is the probability that he or she is not in any of the 3 programming classes?
        \item If a student is chosen randomly at the university, what is the probability that he or she is taking exactly one of the three programming classes?
        \item If two students are chosen randomly at the university, what is the probability that at least one of the chosen students is taking at least one programming class?
    \end{enumerate}
    \begin{shaded}
    \begin{answer}
    
    \end{answer}
    \end{shaded}
    \newpage
    %10
    \item A binary string containing $M$ 0's and $N$ 1's (in arbitrary order, where all orderings are equally likely) is sent over a network. What is the probability that the first $r$ bits of the received message contain exactly $k$ 1's?
    
    \begin{shaded}
    \begin{answer}
    
    \end{answer}
    \end{shaded}
    \newpage
    %11
    \item Suppose that $m$ strings are hashed (randomly) into $N$ buckets, assuming that all $N^m$ arrangements are equally likely. Find the probability that exactly $k$ strings are hashed to the first bucket. 
    
    \begin{shaded}
    \begin{answer}
    
    \end{answer}
    \end{shaded}
    \newpage
    
    %12
    \item \textbf{[Coding]} Consider a game that uses a generator which produces independent random integers between 1 and 100 inclusive. The game starts with a sum $S = 0$. The first player adds random numbers from the generator to $S$ until $S > 100$ and records her last random number $x$. The second player continues adding random numbers from the generator to $S$ until $S > 200$ and records her last random number $y$. The player with the highest number wins, i.e. if $y > x$ the second player wins. Is this game fair? Write a program to simulate 100,000 games. What is the probability estimate, based on your simulations, that the second player wins? Give your answer rounded to 3 places behind the decimal. For an extra credit challenge, give an expression for the exact probability (without sampling).\\
    
    Please include any code that you wrote. If you're using Latex, we recommend the ``verbatim" environment (or any environment designed to display code). Screenshots are another common method.
    
    \begin{shaded}
    \begin{answer}
    
    \end{answer}
    \end{shaded}
    
}
\end{enumerate}


\end{document}