CIS 262, Spring 2020
Automata, Computability and Complexity
February 23, 2020
** Welcome to CIS 262, Spring 2020 **
** Solutions for the review material for Midterm 1 have been posted! **
** The list of topics to review for Midterm 1 has been posted **
** Please, refrain from a touristic behavior
(skipping classes systematically) **
Levine 101 (Wu and Chen), Tu-Th, 9:00-10:30pm
Instructor: Jean H.
Gallier, GRW (Levine) 476, 8-4405, firstname.lastname@example.org
Every Monday, 4:30-5:30pm, Levine 101 (same as classroom)
Office Hours: TBA,
Lounge on the fourth floor of GRW (Levine) for myself
Head TA: Bernadette Bucher,
Jack Buttimer, email@example.com
Justin Choi, firstname.lastname@example.org
Jacob Glenn, email@example.com
Justin Hong, firstname.lastname@example.org
Alan Ismaiel, email@example.com
Akhilesh Khakhart, firstname.lastname@example.org
Seyoung Kim, email@example.com
Steven Shapiro, firstname.lastname@example.org
Jun Park, email@example.com
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 Comutation,
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
to Gradescope the day it is due
at the BEGINING of the class.
It is fine to discuss how solve problems with others
you must submit your own ORIGINAL solution.
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.
Closed book exams. Cheet-sheets allowed (2 pages).
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!