CIS 511, Spring 2021
Introduction to The Theory of Computation

Course Information
April 13, 2021

** Welcome to CIS511, Spring 2021 **
** HW6 is available **
** Some slides have been slightly corrected (cis511-c-sl2, cis511-c-sl7, cis511-c-sl9) **


Lecture: Monday-Wednesday, 1:30-3:00pm
Recitation: Thursday, 5:00-6:15pm


Jean H. Gallier, GRW 476, 8-4405,

Office Hours:


Lawrence Dunn,
Ruijie Mao,
Luca Silver, lucsil@seas.upenn.du
Shaan Vaidya,

Office Hours:

Course Format

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 scenario.

Consequently, there will be a heavier burden and a greater requirement of self-discipline placed on the student to listen to the lectures and read the material in the notes to keep up with the course.

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 interactive class.

There will be no midtems, a single final exam, and homework problems (some challenging).

CANVAS Account

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 that
you should consult each week.

Look for Class Recordings and Files.

There is also a PIAZZA Account: SRS_CIS-511-001 2021A

Please read in Slides and Notes
and the notes tcbook-comp.pdf, Pages 205-228.

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.

Also recommended:

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

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. 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.

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