%
% 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 \#8}
\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 8}
\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, November 19 at 2:30 pm Pacific}
\end{center}

Do not put your answers to Problems 1, 2.ii, 3.ii, or 4 in this file.

Symbols you might find helpful in this problem set:

\begin{itemize}
    \item Language derivatives use the notation $\partial_w L$.
    \item Distinguishability is written as $x \not\equiv_L y$.
\end{itemize}

\pagebreak

\section*{Problem Two: The Complexity of Addition}
    i.
    \begin{shaded}
    Write your answer to Problem Two, part i. here.
    \end{shaded}

\newpage

\section*{Problem Three: Brzozowski’s Theorem}
    i.
    \begin{shaded}
    1. Write your answer to Problem Three, part i., question 1 here. \\
    2. Write your answer to Problem Three, part i., question 2 here. \\
    3. Write your answer to Problem Three, part i., question 3 here. 
    \end{shaded}
    
    iii.
    \begin{shaded}
    Write your answer to Problem Three, part iii. here.
    \end{shaded}

\newpage


\section*{Problem Five: Executable Computability Theory}
    i.
    \begin{shaded}
    \begin{itemize}
    \item Write your answer to Problem Five, part i., first bullet point here.
    \item Write your answer to Problem Five, part i., second bullet point here.
    \item Write your answer to Problem Five, part i., third bullet point here. 
    \end{itemize}
    \end{shaded}
    
    ii.
    \begin{shaded}
    \begin{itemize}
    \item Write your answer to Problem Five, part ii., first bullet point here.
    \item Write your answer to Problem Five, part ii., second bullet point here.
    \item Write your answer to Problem Five, part ii., third bullet point here. 
    \end{itemize}
    \end{shaded}
    
    iii.
    \begin{shaded}
    \begin{itemize}
    \item Write your answer to Problem Five, part iii., first bullet point here.
    \item Write your answer to Problem Five, part iii., second bullet point here.
    \item Write your answer to Problem Five, part iii., third bullet point here. 
    \end{itemize}
    \end{shaded}
    
\newpage

\section*{Problem Six: What Does it Mean to Solve a Problem?}
    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}
    
\newpage

\section*{Optional Fun Problem: TMs and Regular Languages}
\begin{shaded}
Write your answer to the Optional Fun Problem here.
\end{shaded}

\end{document}
