Introduction to Computer Science Theory, 4003-380, 20124

Course Description

This course provides an introduction to the theory of computation, including formal languages, grammars, automata theory, computability, and complexity.

Course Outcomes

  1. Students should demonstrate an understanding of basic concepts in formal language theory, grammars, automata theory, computability theory, and complexity theory.
  2. Students should be able to relate practical problems to languages, automata, computability, and complexity.
  3. Students should demonstrate an increased level of mathematical sophistication.
  4. Students should demonstrate an understanding of and be able to apply mathematical and formal techniques for solving problems in computer science.

Course Web Page


Curtis Menton
Email: last name at
Please include the course name or number (380/theory) in email subject lines so course correspondence is easier for me to find.
Office: 70-3575 (subject to change)

Office hours:


Monday/Wednesday, 4:00PM-5:50PM, 70-3445.


Michael Sipser, Introduction to the Theory of Computation, (Third Edition). The second edition is also acceptable if you have or would prefer to get a used or electronic copy of that. I'll type out the homework questions whenever feasible.

Other Materials

Slides and information about reading and homework assignments, exams, etc. will be linked from the course web page.


The Work

Homework Assignments

There will be eight homework assignments, one per week except for weeks 1 and 6. Homeworks will usually be due on Mondays at 4pm at the start of class, and are posted at least 6 days before they are due. The actual assignments will be available on the homework, reading, and slides page.

Unless it is specifically stated otherwise, you may work on and submit your homework in groups of 1 or 2. If you choose to work as a group of 2, both of you should contribute significantly to the solution for every question. You should submit only one copy of the homework with both your names on it. All authors have to be able to explain all solutions. Whether you submit on your own or with a partner, discussing homework with your fellow students is encouraged. However, after such discussions, all notes must be discarded, blackboards erased, and every group must write up their solutions in private without further consultations with your classmates or any written material other than your class notes, materials handed out in class, the textbook or this webpage. For every problem discussed with other students, state their names and briefly sketch the extent of your discussions (e.g. "solved together", or "clarified problem statement"). You are not allowed to look up the answers to your homeworks. I will not accept late assignments without prior arrangement. I will drop the two lowest homework grades. However, a zero for cheating will not be dropped.

Midterm Exam

The midterm exam will take place in week 5 or 6 during our usual class period. The midterm is closed book and notes but you may bring one sheet of letter-sized paper with your own hand-written notes.

Final Exam

The final is semi-cumulative. It is closed book and notes but you may bring one sheet of letter-sized paper with your own hand-written notes.

Exams can not be made up except for real emergencies in which case proper documentation (like a doctor's note) will be required. If at all possible, you should contact me prior to the exam. Oversleeping, cars that don't start etc. do not constitute a valid excuse.


Numerical grades will be converted to letter grades according to the following scale:
> 88%: A; 77%-88%: B; 66%-77%: C; 55%-66%: D; < 55%: F.

Disputing Your Grade

If you feel that an error was made in grading your homework, quiz, or exam, you have one week from the moment the graded work was handed back to dispute your grade.

Academic Honesty

The DCS Policy on Academic Honesty will be enforced.
You should only submit work that is completely your own. Failure to do so counts as academic dishonesty and so does being the source of such work. Submitting work that is in large part not completely your own work is a flagrant violation of basic ethical behavior and will minimally be punished with failing the course.