\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{Midterm 2}
\rhead{\textit{Thursday, April 23}}
}
\pagestyle{fancyplain}
\usepackage{paralist}
\begin{document}
\thispagestyle{firstpagestyle}
\begin{center}
{\huge \textbf{Midterm 2}}
{\large \textit{Due: 12:01 am EDT on Thursday, April 23}}
\end{center}
Please do not include any identifying information about yourself in the handin, including your Banner ID.
Be sure to leave \textbf{at least 30 minutes} to upload your answers on Gradescope.
\subsection*{Problem 0}
{\setcounter{enum22i}{0}
Please answer the following questions before you begin. We cannot grade your exam without your answers.
\begin{22enumerate}
\item Do you promise to not consult anyone else (besides the TAs) about this exam?
\item Do you promise to not search for solutions on the Internet?
\item If you have a question about this exam, do you promise to only ask for clarifications via \textbf{private} Piazza posts?
\item Have you double checked when the deadline for this midterm is in your time zone?
\end{22enumerate}}
\newpage
\subsection*{Problem 1}
{
{\setcounter{enum22i}{0}
Based on Duncan's online dictionary, he estimates that:
\begin{itemize}
\item $\Pr(\text{`d' in a word}) = 27.0$\%
\item $\Pr(\text{`k' in a word}) = 7.4$\%
\item $\Pr(\text{`n' in a word}) = 51.4$\%
\end{itemize}
Be sure to show your work for all parts of this problem.
\begin{22enumerate}
\item Assuming the probability a letter appears in a word is independent of the probabilities of any other letters appearing, what's the probability that a word contains any one of `d', `k', or `n'?
\item Duncan has done some further analysis and found that the probability the letters appear are \emph{not} actually independent. Here are some additional estimates:
\begin{itemize}
\item $\Pr(\text{`d' and `k' in a word}) = 1.4$\%
\item $\Pr(\text{`d' and `n' in a word}) = 14.1$\%
\item $\Pr(\text{`k' and `n' in a word}) = 3.1$\%
\item $\Pr(\text{`k' and `n' and `d' in a word}) = 0.7$\%
\end{itemize}
What's the actual probability that a word contains any of `d', `k', or `n'?
\item How many words should Duncan expect to have either a `d', `k', or `n' in an arbitrary 10-word sentence?
\item A sentence is \textit{Dunkin} if every word has a `d', `k', and `n' in it; a sentence is \textit{Baskin} if every word has a `k' or `n' in it.
\begin{enumerate}[i.]
\item What is the probability that a 10-word sentence is Baskin given that it is Dunkin?
\item Using Bayes' Theorem, what about Dunkin given Baskin?
\end{enumerate}
\end{22enumerate}
}
}
\newpage
\subsection*{Problem 2}
{
{\setcounter{enum22i}{0}
An $n$-bit Boolean function $f$ is a map from $0/1$ strings of length $n$ to either
$0$ or $1$, that is, \[f : \{0, 1\}^n \rightarrow \{0, 1\}.\]
For each of the following questions below, justify your answer. You may assume $n \geq 1$.
\begin{22enumerate}
{\setlength\itemindent{20pt} \item Count the total number of $n$-bit Boolean functions.}
{\setlength\itemindent{20pt} \item Count the number of $n$-bit Boolean functions that are injective.}
{\setlength\itemindent{20pt} \item Count the number of $n$-bit Boolean functions that are surjective.}
{\setlength\itemindent{20pt} \item Count the number of $n$-bit Boolean functions that are bijective.}
\end{22enumerate}
An $n$-bit Boolean function depends on $i$ if there exist two $n$-bit strings $A$ and
$B$ such that $A$ and $B$ differ only in position $i$ and $f(A) \neq f(B)$.
\begin{22enumerate}
{\setlength\itemindent{20pt} \item \addtocounter{enumii}{4} Count the number of $n$-bit Boolean functions that do not depend on bit $i$,
for some fixed $i$. That is, the function should return the same value independent of how you set bit $i$.}
\end{22enumerate}
}
}
\newpage
\subsection*{Problem 3}
{
{\setcounter{enum22i}{0}
\begin{22enumerate}
\item
Let $x$ be a proposition whose value can be expressed in terms of the Boolean
variables $p$, $q$, and $r$ with the following input/output table:\\
\begin{tabular}{c | c | c || c}
$p$ & $q$ & $r$ & $x$\\ \hline
1 & 1 & 1 & 1\\
1 & 1 & 0 & 0\\
1 & 0 & 1 & 0\\
1 & 0 & 0 & 0\\
0 & 1 & 1 & 1\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 1\\
0 & 0 & 0 & 0\\
\end{tabular}
Write a proposition $x$ and draw a circuit corresponding to the input/output table given
above. You may use an online tool (such as Google Slides) to diagram your circuit, but not if it checks the answer for you.\\
\item
Recall that in Homework 6 we defined the relation $R$ over $B$, the set of all possible propositions (logical formulas made of variables and logical operators),
such that for $a,b \in B$, $a\;R\;b$ if and only if $a$ and $b$ return the same output given the same input.
\begin{enumerate}[i]
\item On the homework, we told you $R$ was an equivalence relation, but we didn't prove it!
Prove $R$ is an equivalence relation.
\item
As we used it on the homework, the equivalence class of a proposition $x$ is
$[x]_R = \{a \in B \mid a\;R\;x\}$.
Prove that $|[x]_R|$ is infinite for any $x \in B$.
\item
You have a program that randomly generates three-input, one-output propositions.
How many times do you have to run it to guarantee you have a pair of logically equivalent propositions?
Explain your answer.\\
\end{enumerate}
\end{22enumerate}
}
}
\newpage
\subsection*{Problem 4}
{
{\setcounter{enum22i}{0}
Duncan has assembled a group of friends to play the \emph{very} fun
and wholesome game of Screaming Toes
\footnote{http://www.ultimatecampresource.com/site/camp-activity/scream-machine-or-screaming-toes.html}!
The rules of the game are very simple: $n$ players stand in a
circle, and each player looks down and (without looking at anyone else's face)
chooses someone else's toes to look at. Everyone then looks up at their chosen player's
face at the same time; if two players are looking at each other, they are out of the game.
The game then proceeds with the remaining players.
As always, show your work and justify your answers.
\begin{22enumerate}
\item Duncan is playing with $n-1$ other friends. What is the probability that he loses the game in the first round?
\item What is the expected number of \underline{pairs} of players that lose in the first round?
\item Duncan, Tim, Kristy, and Kareem have decided (likely against their best interest) that they will only
look at one of the others in their group of 4 in the first round. Find the probability that all four of them end up
losing.
\end{22enumerate}
}
}
\end{document}