\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 April 7, 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.\\
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.\\
{\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 for this assignment)
First, set up all the tools required for this class.
Enroll in the Piazza site for this class: \url{https://piazza.com/ucsd/spring2018/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/n40BwDdk6OI43fNk1}.\\
{\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= \{0,1\}$, $B=\{0,1,2\}$, and let the universal set $U=\{0,1,2,3,4,5,6,7,8,9\}$. List out the element in
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)$
\item[e.]
$\mathcal{P}(A)\times A$
\end{itemize}
\end{problem}
\begin{problem}[Question 2.] ({\bf 10 points})
A string over an alphabet $\Sigma$ is a finite list of symbols from that alphabet.
For $L$ a set of strings, we can define the following associated sets
\[
L \circ L = \{ uw \st u \in L \text{ and } w \in L \}
\]
\[
DOUBLE(L) = \{ vv \st v \in L \}
\]
\[
STUTTER(L) = \{ w_1 w_1 w_2 w_2 \cdots w_n w_n \st n \geq 0, w_i \in \Sigma \text{ for each $i$ where $1 \leq i \leq n$, and }
w_1 w_2 \cdots w_n \in L \}
\]
Note: $\varepsilon$ is in each of these sets iff it is an element of $L$ itself.\\
For each of the following, answer {\bf True} or {\bf False} . Justifications aren't required for credit for this question,
but it's good practice to think about how you would explain why your answer is true.
\begin{itemize}
\item[a.] For all $L$, $DOUBLE(L) \subseteq L\circ L$.
\item[b.] For all $L$, $L \circ L \subseteq DOUBLE(L)$.
\item[c.] $( \emptyset \circ \emptyset ) = DOUBLE(\emptyset) = STUTTER(\emptyset)$.
\item[d.] The length of each string in $L \circ L$ is even.
\item[e.] The length of each string in $DOUBLE(L)$ is even.
\item[f.] The length of each string in $STUTTER(L)$ is even.
\item[g.] For all $L$, $| L\circ L | = |L| \times |L|$.
\item[h.] For all $L$, $|DOUBLE(L)| = 2 |L|$.
\item[i.] For all $L$, $|STUTTER(L)|$ is finite.
\item[j.] There is a set $L$ where $L = STUTTER(L)$.
\end{itemize}
\end{problem}
\begin{problem}[Question 3.] ({\bf 10 points})
A set $X$ is said to be {\bf closed} under an operation $OP$ if, for any elements in $X$, applying
$OP$ to them gives an element in $X$. For example, the set of integers is closed under multiplication
because if we take any two integers, their product is also an integer.\\
For each of the sentences below, (1) first determine if it is a closure claim, then (2) determine
if the sentence is true or false.\\
For example, for the sentence ``The product of any two prime numbers is not prime" is (1) not a closure claim but (2) is true.
\begin{itemize}
\item[a.] Concatenating two strings over the alphabet $\Sigma$ gives a string over the alphabet $\Sigma$.
\item[b.] The reversal of a string over the alphabet $\Sigma$ is a string over the alphabet $\Sigma$.
\item[c.] The intersection of two infinite sets of integers is an infinite set of integers.
\item[d.] The union of two countably infinite sets of real numbers is an uncountable set of real numbers.
\item[e.] The power set of a finite set of positive numbers is a finite set of positive numbers.
\end{itemize}
\end{problem}
\end{document}