About the course:
CS 381 is an introduction to the modern theory of computing. The course has three natural sections:
- Automata and regular languages: Deterministic and nondeterministic finite automata, regular
languages, regular expressions and pattern matching, closure properties of regular languages, the limits
of automata and the pumping lemma, automata minimization, decision problems for automata.
- Context-free languages: Context-free grammars and normal forms, pushdown automata, the pumping lemma
for context-free languages, closure properties of context-free languages, the practical use of context-free grammars
in parsing.
- Effective computability and Turing Machines: the Turing Machine, the Church-Turing thesis, r.e. and recursive
languages, decidability and undecidability, the Halting Problem, reductions, Rice's theorem.
CS 381 is offered in the summer and fall semesters; in terms of material covered and workload, both offerings
are equivalent.
In the fall semester, the department also offers CS 481,
a somewhat deeper and faster-paced course covering the same topics as CS 381.
Instructor:
Lucja Kot
4104 Upson Hall
Office phone: (607) 255-9537
User id: lucja
My email address is my user id followed by @cs.cornell.edu.
Lecture time and place:
Monday to Friday, 8:30am - 9:45am, Hollister 362.
Office hours:
I will be available most days after class, until 11 or so. If you would like to meet at another time, please don't
be shy about emailing for an appointment or just dropping by my office.
Newsgroup:
There will be a class newsgroup
cornell.class.cs381
, which you are welcome to use for questions, discussions, announcements, complaints, suggestions, etc. If you are new
to newsgroups, instructions can be found
here.
Be careful not to post homework solutions, even partial ones.
Grading:
Your final grade in the course is based on regular homework assignments (40%), two prelims (15% each),
a final exam (25%), and in-class quizzes - announced and unannounced - (5%).
Required textbook:
D. C. Kozen, Automata and Computability. Springer-Verlag, 1997.
Prerequisites:
CS 280 or equivalent. It is essential that you be familiar with the basics of discrete mathematics,
as covered (for example) in CS 280. We will make extensive use of trees, sets, functions, relations, and other key concepts. You
should also have a solid understanding of basic mathematical proof techniques, including a good grasp of mathematical
induction.
If you have not taken CS 280 or an equivalent course, and/or if you are unsure about your background, please talk
to me.