CIS 511, Spring 2021
Introduction to The Theory of Computation
April 27, 2021
** Welcome to CIS511, Spring 2021 **
** The take-home Final will take place between **
** May 6, 8am, to May 7, midnight **
** Submission on gradescope, in latex **
** See topics in Homework section **
** Some slides have been slightly corrected (cis511-c-sl9, cis511-c-sl10) **
Lecture: Monday-Wednesday, 1:30-3:00pm
Recitation: Thursday, 5:00-6:15pm
Instructor: Jean H.
Gallier, GRW 476, 8-4405, firstname.lastname@example.org
Lawrence Dunn, email@example.com
Ruijie Mao, firstname.lastname@example.org
Luca Silver, email@example.com
Shaan Vaidya, firstname.lastname@example.org
This course will be fully taught online.
In order to increase the level of interaction between
the students and the instructor(s) I propose to use the following
I will lecture on zoom on Mon-Wed from 1:30 to 3:00pm, record
the lectures and make them available
on the CANVAS account for the class.
- Every student is expected to listen to
recorded classes and read the corresponding material
in the notes, every week.
- A list of the material to be listened to and read
will be available on this web page
(see under CANVAS account).
I will provide an extra recitation (once a week, for
1 hour 15mn). During this recitation
I intend to
answer questions about the material presented
during the lectures.
Occasionally present important proofs.
In general, attempt to motivate, demistify, and
put in context the material of the lectures.
Give an idea about applying the material to solve
the homework problems.
Consequently, there will be a heavier
burden and a greater requirement of
placed on the student to listen to the lectures and read the
material in the notes to keep up with the
On the other, you will have greater flexibility in deciding
when to listen and read the lectures in preparation for the
actual class, which I hope, will be more of an
There will be no midtems, a single final exam,
problems (some challenging).
There is a CANVAS account for the course:
CIS 511-001 2021A
You should have access to it using your Pennkey.
This account contains the video recordings and reading material
you should consult each week.
Look for Class Recordings and Files.
There is also a PIAZZA Account:
in Slides and Notes
and the notes tcbook-comp.pdf, Sections 10.1 and 10.3.
Textbook (not required): 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.
Elements of the Theory of Computation,
H. Lewis and C. Papadimitriou, Prentice Hall
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. 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.
Due to the difficulty of the homework problems and in order to
give you an opportunity to learn how to collaborate
more effectively (I do not mean "copy"), I will allow you
to work in small groups.
A group consists of AT MOST THREE students.
You are allowed to collaborate
with the same person(s) an unrestricted number of times.
Only one homework submission per group.
All members of a group
will get the SAME grade on a homework or a project
(please, list all names in a group).
It is forbidden to use 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.
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!