Computer Science 383

Theory of Computer Science

Spring, 2005

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, that was after Gutenberg....). 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 said to be much 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 difficult material at the end of the course.

Week	Chapter	Topic
Feb 7-11	1 - 2	Introduction; finite automata
Feb 14-18	2 - 3	Regular expressions; the equivalence of regular expressions and finite automata
Feb 21 - 23	4	Regular languages. Determining whether a language is regular
Feb. 25	No class; I will be in St. Louis
Feb 28 – March 4	5	Context-free grammars
Exam 1 -- sometime in the week of March 1-5
March 7- 11	6	Pushdown automata
March 14 -18	7	The equivalence of context-free grammars and pushdown automata.
March 21 - 25	7	Properties of context-free languages
March 28 - April 1	SPRING BREAK!!!
April 4 - 8	8	Turing Machines
Exam 2 -- Friday, April 9??
April 11 - 15	8	Variations on the Turing machine concept
April 18- 22	9	Undecidability
April 25 - 29	9	Post's Correspondence Problem and other undecidable problems
May 2 - 6	10	Intractability. NP-completeness
May 9 - 13	10	Cook's Theorem (SAT is NP-Complete)
Final Exam: Thursday, May 19, 2PM.

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.