\documentclass[letterpaper,12pt]{article}
\usepackage{fullpage}
\usepackage{amssymb}
\usepackage{hyperref}

\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\R}{\mathbb{R}}

\begin{document}

\newlength{\boxwidth}
\setlength{\boxwidth}{\textwidth}
\addtolength{\boxwidth}{-2cm}
\noindent\framebox[\textwidth]{\hfil
\parbox[t]{\boxwidth}{%
{\bfseries CSE\,105: Automata and Computability Theory \hfill Winter 2015}
\begin{center}\huge Homework \#1\end{center}
Due: Wednesday, January 14th, 2015, 11:59 \textsc{pm}%
}\hfil}
\vspace{0.7cm}

\begin{description}

\item[Problem 1] Sign up for an account on Automata Tutor, at
  \url{http://automatatutor.com}.  If you are a UCSD student, use your
  official UCSD e-mail for your account, so that we know whom to
  assign credit to.  If you are an extension student, use the same
  e-mail address you gave us to use for GradeSource.  Enroll in
  CSE~105's Automata Tutor section, which has Course~ID
  ``\texttt{33UCSDCSE}'' and password ``\texttt{UAKRXM1Y}''.
  On automata tutor, there is only one class listed under
  Prof. Shacham. That's the right class even if you are with Prof. Micciancio.

  You may practice designing automata using the practice problem sets. 

  \begin{description}
  \item[a--e.] Complete the five problems that constitute CSE~105's
    HW1 on Automata Tutor.   Notice that you may have only a limited
    number of chances to submit/revise your solution.
    
  \end{description}

  If you don't see any problem listed yet, just be patient, we will 
  add the problems soon. 

\item[Problem 2] Proofs by induction. This problem is just a refresher of standard mathematical notation and simple proofs by induction, which are 
  both essential tools in the study of automata and computability theory. Your solution will be graded both for correctness and clarity.

  Prove, by induction on $n$, that 
  \[ \sum_{k=1}^n (2k) = n^2 + n, \]
  i.e., the sum of the first $n$ even positive integers equals  $n^2 + n$.
  
  Submit your solution as a pdf file \texttt{HW12.pdf} 
  using Bundle. Your solution should be typeset. 
  If using LaTex to typeset your proof,  start from the 
  \texttt{HW12.tex} template file on the course webpage. 
  If not, make sure you include your name, student id, and
  collaboration disclosure at the beginning of your writeup.

\item[Problem 3] Haskell. This is a very simple programming exercise, meant to familiarize 
  yourself with the Haskell programming language and the ghc compiler. 
  To start with, read the instructions on the course webpage/calendar on using Haskell. 

  The task is to write (and compile) a haskell program 
  that computes the function from problem 2. 
  More specifically, on input an integer $n\geq 0$, 
  the program should output the sum of the 
  first $n$ even numbers.
  
  Use the starter file \texttt{HW13.hs} provided on the course webpage, 
  and complete the definition of the program \texttt{HW13} as directed 
  by the comments in the file.
  You should submit your modified file \texttt{HW13.hs} using Bundle.

  You can test your solution by first compiling it with the command 
  \texttt{ghc HW13.hs}. If compilation is successful, move on and
  run the test program with the command 
  \texttt{runghc HW13-test.hs}. 
  You can look at the test program (it is very simple): it computes 
  your function \texttt{hw13} on 100 input values, 
  and checks if they all produce the expected result, according to
  the formula from problem 2. 
  The test program  will print ``True'' if 
  all results are correct, and ``False'' otherwise.
  (Alternatively, you can also test your program by loading it in the 
  interpreter with the command \texttt{ghci HW13.hs}, and then evaluating 
  \texttt{hw13 n} on any input $n$ of your choice.)


\item[Problem 4] Using JFLAP. The aim of this problem is just to make sure you can run JFLAP on your computer. Download JFLAP from the webpage \url{http://www.jflap.com} and start it on your computer following the instructions on the JFLAP webpage. You can also follow the tutorial on that webpage to familiarize yourself with the program.

  Then use JFLAP to draw the DFA $M = (Q,\Sigma,\delta,s,F)$ where 
  \begin{itemize}
    \item $Q = \{A,B,C\}$,
    \item $\Sigma = \{0,1\}$,
    \item $s = A$,
    \item $F = \{B,C\}$, and
    \item $\delta\colon Q\times \Sigma\to Q$ is the transition function 
      specified by the following table
      \[ \begin{array}{c|cc}
        \delta & 0 & 1 \\
        \hline
        A & A & B \\
        B & B & C \\
        C & A & A \\
      \end{array}
      \]
    \end{itemize}

    Save the automaton into a file \texttt{HW14.jff} and submit it using Bundle.

\end{description}

\end{document}