%
% 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 Fall 2018 by Michael Zhu
% Updated for Fall 2019 by Joshua Spayd

\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{wrapfig}
\usepackage{hyperref}
\usepackage{minted}
\usepackage{cancel}
\usepackage{tabularx}
\usepackage{makecell}
\usepackage{changepage}
\usepackage{xcolor}
\usepackage{colortbl}
\usepackage{array}
\usepackage{fourier}

\title{CS 103: Mathematical Foundations of Computing\\Problem Set 3 Checkpoint}
\author{Your Name(s) Here}
\date{\today}

% Running author based on https://tex.stackexchange.com/a/68310
\makeatletter
\let\runauthor\@author
\makeatother

\lhead{\runauthor}
\chead{Problem Set 3}
\rhead{\today}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Autumn 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}
\newcommand{\nb}[1]{\multicolumn{1}{c}{\textit{#1}}}
\newcommand{\homog}{\,E\,}

\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{\Q}{\mathbb{Q}}
\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}}

\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{\parskip}{6pt}
\setlength{\parindent}{0pt}

\pagestyle{fancy}

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

\definecolor{incorrect}{RGB}{182,0,12}
\usetikzlibrary{arrows}

% Fixed-width centered column type from https://tex.stackexchange.com/a/97188
\newcolumntype{Z}{>{\centering\let\newline\\\arraybackslash\hspace{0pt}}X}

% start MZ
\usetikzlibrary{automata,positioning}
\let\oldemptyset\emptyset
\renewcommand{\emptyset}{\text{\O}}
\renewcommand\qedsymbol{$\blacksquare$}
\newenvironment{prf}{{\bfseries Proof.}}{\qedsymbol}
\renewcommand{\emph}[1]{\textit{\textbf{#1}}}
\newcommand{\annotate}[1]{\textit{\textcolor{blue}{#1}}}
\usepackage{stmaryrd}
% end MZ

\tikzset{
  relates/.style={very thick, arrows={-triangle 60}},
  toploop/.style={out=135, in=45, loop, looseness=5},
  bottomloop/.style={out=225, in=-45, loop, looseness=5},
  leftloop/.style={out=135, in=225, loop, looseness=5},
  rightloop/.style={out=45, in=-45, loop, looseness=5},
  trloop/.style={out=90, in=0, loop, looseness=5},
  tlloop/.style={out=180, in=90, loop, looseness=5},
  blloop/.style={out=-90, in=180, loop, looseness=5},
  brloop/.style={out=0, in=-90, loop, looseness=5},
  toparrow/.style={out=45, in=135, looseness=0},
  bottomarrow/.style={out=225, in=-45, looseness=0},
  leftarrowdown/.style={out=225, in=135, looseness=0},
  rightarrowup/.style={out=45, in=-45, looseness=0},
  leftarrowup/.style={out=135, in=225, looseness=0},
  rightarrowdown/.style={out=-45, in=45, looseness=0}
}

\begin{document}

\maketitle

\begin{center}
  \textit{These three checkpoint problems on this problem set are due on Monday
    at 2:30PM.}
\end{center}

\section{The Gallery}
Below is a collection of pictures of binary relations. \\
\begin{tabularx}{\textwidth}{|@{}X@{}|@{}X@{}|@{}X@{}|}
  \hline
  \makecell[c]{\emph{Relation 1}} &
  \makecell[c]{\emph{Relation 2}} &
  \makecell[c]{\emph{Relation 3}} \\
  \makecell[c]{
    \tikzset{every state/.style={scale=.7, fill=black!8, very thick, circle}}
    \begin{tikzpicture}[on grid, auto,
        baseline={(current bounding box.north)}, scale=.6]
      \node[state] (a) at (0,0) {};
      \node[state] (b) at (0,2) {};
      \node[state] (c) at (2,1) {};
      \node[state] (d) at (4,1) {};
      \node[state] (e) at (6,0) {};
      \node[state] (f) at (6,2) {};
      \draw[relates] (b) -> (a);
      \draw[relates] (d) -> (f);
      \draw[relates] (e) -> (d);
      \draw[relates] (e) -> (f);
    \end{tikzpicture}} &
  \makecell[c]{
    \tikzset{every state/.style={scale=.7, fill=black!8, very thick, circle}}
    \begin{tikzpicture}[on grid, auto,
        baseline={(current bounding box.north)}, scale=.6]
      \node[state] (a) at (0,0) {};
      \node[state] (b) at (0,2) {};
      \node[state] (c) at (2,1) {};
      \node[state] (d) at (4,1) {};
      \node[state] (e) at (6,0) {};
      \node[state] (f) at (6,2) {};
      \draw[relates] (a) to [bottomloop] (a);
      \draw[relates] (a) to [out=135, in=225, looseness=0] (b);
      \draw[relates] (b) to [out=-45, in=45, looseness=0] (a);
      \draw[relates] (b) to [toploop] (b);
      \draw[relates] (c) to [toploop] (c);
      \draw[relates] (d) to [leftloop] (d);
      \draw[relates] (d) to [out=-22.5, in=112.5, looseness=0] (e);
      \draw[relates] (d) to [out=67.5, in=202.5, looseness=0] (f);
      \draw[relates] (e) to [out=157.5, in=-67.5, looseness=0] (d);
      \draw[relates] (e) to [bottomloop] (e);
      \draw[relates] (e) -> (f);
      \draw[relates] (f) to [out=-112.5, in=22.5, looseness=0] (d);
      \draw[relates] (f) to [out=-45, in=45, looseness=0] (e);
      \draw[relates] (f) to [toploop] (f);
    \end{tikzpicture}} &
  \makecell[c]{
    \tikzset{every state/.style={scale=.7, fill=black!8, very thick, circle}}
    \tikzset{relates/.style={very thick, arrows={-triangle 60}}}
    \begin{tikzpicture}[on grid, auto,
        baseline={(current bounding box.north)}, scale=.6]
      \node[state] (a) at (0,0) {};
      \node[state] (b) at (2,0) {};
      \node[state] (c) at (2,2) {};
      \node[state] (d) at (0,2) {};
      \draw[relates] (a) -> (b);
      \draw[relates] (b) -> (c);
      \draw[relates] (c) -> (d);
      \draw[relates] (d) -> (a);
    \end{tikzpicture}} \\\hline
  \makecell[c]{\emph{Relation 4}} &
  \makecell[c]{\emph{Relation 5}} &
  \makecell[c]{\emph{Relation 6}} \\
  \makecell[c]{
    \tikzset{every state/.style={scale=.7, fill=black!8, very thick, circle}}
    \begin{tikzpicture}[on grid, auto,
        baseline={(current bounding box.north)}, scale=.6]
      \node[state] (a) at (0,0) {};
      \node[state] (b) at (0,2) {};
      \node[state] (c) at (2,0) {};
      \node[state] (d) at (2,2) {};
      \node[state] (e) at (4,0) {};
      \node[state] (f) at (4,2) {};
      \draw[relates] (a) to [bottomloop] (a);
      \draw[relates] (a) to (c);
      \draw[relates] (b) -> (a);
      \draw[relates] (c) to [out=45, in=-45, looseness=0] (d);
      \draw[relates] (c) -> (e);
      \draw[relates] (d) -> (b);
      \draw[relates] (d) to [out=224, in=135, looseness=0] (c);
      \draw[relates] (e) -> (f);
      \draw[relates] (f) -> (d);
      \draw[relates] (f) to [toploop] (f);
    \end{tikzpicture}} &
  \makecell[c]{
    \textit{(This is intentionally blank.)}} &
  \makecell[c]{
    \tikzset{every state/.style={scale=.7, fill=black!8, very thick, circle}}
    \begin{tikzpicture}[on grid, auto,
        baseline={(current bounding box.north)}, scale=.6]
      \node[state] (a) at (0,1) {};
      \node[state] (b) at (2,0) {};
      \node[state] (c) at (2,2) {};
      \draw[relates] (a) to [out=-22.5, in=112.5, looseness=0] (b);
      \draw[relates] (a) to [out=67.5, in=202.5, looseness=0] (c);
      \draw[relates] (b) to [out=157.5, in=-67.5, looseness=0] (a);
      \draw[relates] (b) -> (c);
      \draw[relates] (c) to [out=-112.5, in=22.5, looseness=0] (a);
      \draw[relates] (c) to [out=-45, in=45, looseness=0] (b);
    \end{tikzpicture}} \\\hline
\end{tabularx}

Fill in the table below. No justification is necessary. We've included a few
entries to help get you started.

\begin{tabularx}{\textwidth}{r|Z|Z|Z|Z|Z|Z|Z|}
  \nb{}             & \nb{Reflexive} & \nb{Symmetric} & \nb{Transitive} & \nb{Irreflexive} & \nb{Asymmetric} & \nb{Equiv. Rel.} & \nb{Strict Order} \\\cline{2-8}
  \emph{Relation 1} & No             & No             &                 & Yes              & Yes             &                  &                   \\\cline{2-8}
  \emph{Relation 2} &                &                &                 &                  &                 &                  &                   \\\cline{2-8}
  \emph{Relation 3} &                &                &                 &                  &                 &                  &                   \\\cline{2-8}
  \emph{Relation 4} &                &                &                 &                  &                 &                  &                   \\\cline{2-8}
  \emph{Relation 5} &                &                &                 &                  &                 &                  &                   \\\cline{2-8}
  \emph{Relation 6} &                &                &                 &                  &                 &                  &                   \\\cline{2-8}
\end{tabularx}

\annotate{
  To help you check your answers, note that
  \begin{itemize}[noitemsep]
    \item three of these six relations are transitive,
    \item at least one relation is both symmetric and asymmetric,
    \item at least one relation is both reflexive and irreflexive, and
    \item at least one relation is asymmetric and irreflexive but not
      transitive.
  \end{itemize}}

\pagebreak

\section{Redefining Equivalence Relations?}

Below is a purported proof that every relation that is both symmetric and
transitive is also reflexive.

\begin{tabularx}{\textwidth}
  {>{\centering\arraybackslash}m{.25in}|X|>{\centering\arraybackslash}m{.25in}}
  \arrayrulecolor{incorrect}\cline{2-2}
  \makecell[c]{\\\\\\\textcolor{incorrect}\danger} &
  \textbf{(Incorrect!) Theorem}: If $R$ is a symmetric and transitive binary
  relation over a set $A$, then $R$ is also reflexive.

  \textbf{(Incorrect!) Proof}: Let $R$ be an arbitrary binary relation over a
  set $A$ such that $R$ is both symmetric and transitive. We need to show that
  $R$ is reflexive. To do so, consider an arbitrary $x, y \in A$ where $x R y$.
  Since $R$ is symmetric and $x R y$, we know that $y R x$. Then, since $R$ is
  transitive, from $x R y$ and $y R x$ we learn that $x R x$ is true.
  Therefore, $R$ is reflexive, as required. \qedhere
  &
  \makecell[c]{\\\\\\\textcolor{incorrect}\danger}\\
  \arrayrulecolor{incorrect}\cline{2-2}
\end{tabularx}

This proof, unfortunately, is incorrect.

\begin{enumerate}[label=\roman*.]
  \item Draw the simplest possible relation that is symmetric, transitive, and
    not reflexive. As a hint, it requires three or fewer elements.
    \begin{shaded}
      Place your picture and write your justification here.
    \end{shaded}

    \item What's wrong with this proof? Justify your answer. Be as specific as
      possible.
    \begin{shaded}
      Write your answer and justification here.
    \end{shaded}
\end{enumerate}

\annotate{The error in this proof is one that we see a lot of people make
  consistently throughout the problem set. That often leads to folks having
  mistakes in every single one of the proofs they submit. Read over the Guide
  to Proofs on Discrete Structures and Discrete Structures Proofwriting
  Checklist and make sure you’re confident that you see what the issue is. If
  you aren't sure, feel free to ask on Piazza or to stop by office hours.
  Regardless of what you write, \emph{be sure to read the checkpoint solutions}
  as soon as they come out! It would be a shame if you missed the issue here
  and then made this exact mistake later on in this problem set.}

\pagebreak

\section{Homogeneous Coordinates}
This problem explores \emph{homogeneous coordinates}, a mathematical concept
that's used extensively in computer graphics. Take CS148 to learn how they're
used to draw 3D graphics on the screen!

Let $\mathbb{R}^2$ denote the set of all ordered pairs of real numbers. For
example, $(137, 42) \in \mathbb{R}^2$, $(\pi, e) \in \mathbb{R}^2$, and $(-2.71,
103) \in \mathbb{R}^2$. Two ordered pairs are equal if and only if each of
their components are equal. That is, we have $(a, b) = (c, d)$ if and only if $a
= c$ and $b = d$.

Now, consider the relation $E$ over $\mathbb{R}^2$ defined as follows:
\[
  (x_1, y_1) \homog (x_2, y_2) \quad\textrm{if}\quad \exists k \in \mathbb{R}.
  (k \ne 0 \land (kx_1, ky_1) = (x_2, y_2)).
\]

For example, $(3, 4) \homog (6, 8)$ because $(2 \cdot 3, 2 \cdot 4) = (6, 8)$.

Prove that $E$ is an equivalence relation over $\mathbb{R}^2$.

\annotate{Remember that the ``if'' in the definition of the relation $E$ means
  ``is defined as'' and isn't an implication.}

\begin{shaded}
  Provide a proof here.
\end{shaded}

\annotate{Once you've written a draft of your proof of this result, take a few
  minutes to apply both the standard Proofwriting Checklist (the one you've used
  on the first two problem sets) and the new Discrete Structures Proofwriting
  Checklist. Here are a few specific things to keep an eye on:
  \begin{itemize}
    \item Terms like symmetry, transitivity, etc. are defined in first-order
      logic and proofs of those properties depend on those first-order
      definitions.  However, you should \emph{not} use first-order logic
      notation (quantifiers, connectives, etc.) in your proofs. Look at the
      proofs from the Guide to Binary Relations and last week's lectures for
      some examples of what we're expecting.
    \item Make sure that you've set all of your proofs up properly. For example,
      what should a proof that a relation is symmetric look like? What should
      you assume, and what you should prove?
    \item Don't repeat the definition of the $E$ relation in your proof. The
      reader knows how it's defined.
  \end{itemize}}
\end{document}
