%
% LaTeX Problem Set Template originally designed
% by former CS103 TA Sachin Padmanabhan, with updates,
% edits, and simplifications by the lovely folks below.
%
% 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
% Commands slimmed down and simplified in Fall 2022 by Keith Schwarz

\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{mathdots}
\usepackage{braket}
\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 --- Summer 2024}
\rfoot{\thepage}

\newcommand{\abs}[1]{\lvert #1 \rvert}
\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{\powerset}[1]{\wp\left(#1\right)}
\newcommand{\suchthat}{\ \vert \ }
\newcommand{\naturals}{\mathbb{N}}
\newcommand{\integers}{\mathbb{Z}}
\newcommand{\reals}{\mathbb{R}}
\renewcommand{\qed}{\blacksquare}
\newcommand{\accepts}{\text{ accepts }}
\newcommand{\rejects}{\text{ rejects }}
\newcommand{\loopson}{\text{ loops on }}
\newcommand{\haltson}{\text{ halts on }}
\newcommand{\encoded}[1]{\left\langle#1\right\rangle}
\newcommand{\rlangs}{\mathbf{R}}
\newcommand{\relangs}{\mathbf{RE}}
\newcommand{\corelangs}{\text{co-}\mathbf{RE}}
\newcommand{\plangs}{\mathbf{P}}
\newcommand{\nplangs}{\mathbf{NP}}

\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

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

\usepackage{boxedminipage}
\newenvironment{blank}{\colorbox{shadecolor}{\strut \underline{\ \ \ \ \ }}}

\begin{document}

\maketitle

\begin{center}
  \emph{Due Friday, July 19 at 5: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$.
\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: Strictly Increasing Functions}
    i.
    \begin{shaded}
    Write your answer to Problem Two, part i. here.
    \end{shaded}
    
    ii.
    \begin{shaded}
    Write your answer to Problem Two, part ii. here.
    \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}
    
\newpage

\section*{Problem Three: Independent and Dominating Sets}
    i.
    \begin{shaded}
    Write your answer to Problem Three, part i. here.
    \end{shaded}
    
    ii.
    \begin{shaded}
    Write your answer to Problem Three, part ii. here.
    \end{shaded}
    
    iii.
    \begin{shaded}
    Write your answer to Problem Three, part iii. here.
    \end{shaded}
    
    iv.
    \begin{shaded}
    Write your answer to Problem Three, part iv. here.
    \end{shaded}
    
\newpage

\section*{Problem Four: Left and Right Inverses}
    i.
    \begin{shaded}
    Write your answer to Problem Four, part i. here.
    
    Here is some guidance on how to insert a picture into LaTeX: \href{https://www.overleaf.com/learn/latex/Inserting_Images}{Overleaf Documentation - Inserting Images}
    \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: True Inverses}

    \begin{shaded}
    Write your answer to Problem Five here.
    \end{shaded}

\section*{Problem Six: Bipartite Graphs}
    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}

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