\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx, xcolor}
\usepackage{varwidth, hyperref}
\pagestyle{empty}
\newcommand{\R}{\mathcal{R}}
\newcommand{\st}{~\mid~}
\name{}
\class{CSE 105}
\assignment{Individual Homework 0}
\duedate{Due: Saturday January 13, 2018 at 11:00PM (on Gradescope)}
\begin{document}
\begin{center}
\begin{minipage}[t]{5.7in}
\rule{\linewidth}{2pt}
This {\bf Individual HW0} must be completed without any collaboration
with other students in this class. The only allowed sources of help for this homework
are the class textbook, notes, and podcast, and the instructional team. Two of the questions on this homework will be graded for fair effort completeness; one will be graded for correctness.\\
Your homework must be typed. We recommend that you submit early drafts to Gradescope so that in
case of any technical difficulties, at least some of your work is present. You may update
your submission as many times as you'd like up to the deadline.\\
Your assignments in this class will be evaluated not only on the correctness of your answers, but
also on your ability to present your ideas clearly and logically. Whether you use formal proof techniques or write a more informal argument for why something is true, your answers should always be well-supported.\\
{\sc Reading} Sipser Chapter 0
\newline
{\sc Key Concepts} Sets, integers, sequences, functions, relations,
predicates, graphs, trees, strings,
boolean logic, proof by construction, proof by contradiction, proof by induction.
\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\problemlist{}
\begin{problem}[Question 0.] (up to {\bf 2 points} extra credit)
First, set up all the tools required for this class.
Enroll in the Piazza site for this class: \url{https://piazza.com/ucsd/winter2018/cse105/home}.
Confirm you have access to this class via Gradescope \url{https://gradescope.com/} using your \texttt{ucsd.edu} email address. If you do not have access to Gradescope, post a private note on
Piazza with your name, PID, section number, and email.\\
Also, complete the pre-class survey: \url{https://goo.gl/forms/OLZOShiyVFcQl1ts1}.\\
{\it Completing the survey will give you 2 points extra credit towards the maximum score of 30 points on
this assignment.}
\end{problem}
\begin{problem}[Question 1.]({\bf 10 points})
Let $A= \{a,c,e,s\}$, $B=\{a,b,c,d\}$, and let the universal set $U=\{a,b,c,\dots,z\}$. Use set notation to write out each of the following sets.
\begin{itemize}
\item[a.]
$A\cup B$
\item[b.]
$(A\cap B)\times A$
\item[c.]
$\overline{A \cup B}$
\item[d.]
$\mathcal{P}(A\cap B)$
\end{itemize}
\end{problem}
\begin{problem}[Question 2.] ({\bf 10 points}) {\bf True/False}
State whether each statement is true or false and justify with one or two sentences.
For example, if the statement is true and follows from definition(s), write out the relevant
definitions and explain how they apply.
\begin{itemize}
\item[a.] $\overline{A\cup B} = \overline{A} \cap \overline{B}$
\item[b.] There exist finite sets $A,B$ for which the Cartesian product $A \times B$
equals
$\mathcal{P}(A \cup B)$.
\item[c.] $\{\emptyset\} \cup \{a,b\} = \{a,b\}$.
\item[d.] $\emptyset \in \{a,b\}$
\item[e.] $\{a,b\}\cap \{c,d\} = \emptyset$
\end{itemize}
\end{problem}
\begin{problem}[Question 3.] ({\bf 10 points})
CSE 105 is a fairly proof heavy class. The goal of this problem is to help refresh your memory on different proof techniques: proof by induction, closure proofs and set equality proofs.\\
For each part of this question, {\bf complete the proofs} by filling in the blanks.\\
{\it Note: there may be alternate correct proofs to each of these claims. The point of this
question is to practice certain proof strategies.}
\begin{itemize}
\item[a.]
{\bf Definition:} The \emph{reverse} of a string $u$, denoted $u^\R$, is defined recursively as follows:
\begin{itemize}
\item[(1)]
$\varepsilon^\R=\varepsilon$ (Note that $\varepsilon$ is the empty string.)
\item[(2)]
For any character $a$, and any string $w$, then $(wa)^\R=a w^\R$.
\end{itemize}
{\it This definition, in words, is on page 14.}
{\bf Claim}: $(uv)^\R=v^\R u^\R$ for any strings $u$ and $v$.
{\it Proof}: By structural induction on $v$.
\begin{quote}
{\bf Base case:} $v=\varepsilon$. Let $u$ be any string.
\[
(u \varepsilon)^\R = ~\framebox{\phantom{I\hspace{2 in}}}~
= \varepsilon^\R u^\R
\]
{\bf Induction step:} Let $v$ be an arbitrary string. Assume that for all strings $u$,
$(uv)^\R=v^\R u^\R$. We need to show that, for each character $a$ and all strings $u$,
$(u ~ va )^\R = (va)^\R u^\R$.
By the recursive definition of \emph{reverse}: $(u ~ va)^\R=$~\framebox{\phantom{I\hspace{2 in}}}.\\
By the inductive hypothesis: $(uv)^\R = $~\framebox{\phantom{I\hspace{2 in}}}.\\
Also, by the recursive definition of \emph{reverse}: $(va)^\R =$~\framebox{\phantom{I\hspace{2 in}}}.
\bigskip
Thus,
\begin{eqnarray*}
(u~va)^R&\overset{(def)}{=}&\framebox{\phantom{I\hspace{2 in}}}\\
&\overset{(IH)}{=}&\framebox{\phantom{I\hspace{2 in}}}\\
&\overset{(def)}{=}&(va)^\R u^\R.~~~~~~~~~~~~~~\square
\end{eqnarray*}
\end{quote}
\end{itemize}
\end{problem}
\begin{problem}[ (cont'd) ]
\begin{itemize}
\item[b.]
Prove that the set $\{n\in \mathbb{Z}\st n>2 \text{ and } n \text{ is composite}\}$ is closed under multiplication but not closed under addition.
\begin{quote}
An integer $a$ is composite if $a=xy$ such that $x,y\in \mathbb{Z}$, $1