Computer Science 383

Theory of Computer Science

Spring, 2006

Textbook:

Introduction to Automata Theory, Languages, and Computation (2nd edition) by Hopcroft, Motwani, and Ullman
This is one of the classic texts in Computer Science. It is also one of the oldest -- it is the grandchild of a book Formal Languages and Their Relation to Automata that Hopcroft and Ullman wrote in 1969. I took a course from the latter book as an undergraduate (yes, there were computers back then. We even had transistors and rock & roll and student protests and all kinds of modern innovations....). The first edition of the text was widely admired (by faculty) and widely regarded as hard to read (by students). The second edition, which we will be using, is a complete rewrite of the first and is considerably easier to read.

 

Course Description:

We will cover most of chapters 1-10 of the text. After Chapter 1, which is just an introduction, this material falls into three clusters:

• Chapters 2 through 8 discuss the interplay between languages and abstract machines (automata) that can process them.
• Chapter 9 discusses Undecidability -- problems that cannot be solved algorithmically.
• Chapter 10 discusses Intractability -- problems that can be solved algorithmically, but only in exponential time.

Here is a tentative schedule for the course. The early material here is fun and not very difficult (I used to do the first few weeks of this in CS151), so I will try to move along quickly at the start to allow more time for the more challenging material at the end of the course.

Week	Chapter	Topic
2/6 - 2/10	1 - 2	Introduction; finite automata
2/13 - 2/17	2 - 3	Regular expressions; the equivalence of regular expressions and finite automata
2/20 - 2/24	4	Regular languages. Determining whether a language is regular
2/27 - 3/3	5	Context-free grammars
Exam 1 -- sometime around March 1
3/6 - 3/10	6	Pushdown automata
3/13 - 3/17	7	The equivalence of context-free grammars and pushdown automata.
3/20 - 3/24	7	Properties of context-free languages
3/27 - 3/31	SPRING BREAK!!!
4/3 - 4/7	8	Turing Machines
4/10 - 4/14	8	Variations on the Turing machine concept
Exam 2 -- sometime around March 12
4/17 - 4/21	9	Undecidability
4/24 - 4/28	9	Post's Correspondence Problem and other undecidable problems
5/1 - 5/5	10	Intractability. NP-completeness
5/8 - 5/12	10	Cook's Theorem (SAT is NP-Complete)
Final Exam: Thursday, May 18, 9 AM

Grading:

We will have weekly homework assignments (graded by me), 2 in-class exams, and a final exam. In rough terms each hour exam is worth 20% of your final grade, the final is 30%, and the homework is 30%.  Last year I tried have 3 in-class exams and was unable to work the third one in.  If it seems to me to be needed, I reserve the write to have a third hour exam late in the semester. 

The Honor Code

The Honor Code has a straightforward application to this class. You can work together on the homework assignments and you are even encouraged to do so. This is a class where you can learn a lot from other students. You may talk as much as you want about the problems and can even work out solutions together. The only restriction is that each person must write up the solutions by himself or herself. The exams, of course, you must do on your own.