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

\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.}

\setcounter{Part}{2}
\PART{Nick}
\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}