CS 520: Introduction to the Theory of Computation

Fall 2005

Instructor:

• Deborah Joseph
• Office: 4382 CS
• Office Hours: 3:30-4:30 Tuesday.
  Each week I will try to list additional hours when I expect to be in my office.
• Email:

Teaching Assistant:

• Not Known
• Office: Not Known CS
• Office Hours: Not Known or by appointment.
• Email:

Lecture:

• Room: 119 Babcock
• Hours: TR 11:00 - 12:15.

Homeworks:

• Homework 1 (pdf) Due: Oct. 11, 2005.
• Homework 2 (pdf) Due: Nov. 10, 2005.
• Homework 3 (Edition 1 of text book: 7.5, 7.6, 7.7, 7.9, 7.10, 7.19. Edition 2: 7.5, 7.6, 7.7, 7.8, 7.9, 7.21.) Due: Dec. 15, 2005.

What's Happening in Class:

Click here.

Additional Material:

• Here is a note on quadratic time lower bound for single-tape Turing Machines. Read section 5.2. It can also be accessed from http://www-cc.cs.uni-sb.de/cct/, go to lecture 5.

---

Course Description:

This course is a survey of the basic concepts of the theory of computation, including context-free and context-sensitive languages, regular sets, finite and pushdown automata, Turing machines, undecidable problems, complexity with respect to time and space, NP-completeness, and reducibilities. Prereq: CS 367 and Math 240, or consent of instructor.

Books:

• Required Text : Michael Sipser, "Introduction to the Theory of Computation", PWS Publishing Company, 2005. (The website contains errata.)

Exams:

Midterm: Nov. 22, 5:30 pm - 7:00 pm, 1257 CS. No class that day.
Practice problems

Grading Policy:

• Homeworks : 50%
• Mid-term: 25%
• Final exam OR project: 25%