\documentclass[ps, letterpaper]{cscie121}
\usepackage{enumerate}
\begin{document}
\header{0}{Friday, September 13, 2013}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent{\bf Note: This is our standard prologue. Problem set 0 counts 0 points, but you should complete it, and we will grade it and provide a solution set for your edification.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem{2+2+2+2} Using set notation, give formal descriptions of the following sets:
\subproblem The set containing no elements.
\subproblem The set containing the empty string.
\subproblem The power set of a set $X$, denoted $\mathcal{P}(X)$, i.e., the set containing all subsets of $X$.
\subproblem The difference between two sets $X$ and $Y$, denoted $X\setminus Y$, i.e., the set containing all elements of $X$ that are not elements of $Y$.  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem{10+10} Given a set $X$, we define the power set $\mathcal{P}(X)$ to be the set of all subsets of $X$. 
\subproblem Construct a bijection between $\mathcal{P}(X)$ and the set of functions from $X$ into the set $\{0,1\}$.
\subproblem Prove that for any finite set $X$, $|P(X)| = 2^{|X|}$. (Hint: use induction on $|X|$.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\turnover
\problem{5+5+5+5} Let $L_1$ be the language $\{a^n : n \ge 0\}$ and $L_2$ be the language $\{x : x \in \{a,b\}^* $ and $|x|=5\}$.

\subproblem Which of the following sets are finite? Of those that are
finite, what is their cardinality? \begin{enumerate}[i.]
\item $L_1 \cap L_2$ 
\item $L_2 \times (L_1 \cap L_2)$
\item $L_2 \setminus L_1$.
\end{enumerate}

\subproblem Which of the following sets contain the empty string $\vareps$? 
\begin{enumerate}[i.]
\item $L_1 \cap L_2$
\item $L_1 \cup L_2$
\end{enumerate}

\subproblem Which of the following sets have the empty set $\emptyset$
as a subset? \begin{enumerate}[i.]
\item $L_2$ 
\item $L_1 \cap L_2$
\end{enumerate}
\subproblem Which of the following sets contain $\emptyset$ as an
element? \begin{enumerate}[i.]
\item $L_1$ 
\item $P(L_2)$
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem{Sipser 0.13 Challenge! 3}
An undirected graph is a set of points with lines connecting some of the points. The points are called nodes or vertices, and the lines are called edges. The number of edges at a particular node is the degree of that node. An edge from a node to itself is called a self-loop. (Sipser, pg. 10)\\

\noindent Show that every graph without self loops and with two or more nodes contains two nodes that have equal degrees.  

\end{document}