MW 1:40 -- 3:00, Hill 250

email: farach@cs.rutgers.edu

www: http://www.cs.rutgers.edu/~farach

Office hours: W: 11-12 or by appointment

TA: Le Wang

Text: Introduction to the Theory of Computation by Michael Sipser

The homework assignments are mathematically oriented. The top 80% of the assigned homework will be used to compute the homework grade. NO LATE HOMEWORK WILL BE ACCEPTED.

Homework must be turned in by email as a pdf. I recommend doing it in
LaTeX. Wysiwyg editors for latex are available at TeXmacs, LyX, or MathType.
See also the Mac-TeX site.
Also, please out Gastex
for drawing automata. It has a java interface that I haven't checked
out. It's pretty easy to hack from scratch. For example:
\begin{center}\compatiblegastexun

\begin{picture}(80,35)(-20,-28)

\thinlines

%\put(-20,-15){\framebox(80,55){}}

\letstate A=(0,0) \drawinitialstate(A){$q_0$}

\letstate B=(20,0) \drawstate(B){$q_1$}

\letstate C=(40,0) \drawrepeatedstate(C){$q_2$}

\letstate D=(10,-20) \drawstate(D){$q_3$}

\drawtrans[r](A,B){$a$}

\drawtrans[r](B,C){$b$}

\drawtrans[r](A,D){$b$}

\drawloop[b](D){$a$}

\drawloop[b](C){$b$}

\drawloop[r](C){$a$}

\drawcurvedtrans(B,D){$b$}

\drawcurvedtrans(D,B){$a$}

\end{picture}

\end{center}

On any assignment (homework, exam or presentation), you can either attempt to answer the question, in which case you will receive betweeen 0 and 100% credit for that question, or you can write "I don't know", in which case you receive 25% credit for that question.

- Midterm: TBA.
- Final: TBA.