Policies

What to expect:

This class is going to be hard. There is no way around it. There will be a lot of material. A lot of it is difficult material. It will stretch your brain.

The class will be organized and regularly scheduled. I will do everything I can to arrange it so the total time required is kept reasonable and consistent. Ideally, you will be able to put your outside-of-class work (reading and homework) as a weekly calendar item, just like the lectures.

The Book:

The textbook for this course is Introduction to the Theory of Computation by Michael Sipser. It does not matter if you use the first, second, or third edition. We will follow the book pretty closely. This is supposed to help you. If you don't understand something, you can be confident that you can find it in the book. You should still ask a question if you have one during the lecture.

The Subject Matter:

The course has three main units corresponding to the three parts of the book: Automata, Computability, and Complexity. Additionally, students will be expected to know the basic math of sets, logic, and proofs as presented in Chapter 0 of the book. The specific topics are as follows, however, these are subject to change.

Automata
  • Finite Automata
  • Nondeterminism
  • Regular Expressions
  • Nonregular Languages
  • Context-free Grammars
  • Pushdown Automata
  • Noncontext-free languages
  • Book sections: 1.1, 1.2, 1.3, 1.4, 2.1, 2.2, and 2.3
Computability
  • Turing Machines
  • Turing Machine Variants
  • Decidable Languages
  • Undecidable Languages
  • Book sections: 3.1,3.2,3.3,4.1, and 4.2
Complexity
  • Measuring Complexity
  • The Class P
  • The Class NP
  • NP-Completeness
  • Proving NP-Completeness
  • Book sections: 7.1, 7.2, 7.3, 7.4, and 7.5

Homework:

Late homework will not be accepted. Usually, there will be a homework handed out every Wednesday. Each homework will cover the topics from the two lecture for that week and will be due one week after it has been handed out (i.e., the following Wednesday at the beginning of class). If you will not be in class on a day that the homework is due, it may be submitted by email to me (Don) at least one hour before the start of class.

You can handwrite your solutions but they need to look neat. Typed solutions are encouraged, preferably typeset with LaTeX. If they are sloppily written, hard to read, crumpled up, etc., you will get one warning. If it happens again, you enter the homework doghouse. If you are in the homework doghouse, your work will only accepted if it is typed. For typed homework, drawing figures by hand is okay.

Collaboration:

Collaboration on homework is allowed, but assignments must be written up individually. Collaboration on quizzes is NOT allowed. Collaboration means discussing specific problems with your classmates. Your write-up must be done alone. Do not copy down a solution that you don't understand. This is called cheating and its a serious mistake with serious consequences. If you obtain any part of your solutions with the help of others or other sources, you must identify the sources/people on your submitted homework.

Grading:

The homeworks will combine for 50 percent of your grade.
The midterm will count 20 percent.
The final will count 30 percent.

HuskyCT:

I will be using HuskyCT to distribute announcements, homework, homework solutions, and grades. All other relevant course info and material will be posted to this course website.