CIS 511, Fall 2021
Introduction to The Theory of Computation
September 28, 2021
** Welcome to CIS511, Fall 2021 **
Lecture: Monday-Wednesday, noon-1:30pm; LEVH 101
Instructor: Jean H.
Gallier, GRW 476, 8-4405, email@example.com
Office Hours: Thursday 5:00-6:15pm (see zoom link on canvas)
Andrews Beams: firstname.lastname@example.org
Daniel Feshback: email@example.com
Varun Gupta: firstname.lastname@example.org
Malathy Nagalakshmi: email@example.com
Nagul Ulaganathan: firstname.lastname@example.org
Jocelyn Quaintance: email@example.com
Yuwei Yuan (Lucy): firstname.lastname@example.org
This Fall we are returning to in class teaching, but
lectures will be recorded
and some office hours and recitations will
be conducted on zoom and recorded as well.
In order to increase the level of interaction between
the students and the instructor(s) I propose to use the following
is expected to read the material covered
every week in advance. This material is in the
slides and the notes online.
During class time, held in (LEVH 101)
on Mon-Wed from noon to 1:30pm,
I will take questions about the material of the week,
present examples, work out simple problems, and
sometimes present proofs. Sometimes I will give lectures, but not always.
I will record
each session and make them available
on the CANVAS account for the class.
- Students, whether or not they attended lectures, may listen to
recorded classes and should read the corresponding material
in the notes.
- 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.
There will be no midtems, a single final exam,
problems (some challenging).
There is a CANVAS account for the course:
CIS 511-001 2021C
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 preparation for the next lecture (September 29), please read
in Slides and Notes
Chapter 6, Pages 109-115,
Also read Pages 221-234 of
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 :
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!