CIS 262, Spring 2020
Automata, Computability and Complexity

Course Information
May 1, 2020

** Welcome to CIS 262, Spring 2020 **
** The Practice Problems for the Final are online **
** The list of topics for the final exam is online **
** Please, refrain from a touristic behavior
(skipping classes systematically) **


Levine 101 (Wu and Chen), Tu-Th, 9:00-10:30pm


Jean H. Gallier, GRW (Levine) 476, 8-4405,


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,
Justin Choi,
Jacob Glenn,
Justin Hong,
Alan Ismaiel,
Akhilesh Khakhart,
Seyoung Kim,
Steven Shapiro,
Jun Park,

Office Hours:

see Piazza

Textbook (not required):

Elements of the Theory of Computation, H. Lewis and C. Papadimitriou, Prentice Hall

Also recommended:

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):


[   Grade (Homeworks, Exams)   |  Additional Resources   |  Syllabus   |  Slides and Notes   ]

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 but 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 internet. 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.).

Plagiarism Policy

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!

Back to Gallier Homepage

published by:

Jean Gallier