CIS 262, Fall 2017
Automata, Computability and Complexity

Course Information
December 7, 2017

** The practice exam is online **
** The list of topic for the final has been updated **
** The notes have been updated **
** There will be a recitation on 12/09/2017 **
** 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


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


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:
Xuan Ru Ng:
Omar Paladines:
Kelly Tan:
Rohit Venkataraman:
Waley Zang:

Office Hours:

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

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 Computation, 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 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 found on the internet. 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.).

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