CISC 401/601 -- Fall 2009

T/Th 11:00-12:15pm, 114 Pearson

Instructor: Vijay Shanker	TA:  Scott Grauer-Gray
Office: Room 442 Smith Hall	Office: 103 Smith Hall
Hours: Tuesday 1:00-2:00pm, Wednesday 8:45-9:45	Hours: Wednesday 1:00-3:00pm
Phone: 831-1952	Phone: 831-
Email: vijay@cis.udel.edu	Email: sgrauerg@gmail.com

Textbook

• Computability, Complexity and Languages: Fundamentals of Theoretical Computer Science, Second Edition, by M Davis, R. Sigal and E. Weyuker, Academic Press, New York, NY

Additional References

• Introduction to Automata Theory, Languages and Computation, Second Edition, by J. E. Hopcroft, R. Motwani, and J. D. Ullman, Addison Wesley, Reading, MA, 2001.

• Elements of the Theory of Computation, Second Edition, H. Lewis and C. Papadimitriou, Prentice-Hall, Upper Saddle River, NJ, 1998

Syllabus

• Computability Theory: Unlimited register machines, Turing machines, partial recursive functions; the Church-Turing thesis; algorithmically unsolvable problems and diagonalization; primitive recursive functions; universal programs; recursively enumerable and recursive sets; the recursion theorem; Rice's theorem.
• Formal Language Theory: Deterministic and non-deterministic finite automata and their equivalence to regular expressions, pumping lemma and Myhill-Nerode theorem; context-free grammars and languages, and the corresponding pushdown automata.

Grading

Homeworks:

There will be about 5-6 written homeworks. They will have to be turned in at the beginning of the class on the due date. No late submission will be accepted without prior permission of the instructor.

Exams:

There will be a mid-term and a final exam.

Overall Course Grade:

40% Final

30% In-class Midterm exam

30% Homework

The grades for 404 and 604 students will be maintained seperately. The midterm and final exams may be different for the 404 and 604 students.

Retain copies of your class notes, handouts, homeworks, and solutions (when provided). Exam questions will generally be similar to homework problems or results presented in class.

In case of questions regarding graded material, first you should contact the TA.  Then, if you still have questions, contact the instructor.  For other questions, you may contact either the instructor or the TA.

Cooperative efforts at understanding the material conceptually are encouraged. However, all written work you turn in must be entirely your own. Submitting work that is not your own is considered cheating, as per Departmental and University policy.

Helpful Prior Knowledge

CIS 303 or equivalent or at least one course in which the student was required to prove theorems. You are responsible on your own for the mathematical preliminaries. If you need some additional help, exercises, etc. please meet me in my office. 

Homeworks

Homework 1 due date: Thursday, September 24, 2009. NO late submission

Homework 2 due date: Thursday, October 1, 2009. NO late submission

Homework 3 due date: Thursday, October 15, 2009. NO late submission

Homework 4 due date: Tuesday, November 17, 2009. NO late submission

Homework 4 will count as 2 homeworks (hence there is no Homework 5).

Homework 6 due date: Tuesday, November 24, 2009. NO late submission

Homework Solutions

Homework 1 solutions can be found here .

Homework 2 solutions can be found here .

Homework 3 solutions can be found here .

Handouts