CS 452 - Automata and Formal Languages - Spring 2010

M 1:40 -- 4:40

Prof. M. Farach-Colton, Hill 448, Phone: Not very effective.
email: farach@cs.rutgers.edu
www: http://www.cs.rutgers.edu/~farach
Office hours: M: 12:30--1:30 PM or by appointment

TA: TBA
Text: Introduction to the Theory of Computation by Michael Sipser
Grading Policy: There will be a midterm and a final exam. The midterm is worth 35% of the final grade. The final will cover the entire course contents and will weigh 45% of the final grade. Each student will be required to read one paper and make a class presentation on its contents. This will count for 10% of the final grade. Homework assignments will constitute 10% of the final grade.

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.

Schedule: