CIS 262, Fall 2017
Automata, Computability and Complexity
October 17, 2017
** Revised due date for HW5: 10/20/2017, 11:59 **
** Review session available online **
** Tutorials on HMMs available in "Additional Resources" **
** Please, refrain from a touristic behavior
(skipping classes systematically) **
** Your performance will only suffer from such a behavior **
Towne 100, Tu-Th, 12:00-1:30pm
Instructor: Jean H.
Gallier, GRW (Levine) 476, 8-4405, email@example.com
Every Monday, 2:00-3:00pm, Towne 100
Office Hours: Tuesday 4:30-5:30pm,
Lounge on the fourth floor of GRW (Levine) for myself
Andrej Illic: firstname.lastname@example.org
Xuan Ru Ng: email@example.com
Omar Paladines: firstname.lastname@example.org
Kelly Tan: email@example.com
Rohit Venkataraman: firstname.lastname@example.org
Waley Zang: email@example.com
Andrej Illic: Mon, 3:00-4:00pm
Xuan Ru Ng: Thu, 6:00-7:00pm, Harrison Mezzanine
Omar Paladines: Tu, 2:00-3:30pm
Kelly Tan: Mon, 1:30-3:00pm
Rohit Venkataraman: Tu, 3:30-4:30pm
Waley Zang: Mon, 6:00-7:30pm, Lounge on the fourth floor of GRW (Levine)
Textbook (not required):
Elements of the Theory of Computation,
H. Lewis and C. Papadimitriou, Prentice Hall
Introduction to Automata Theory, Languages
and Computation, J.E. Hopcroft, R. Motwani,
and J.D. Ullman,
Addison Wesley, third edition (July 8, 2006).
The second edition is also fine.
Introduction to the Theory of Computation,
Michael Sipser, PWS Publishing
Latex Tutorial (Especially Section 11):
A Word of Advice :
Expect to be held to high standards, and conversely!
In addition to transparencies, I will post
lecture notes on the web page for the class.
Please, read the course notes regularly, and
start working early on the problems sets. They will be hard!
Take pride in your work.
Be clear, rigorous, neat, and concise.
Preferably, use a good text processor, such as LATEX, to
write up your solutions.
We will use Piazza for discussion.
Each homework should be submitted
the day it is due
at the BEGINING of the class as a hard copy.
Graded homeworks can be picked up in the CIS main office, Levine 302.
It is forbidden to use old solutions or
solutions of problems posted on the
If you use resources other than the textbook (or the recommended textbooks)
or the class notes, you must cite these references.
Open book exams. During a midterm exam or during the final, you
can consult the textbook, class notes, your own personnal notes,
but you are not allowed to use the internet for any other
purpose than accessing the class notes or slides.
During lectures, please refrain from using mobile devices or
your laptop (no online shopping, use of facebook, etc.).
I assume that you are all responsible adults.
Copying old solutions verbatim or blatantly
isomorphic solutions are easily detectable.
DO NOT copy solutions from old solution
sheets, from books, from solutions posted on the internet, or from friend!
Either credit will be split among the perpetrators, or worse!