%
% LaTeX Problem Set Template by Sachin Padmanabhan
% I created this when I was a freshman in CS 103,
% and I continue to use it to this day.
%
% Hope you enjoy!
%
% There may be problems with this template.
% If so, feel free to contact me.
%
% Updated for Summer 2019 by Amy Liu
\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[table]{xcolor}
\usepackage{pdfpages}
\usepackage{algpseudocode}
\usepackage{tikz}
\usepackage{enumitem}
\usepackage[T1]{fontenc}
\usepackage{inconsolata}
\usepackage{framed}
\usepackage{wasysym}
\usepackage[thinlines]{easytable}
\usepackage{hyperref}
\usepackage{minted}
\usemintedstyle{perldoc}
\hypersetup{
colorlinks=true,
linkcolor=blue,
filecolor=magenta,
urlcolor=blue,
}
\title{CS 103: Mathematical Foundations of Computing\\Problem Set \#1}
\author{}
\date{June 24, 2019}
\lhead{}
\chead{Problem Set 1}
\rhead{June 24, 2019}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Summer 2019}
\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}
% For Polyominoes
% Source: https://tex.stackexchange.com/a/110669
\usepackage{color}
\definecolor{lightgray}{rgb}{0.75, 0.75, 0.75}
\newdimen\omsq \omsq=16pt
\newdimen\omrule \omrule=1pt
\newdimen\omint
\newif\ifvth \newif\ifhth \newif\ifomblank
\def\OMINO#1{%
\vthtrue \hthtrue
\vbox{ \offinterlineskip\parindent=0pt \OM#1\relax\vskip1pt}}
\definecolor{gray}{rgb}{0.5, 0.5, 0.5}
\def\OM#1{%
\omint=\omsq \advance\omint-\omrule
\ifx\relax#1%
\else
\ifx\\#1 \newline\null \hthtrue \ifvth\vthfalse\else\vskip-\omrule\vthtrue\fi
\else%
\ifx .#1\hskip\ifhth \omrule\else \omint\fi
\else%
\ifx +#1\def\colour{black}\fi%
\ifx -#1\def\colour{black}\fi%
\ifx |#1\def\colour{black}\fi%
\ifx @#1\def\colour{black}\fi%
\ifx r#1\def\colour{red}\fi%
\ifx g#1\def\colour{green}\fi%
\ifx b#1\def\colour{blue}\fi%
\ifx y#1\def\colour{yellow}\fi%
\ifx m#1\def\colour{magenta}\fi%
\ifx c#1\def\colour{cyan}\fi%
\ifx x#1\def\colour{lightgray}\fi%
\textcolor{\colour}{\rule{\ifhth\omrule\else\omsq\fi}{\ifvth\omrule\else\omsq\fi}}%
\ifhth\else\hskip -\omrule\fi%
\fi%
\ifhth\hthfalse\else\hthtrue\fi%
\fi%
\expandafter\OM%
\fi}
\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}}
\begin{document}
\maketitle
\textbf{Checkpoint Questions Due Monday, July 1st at 3:00PM Pacific time.}
\textbf{Remaining Questions Due Friday, July 5th at 3:00PM Pacific time.} \\
Here we are -- the first problem set of the quarter! This problem set is designed to give you practice writing proofs on a variety of different topics. We hope that this problem set gives you a sense of what proof-based mathematics is like and helps solidify your understanding of set theory. \\
Before you start this problem set, please do the following:
\begin{itemize}
\item Sign up for Piazza so that you have an easy way to ask us questions.
\item Review the office hours timetable to find good times to drop on by to ask questions.
\item Review Handout ``Proofwriting Checklist,'' for a detailed set of criteria you should apply to your proofs before submitting them. We will be running this same checklist on your proofs when grading, so please be sure to look over it before submitting!
\end{itemize}
The following are additional resources and handouts that can clarify or supplement your understanding of lecture topics:
\begin{itemize}
\item ``Guide to $\in$ and $\subseteq$'' to make sure you understand the distinction between these terms.
\item ``Guide to Set Theory Proofs,'' for more information about how to structure proofs about sets and their properties.
\item ``Mathematical Vocabulary,'' which covers mathematical phrases you may need to use in your proofs and how to use them correctly.
\item ``Guide to Indirect Proofs,'' which provides some guidance about how to set up proofs by contradiction and contrapositive.
\item ``Ten Techniques to Get Unstuck,'' for advice about how to make progress on these sorts of problems when you're not sure what to do.
\end{itemize}
As always, please feel free to drop by office hours or post on Piazza if you have any questions. We're happy to help out. \\
Good luck, and have fun! \pagebreak
Write your solutions to the following checkpoint problems and submit them through GradeScope by Monday at 3:00PM Pacific time. Note in particular that late days may NOT be used on checkpoints. These problems will be graded on a 0 / \checkmark / $\checkmark^+$ scale. Solutions that reasonably attempt to solve all of the problems, even if the attempts are incorrect, will receive a $\checkmark^+$. Solutions that reasonably attempt some but not all of the problems will receive a \checkmark. Solutions that do not reasonably attempt any of the problems -- or solutions that are submitted after the deadline -- will receive a 0. Essentially, if you've made a good, honest effort to solve all of the problems and you submit on time, you should receive full credit even if your solutions contain errors. \\
Please make the best effort you can when solving these problems. We want the feedback we give you to be as useful as possible, so the more time and effort you put into them, the better we'll be able to comment on your proof style and technique. We will try to get these problems returned to you with feedback on your proof style by Wednesday. Submission instructions are in the ``Problem Set Policies'' handout.
\section*{Checkpoint Problem One: Finding Negations}
In order to write a proof by contradiction or contrapositive, you'll need to determine the negation of one or more statements. In Friday's lecture, we talked about a few common classes of statements and how to form their negations. Using what you've learned, answer the following multiple-choice questions and \textit{\textbf{briefly explain how you arrived at your answer}}. \\
Which of the following is the negation of ``everything that has a beginning has an end?''
\begin{enumerate}[label=\Alph*)]
\item Everything that does not have a beginning has an end.
\item Everything that has a beginning has no end.
\item There is something that has no beginning and has an end.
\item There is something that has a beginning and has no end.
\end{enumerate}
\begin{shaded}
Write your answer here.
\end{shaded}
Which of the following is the negation of ``there is a successful person who is grateful?''
\begin{enumerate}[label=\Alph*)]
\item There is an unsuccessful person who is grateful.
\item There is a successful person who is ungrateful.
\item Every successful person is grateful.
\item Every successful person is ungrateful.
\item Every unsuccessful person is grateful.
\item Every unsuccessful person is ungrateful.
\end{enumerate}
\begin{shaded}
Write your answer here.
\end{shaded}
Which of the following is the negation of ``if $A \subseteq B$, then $A - B = \emptyset$?''
\begin{enumerate}[label=\Alph*)]
\item If $A \subseteq B$, then $A - B = \emptyset$.
\item If $A \subseteq B$, then $A - B \neq \emptyset$.
\item If $A \not\subseteq B$, then $A - B = \emptyset$.
\item If $A \not\subseteq B$, then $A - B \neq \emptyset$.
\item There are sets $A$ and $B$ where $A \subseteq B$ and $A - B = \emptyset$.
\item There are sets $A$ and $B$ where $A \subseteq B$ and $A - B \neq \emptyset$.
\item There are sets $A$ and $B$ where $A \not\subseteq B$ and $A - B = \emptyset$.
\item There are sets $A$ and $B$ where $A \not\subseteq B$ and $A - B \neq \emptyset$.
\end{enumerate}
\begin{shaded}
Write your answer here.
\end{shaded}
\textit{\textcolor{blue}{Remember that you need to provide a justification for your answers. While it's not required, ideally you should be able to explain both why your answer is correct \textbf{and} why all the other answers are incorrect.}}
\section*{Checkpoint Problem Two: Set Theory Warmup}
This question is designed to help you get used to the notation and mathematical
conventions surrounding sets.
Consider the following sets:
\begin{align*}
A &= \{0, 1, 2, 3, 4\} \\
B &= \{2, 2, 2, 1, 4, 0, 3\} \\
C &= \{1, \{2\}, \{\{3, 4\}\}\} \\
D &= \{1, 3\} \\
E &= \N \\
F &= \{\N\}
\end{align*}
Answer each of the following questions and briefly justify your answers.
No proofs are necessary.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Which pairs of the above sets, if any, are equal to one another?
\begin{shaded}
Write your answer here.
\end{shaded}
\item Is $D \in A$? Is $D \subseteq A$?
\begin{shaded}
Write your answer here.
\end{shaded}
\item What is $A \cap C$? How about $A \cup C$? How about $A \Delta C$?
\begin{shaded}
Write your answer here.
\end{shaded}
\item What is $A - C$? How about $\{A - C\}$? Are those sets equal?
\begin{shaded}
Write your answer here.
\end{shaded}
\item What is $|B|$? What is $|E|$? What is $|F|$?
\begin{shaded}
Write your answer here.
\end{shaded}
\item What is $E - A$? Express your answer in set-builder notation.
\begin{shaded}
Write your answer here.
\end{shaded}
\item Is $0 \in E$? Is $0 \in F$?
\begin{shaded}
Write your answer here.
\end{shaded}
\end{enumerate}
\section*{Checkpoint Problem Three: Modular Arithmetic}
Different numbers can yield the same remainder when divided by some number. For example, the numbers 1, 12, 23, and 34 all leave a remainder of one when divided by eleven. To formalize this relationship between numbers, we'll introduce a relation $\equiv_k$ that, intuitively, indicates that two numbers leave the same remainder when divided by $k$. For example, we'd say that $1 \equiv_{11} 12$, since both 1 and 12 leave a remainder of 1 when divided by 11, and that $8 \equiv_3 14$, since both 8 and 14 leave a remainder of 2 when
divided by 3.
To be more rigorous, we'll formally define $\equiv_k$. For any integer $k$, define $a \equiv_k b$ as follows:
\begin{center}
We say that $a \equiv_k b$ if there exists an integer $q$ such that $a = b + kq$
\end{center}
We'd read the statement ``$x \equiv_k y$'' aloud as ``\textit{$x$ is congruent to $y$ modulo $k$}.'' For example, $7 \equiv_3 4$, because $7 = 4 + 3 \cdot 1$, and $5 \equiv_4 13$ because $5 = 13 + 4 \cdot (-2)$.
In this problem, you will prove several properties of modular congruence.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Prove that for any integer $x$ and any integer $k$ that $x \equiv_k x$.
\textit{\textcolor{blue}{Be careful not to assume what you need to prove. Don't start your proof by assuming there's a choice of $q$ where $x = x + kq$ and then solving for $q$. If you assume there's an integer $q$ where $x = x + kq$, you're already assuming that $x \equiv_k x$! Look at the proofs we did in lecture with odd and even numbers as an example of how to prove that there is a number with a specific property without making any unfounded assumptions.}}
\begin{shaded}
Write your answer here.
\end{shaded}
\item Prove that for any integers $x$ and $y$ and any integer $k$ that if $x \equiv_k y$, then $y \equiv_k x$.
\textit{\textcolor{blue}{Keep an eye out for your variable scoping in the above proof. Make sure you introduce the variables $x$, $y$, and $k$ before you use them. Are they chosen arbitrarily? Do they represent specific values?}}
\begin{shaded}
Write your answer here.
\end{shaded}
\item Prove that for any integers $x$, $y$, and $z$ and any integer $k$ that if $x \equiv_k y$ and $y \equiv_k z$, then $x \equiv_k z$.
\begin{shaded}
Write your answer here.
\end{shaded}
\end{enumerate}
Modular congruence is a powerful mathematical tool. You'll use it later in this problem set to build a better
understanding of star-drawing!
\pagebreak
\begin{center}
\textit{\textbf{The rest of these problems are due on Friday at 3:00PM. \\ Please type your solutions and submit them on GradeScope.}}
\end{center}
\section{Much Ado About Nothing}
It can take a bit of practice to get used to the empty set. This problem will ask you to think about a few different sets related to $\varnothing$. \\
Go to the CS103 website and download the starter files for Problem Set One. Unpack the files somewhere convenient and open up the bundled project. Answer each part of this question by editing the relevant resource files (they're in the \texttt{res/} directory). There's information in the top of each of the files about how to represent sets; most importantly, note that to write out the empty set, you should write \{\} rather than using the empty-set symbol. For example, the set $\{\varnothing\}$ would be written as \{\{\}\}.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Edit the file \texttt{PartI.object} so that it contains a set equal to $\varnothing \cup \{\varnothing\}$.
\item Edit the file \texttt{PartII.object} so that it contains a set equal to $\varnothing \cap \{\varnothing\}$.
\item Edit the file \texttt{PartIII.object} so that it contains a set equal to $\{\varnothing\} \cup \{\{\varnothing\}\}$.
\item Edit the file \texttt{PartIV.object} so that it contains a set equal to $\{\varnothing\} \cap \{\{\varnothing\}\}$.
\item Edit the file \texttt{PartV.object} so that it contains a set equal to $\wp(\wp(\varnothing))$.
\item Edit the file \texttt{PartVI.object} so that it contains a set equal to $\wp(\wp(\wp(\varnothing)))$.
\end{enumerate}
The starter code contains a driver program you can use to see the contents of your files and confirm they're syntactically correct. Submit your answers through GradeScope under ``Coding Problems for Problem Set One'' by uploading your edited starter files. You're welcome to submit as many times as you'd like.
\begin{shaded}
Submit your six $\mathsf{.object}$ files through GradeScope under ``Coding Problems for Problem Set One'' by uploading your edited starter files.
\end{shaded}
\section{Set Theory in C++}
The C++ standard library contains a type called \mintinline{c++}{std::set} that represents a set of elements, all of which must be of the same type. For example, the type \mintinline{c++}{std::set} represents a set of integers, the type \mintinline{c++}{std::set} represents a set of strings, and \mintinline{c++}{std::set>} is a type representing a set of sets of integers. \\
There are all sorts of operations you can perform on \mintinline{c++}{std::sets}. For example, here's how you iterate over all the elements of a set:
\begin{minted}{c++}
std::set mySet;
for (T elem: mySet) {
/* ... do something with the current element elem ... */
}
\end{minted}
Here's how you check whether a particular value is an element of a set:
\begin{minted}[escapeinside=||,mathescape=true]{c++}
if (mySet.count(value)) {
/* ... value $\in$ mySet ... */
} else {
/* ... value $\notin$ mySet ... */
}
\end{minted}
And, finally, here's how you can get the cardinality of a set:
\begin{minted}{c++}
size_t size = mySet.size();
\end{minted}
Here, the \mintinline{c++}{size_t} type is a type representing a natural number, since sets can't have negative size. (The folks who designed the C++ standard libraries had a strong discrete math background.) \\
One of the major differences between the sets we've talked about in CS103 and the \mintinline{c++}{std::set type} is that in discrete mathematics, sets can contain anything -- numbers, philosophies, recipes, other sets, etc. -- but in C++ all objects in a set must have the same type. For the purposes of this problem, we've created a custom C++ type called \mintinline{c++}{Object}. Variables of type \mintinline{c++}{Object} can represent just about anything, so a \mintinline{c++}{std::set