CIS 5110, Spring 2025
Introduction to The Theory of Computation
Course Information
January 17, 2025
** Welcome to CIS5110, Spring 2025 **
Coordinates:
Lecture: Tuesday-Thursday, noon-1:30pm, DRL A8
Recitation: ? Thursday, 5:00-6:15pm ?
Instructor:
Jean H.
Gallier, Levine 476, 8-4405, jean@cis.upenn.edu
Office Hours:
TA/Graders:
Office Hours:
Course Format
I will lecture in person in DRL A8.
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
scenario.
-
Every student
is expected to read the material covered
every week in advance. This material is in the
slides and the notes online.
-
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
-
Take and
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 homework
problems (some challenging) but
no midtems and no final exam.
CANVAS Account
There is a CANVAS account for the course:
BAN_CIS 5110-001 202510
https://canvas.upenn.edu/courses/1842992
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 an Ed Account:
CIS-5110 001 in the Canvas site.
In preparation for the secondt lecture, please read
in Slides and Notes
Pages 1-49 of
the slides
https://www.cis.upenn.edu/~cis511/notes/cis511-sl1.pdf
And Pages 51-67 of the slides
https://www.cis.upenn.edu/~cis511/notes/cis511-sl2.pdf
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 :
html
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: