%
% LaTeX Problem Set Template originally designed
% by former CS103 TA Sachin Padmanabhan.
%
% Updated for Fall 2018 by Michael Zhu
% Updated for Fall 2019 by Joshua Spayd
% Updated for Fall 2020 by Lucy Lu
% Updated for Winter/Spring 2021 by Cynthia Bailey Lee
% Updated for Fall 2021 by Grant McClearn

\documentclass{article}
\usepackage{amsmath}
\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{wasysym}
\usepackage[thinlines]{easytable}
\usepackage{hyperref}
\usepackage{wrapfig}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,
    urlcolor=blue,
}

\title{CS 103: Mathematical Foundations of Computing\\Problem Set \#3}
\author{[TODO: Replace this with your name(s)]}
\date{\today}

% Running author based on https://tex.stackexchange.com/questions/68308/how-to-add-running-title-and-author#answer-68310
\makeatletter
\let\runauthor\@author
\makeatother

\lhead{\runauthor}
\chead{Problem Set 3}
\rhead{\today}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Fall 2021}
\rfoot{\thepage}

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

% start MZ
\let\oldemptyset\emptyset
\renewcommand{\emptyset}{\text{\O}}
\renewcommand{\labelitemii}{$\bullet$}
\renewcommand\qedsymbol{$\blacksquare$}
\newenvironment{prf}{{\bfseries Proof.}}{\qedsymbol}
\renewcommand{\emph}[1]{\textit{\textbf{#1}}}
\newcommand{\annotate}[1]{\textit{\textcolor{blue}{#1}}}
\usepackage{mdframed}
\usepackage{float}

\makeatother
% end MZ

\definecolor{shadecolor}{gray}{0.95}

\theoremstyle{plain}
\newtheorem*{lem}{Lemma}

\theoremstyle{plain}
\newtheorem*{claim}{Claim}

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

\newtheorem{theorem}{Theorem}[section]
\newtheorem*{thm}{Theorem}
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{lemma}[theorem]{Lemma}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\setlength{\parindent}{0pt}

\pagestyle{fancy}

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

% Lucy
\usepackage{boxedminipage}
\newenvironment{blank}[1]{\colorbox{shadecolor}{\strut \underline{\hspace{#1}}}}
% Lucy

\begin{document}

\maketitle

\begin{center}
  \emph{Due Friday, October 15 at 2:30 pm Pacific}
\end{center}

\vspace{1cm}

Problem One is autograded. You won't include your answers to that problem here.

\section*{Symbols Reference}
Here are some symbols that may be useful for this problem set. If you are using \LaTeX, view this section in the template file (the code in \texttt{ps3-latex-template.tex}, not the PDF) and copy-paste math code snippets from the list below into your responses, as needed. If you are typing your problem set in another program such as Microsoft Word, you should be able to copy some of the symbols below from this PDF and paste them into your program. Unfortunately the symbols with a slash through them (for ``not'') and font formats such as exponents don't usually copy well from PDF, but you may be able to type them in your editor using its built-in tools.
\begin{itemize}
    \item $f$ is a function from $A$ to $B$: $f : A \to B$.
    \item $\clubsuit$ and $\heartsuit$ are needed for Problem Three.
\end{itemize}

\LaTeX typing tips:
\begin{itemize}
    \item Set (curly braces need an escape character backslash): ${1, 2, 3}$ (incorrect), $\{1, 2, 3\}$ (correct)
    \item Exponents (use curly braces if exponent is more than 1 character): $x^2$, $2^{3x}$
    \item Subscripts (use curly braces if subscript is more than 1 character): $x_0$, $x_{10}$
\end{itemize}

\newpage

\section*{Problem Two: Iterated Functions, Part One}
    i.
    \begin{shaded}
    Write your answer to Problem Two, part i. here.
    \end{shaded}
    
    ii. Fill in the blanks to Problem Two, part ii. below.
    \begin{shaded}
	1. $f^3(2) = \blank{1cm}$

	2. $f^{137}(1) = \blank{1cm}$

	3. $f^0(137) = \blank{1cm}$
    \end{shaded}
    
    iii.
    \begin{shaded}
    Write your answer to Problem Two, part iii. here.
    \end{shaded}
    
    iv.
    \begin{shaded}
    Write your answer to Problem Two, part iv. here.
    \end{shaded}
    
    v.
    \begin{shaded}
    Write your answer to Problem Two, part v. here.
    \end{shaded}
    
    vi.
    \begin{shaded}
    Write your answer to Problem Two, part vi. here.
    \end{shaded}
    
    vii.
    \begin{shaded}
    Write your answer to Problem Two, part vii. here.
    \end{shaded}
    
    viii.
    \begin{shaded}
    Write your answer to Problem Two, part viii. here.
    \end{shaded}
    
\newpage

\section*{Problem Three: Infinity Times Two}
    i. Fill in the blank to Problem Three, part i. below.
    \begin{shaded}
    $f(n, x) = \blank{1cm}$
    \end{shaded}
    
    ii.
    \begin{shaded}
    Write your answer to Problem Three, part ii. here.
    \end{shaded}
    
\newpage

\section*{Problem Four: Monotone Functions}
    i.
    \begin{shaded}
    Write your answer to Problem Four, part i. here.
    \end{shaded}
    
    ii.
    \begin{shaded}
    Write your answer to Problem Four, part ii. here.
    \end{shaded}
    
    iii.
    \begin{shaded}
    Write your answer to Problem Four, part iii. here.
    \end{shaded}
    
    iv.
    \begin{shaded}
    Write your answer to Problem Four, part iv. here.
    \end{shaded}

\newpage


\section*{Problem Five: Idempotent Functions}
    i.
    \begin{shaded}
    Write your answer to Problem Five, part i. here.
    \end{shaded}
    
    ii.
    \begin{shaded}
    Write your answer to Problem Five, part ii. here.
    \end{shaded}
    
    iii.
    \begin{shaded}
    Write your answer to Problem Five, part iii. here.
    \end{shaded}
    
    iv.
    \begin{shaded}
    Write your answer to Problem Five, part iv. here.
    \end{shaded}
    
\newpage

\section*{Problem Six: Understanding Diagonalization}
    i.
    \begin{shaded}
    Write your answer to Problem Six, part i. here.
    \end{shaded}
    
    ii.
    \begin{shaded}
    Write your answer to Problem Six, part ii. here.
    \end{shaded}
    
    iii.
    \begin{shaded}
    Write your answer to Problem Six, part iii. here.
    \end{shaded}
    
    iv.
    \begin{shaded}
    Write your answer to Problem Six, part iv. here.
    \end{shaded}
    
    v.
    \begin{shaded}
    Write your answer to Problem Six, part v. here.
    \end{shaded}
    
\newpage

\section*{Problem Seven: Simplifying Cantor's Theorem?}
\begin{shaded}
Write your answer to Problem Seven here.
\end{shaded}

\newpage

\section*{Problem Eight: Iterated Functions, Part Two}
    i.
    \begin{shaded}
    Write your answer to Problem Eight, part i. here.
    \end{shaded}
    
    ii.
    \begin{shaded}
    Write your answer to Problem Eight, part ii. here.
    \end{shaded}

\newpage

\section*{Optional Fun Problem: Infinity Minus Two}
\begin{shaded}
Write your answer to the Optional Fun Problem here.
\end{shaded}
    
\end{document}/staff/ps3
