\documentclass[12pt,letterpaper]{article}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amscd}
\usepackage{enumerate}
\usepackage{fancyhdr}
\usepackage{mathrsfs}
\usepackage{bbm}
\usepackage{framed}
\usepackage{mdframed}
\usepackage{cancel}
\usepackage{mathtools}
\usepackage{verbatim}
\usepackage[letterpaper,voffset=-.5in,bmargin=3cm,footskip=1cm]{geometry}
\setlength{\parindent}{0.0in}
\setlength{\parskip}{0.1in}
\allowdisplaybreaks
\headheight 15pt
\headsep 10pt
\newcommand\N{\mathbb N}
\newcommand\Z{\mathbb Z}
\newcommand\R{\mathbb R}
\newcommand\Q{\mathbb Q}
\newcommand\lcm{\operatorname{lcm}}
\newcommand\setbuilder[2]{\ensuremath{\left\{#1\;\middle|\;#2\right\}}}
\newcommand\E{\operatorname{E}}
\newcommand\V{\operatorname{V}}
\newcommand\Pow{\ensuremath{\operatorname{\mathcal{P}}}}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newcommand\hint[1]{\textbf{Hint}: #1}
\newcommand\note[1]{\textbf{Note}: #1}
\newcounter{enum22i}
\newenvironment{22enumerate}{\begin{enumerate}[a.]\itemsep0em\setcounter{enumi}{\value{enum22i}}}{\setcounter{enum22i}{\value{enumi}}\end{enumerate}}
\newenvironment{22itemize}{\begin{itemize}\itemsep0em}{\end{itemize}}
\fancypagestyle{firstpagestyle} {
\renewcommand{\headrulewidth}{0pt}
\lhead{\textbf{CSCI 0220}}
\chead{\textbf{Discrete Structures and Probability}}
\rhead{M. Littman}
}
\fancypagestyle{fancyplain} {
\renewcommand{\headrulewidth}{0pt}
\lhead{\textbf{CSCI 0220}}
\chead{Homework 8}
\rhead{\textit{Wednesday, April 15}}
}
\pagestyle{fancyplain}
\begin{document}
\thispagestyle{firstpagestyle}
\begin{center}
{\huge \textbf{Homework 8}}
{\large \textit{Due: Wednesday, April 15}}
\end{center}
All homeworks are due at 12:55 PM on Gradescope.
Please do not include any identifying information about yourself in the handin, including your Banner ID.
Be sure to fully explain your reasoning and show all work for full credit.
\subsection*{Problem 1}
{
\nopagebreak
{\setcounter{enum22i}{0}
`Hash functions' are very important in computer science, particularly for
data structures such as hash tables that rely upon them to store and look up
elements in memory. A hash function is any function that maps values from
a large domain to a much smaller codomain. For example, $H: \Z \to \{0,1,2,3,4\};
\ H(x) = \text{rem}(x,5)$. This particular function might be useful to map
arbitrary integers into a table with 5 entries.
The (general) key to a good hash function is to map inputs as evenly as
possible among the possible output valuesâ€“- that is, the probability of
generating a particular output given an arbitrary input should be as close
to the same as possible for all outputs. This is necessary to minimize the
number of `collisions': multiple inputs mapping to the same output.
\footnote{If you are interested in further exploring what makes a good hash
function-- in particular, what makes good \emph{families} of hash functions,
consider taking CS157: Design and Analysis of Algorithms}
Consider the hash function \[H: \Z \to \{0,1,2,3,4,5\}; \ H(x) =
\text{rem}(x,6).\]
\begin{22enumerate}
\item What is the probability that a collision will occur when hashing
three input integers between 1 and $6^{100}$ (inclusive) chosen independently
and uniformly at random?
\item Modifying the function greatly distorts the otherwise uniform
probabilities of its outputs. Consider the general formula $H(x) =
\text{rem}(ax, m)$. You might get this sort of situation if there is regularity
in the inputs, like they all share a common multiple.
Given an arbitrary $a$, explain how to choose a value
for $m$ that will minimize the probability of collisions when hashing.
\hint{Consider how the output values with a nonzero probability of
occurring relate to $a$ and $m$}.
\end{22enumerate}
}
}
\subsection*{Problem 2}
{
\nopagebreak
{\setcounter{enum22i}{0}
Donnah plays the following game. She flips a coin repeatedly.
The coin has a probability $p$ of turning up heads. She wins the game
if heads appears at least $m$ times before tails has appeared $n$
times; otherwise, she loses. Find the probability that
she wins the game in terms of $m$, $n$, and $p$. You can leave your answer
as a summation.
\hint{Think about how you'd count up the number of ways the coin can
be flipped so that the losing condition doesn't happen.}
}
}
\subsection*{Problem 3}
{
\nopagebreak
{\setcounter{enum22i}{0}
Duncan wants to choose a donut to eat, but he is very indecisive! In front of him is a line of $n$ different
donuts. However, we do not know the value of $n$, only that $n$ is a positive integer.
Duncan wants to select a donut \textbf{uniformly at random}. He uses the following strategy as
he walks down the line of donuts.
\begin{22itemize}
\item Upon arriving at donut $1$, Duncan will choose it and put it on his plate.
\item Upon arriving at donut $2$, Duncan will replace the current donut with donut $2$ with
probability $\frac{1}{2}$.
$\vdots$
\item Upon arriving at donut $i$, Duncan will dump the current donut and replace it with
donut $i$ with probability $\frac{1}{i}$.
$\vdots$
\item Upon arriving at donut $n$, with probability $\frac{1}{n}$ Duncan will dump the current
donut and replace it with donut $n$.
\end{22itemize}
Prove that by the time Duncan reaches the end of the line, the donut he has will have been selected
uniformly at random from all $n$ donuts. In other words, a given donut will be on Duncan's plate at the end of the line with probability $\frac{1}{n}$.
}
}
\subsection*{Problem 4}
{
\nopagebreak
{\setcounter{enum22i}{0}
At the the donut factory, produced donuts are sometimes invalid.
A detection system was implemented consisting of $n$ taste testers,
each operating independently with a probability of .9 of successfully
detecting an invalid donut.
\begin{enumerate} [a.]
\item If $n = 5$ and the current donut is invalid, what is the
probability that \textbf{exactly four} taste-testers label the donut as
invalid?
\item Assuming that the donut is invalid, how large must $n$ be in order
for the probability of detecting the invalid donut to be .999? .9999?
\end{enumerate}
}
}
\subsection*{Problem 5}
{
\nopagebreak
{\setcounter{enum22i}{0}
When it's safe to do so, your friendly CS22 TAs get together every week to eat donuts
(and grade your homework). Last week, Dunkin' Donuts had a promotional sale that the
TAs could not pass up. Their ad reads:
\textit{``Buy 2 donuts at the regular price, and get unlimited toppings on each (from the 11 toppings possible) absolutely free (no double toppings).
That's 4,194,304 different ways to design your order!"}
The writer of the ad was no stranger to counting. They
reasoned that the number of ways to choose different toppings for one donut is all
the possible subsets of the set of 11 toppings, which is $2^{11}$. Since there are
two donuts, they reasoned that the total possible combinations of donuts is
$(2^{11})^2=4,194,304$.
Unfortunately, the writer of the ad suffered the grave misfortune of never having
taken CS22, and alas, the number $(2^{11})^2$ is actually wrong. Can you help them
get it right?
\begin{22enumerate}
\item Explain what is wrong with the ad writer's counting.
\item In how many ways can you really choose toppings for the two donuts?
\item One of the TAs has a nut allergy. What is the probability that the TA will be able
to take a bite from a single donut if there are 4 nut toppings and the toppings for the donut
are chosen at random?
\item What is the probability the nut-allergic TA will be able to eat a donut if $n$ donuts are ordered with their toppings chosen at random?
\end{22enumerate}
}
}
\end{document}