\documentclass[11pt,fleqn]{article}
\usepackage{fullpage}
\usepackage{latexsym,epsf,epsfig}
\usepackage{amsmath,amsthm,amsfonts}
\begin{document}
\def\N{\mathbb{N}}
\def\E{\mathbb{E}}
\def\Var{\operatorname{Var}}
\newtheorem{thm}{Theorem}
\section*{CS 70 homework 13 solutions}
Your full name: PUT YOUR NAME HERE
\newline
Your login name: PUT YOUR LOGIN NAME HERE
\newline
Homework 13
\newline
Your section number: PUT YOUR SECTION NUMBER HERE
\newline
Your list of partners: LIST YOUR PARTNERS HERE
\newline
\begin{enumerate}
\item
\begin{enumerate}
\item[(a)] Let $Z$ be normally distributed with mean 0 and variance $1$.
Use one of the tables or calculator mentioned above to find the
approximate value of $\Pr[Z \ge 3]$.
YOUR ANSWER GOES HERE.
\item[(b)] Suppose $X$ is normally distributed with mean 100 and
standard deviation 10.
Calculate
$\Pr[X\ge 125]$.
YOUR ANSWER GOES HERE.
\item[(c)] Find a value $k$ for which,
when you flip a fair coin 10000 times,
the probability of $k$ or more heads is approximately $0.20$.
YOUR ANSWER GOES HERE.
\end{enumerate}
\item
Determine whether the following sets are countable or uncountable.
For each countable set, display a one-to-one correspondence
between the set of natural numbers and that set, or an enumeration
of the set.
For each uncountable set, explain why it is uncountable.
\begin{enumerate}
\item
The set of binary strings which are palindromes. A string $s$ is a
palindrome if it can be written as the concatenation of some string $t$
followed by the reversal of $t$.
YOUR ANSWER GOES HERE.
\item
The set of real numbers in the interval [0,1] whose decimal
representation contains a single ``1'' digit, and all other digits are ``0''.
YOUR ANSWER GOES HERE.
\item
The set of real numbers in the interval [0,1] whose decimal
representation contains only ``0'' and ``1'' digits (mixed in any order or
combination).
YOUR ANSWER GOES HERE.
\item
The set of rooted, finite binary trees,
in which trees are distinguished only by their
shape (that is, you should ignore node values).
YOUR ANSWER GOES HERE.
\end{enumerate}
\item
Show that the Cantor set is uncountably infinite.
YOUR ANSWER GOES HERE.
\item
Let $S$ denote
the set of functions from $\N$ to the set
$\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$.
Show that $S$ is uncountable.
YOUR ANSWER GOES HERE.
\item
The expected number of comparisons [used by QuickSelect]---call it $T(n)$---is
less than $4n$.
Prove it.
YOUR ANSWER GOES HERE.
\end{enumerate}
\end{document}