Contact Information

Course Description: (From the catalog) This course provides an introduction to theoretical computer science. The course covers the fundamentals of automata theory, formal languages and computability theory. Several distinct models of computation, including the Turing Machine, will be introduced. The concepts of computability, decidability and reducibility will be explored.

Course goals

Some of the material is directly used in other courses; a bit of complexity theory is needed in Algorithm Analysis and Design. Most people already know a little about computability and non-computable functions. Regular expressions are such useful tools that we introduce them early in the curriculum.

So students are likely to have seen some of the material before, but without the accompanying mathematics and proofs.

Upon completion of the course, a student should be able to do the following:

• Describe the FSA and Turing Machine models of computation
• Prove the non-computability of the Halting problem
• Explain algorithm complexity
• Describe some of the NP-complete problems

Course Objectives

• understood many of the proofs of the basic theorems of computational theory.
• learned some of the models used in computer science
• reviewed some some of the discrete math concepts used in computer data structures, including sets, sequences, and graphs
• reviewed and used basic proof techniques
• learned many of the best-known mathematical results in our field.

Attendance policy

My grading reflects my expectation of seeing you regularly.

Quizzes and exams are ordinarily due in the period in which they are given, and may not be turned in later, although they may be excused if you have a convincing story, such as your grandmother getting married in Provincetown.

Anything turned in by midnight is on time, and unless I am actually in my office at midnight, anything I find in the Blackboard dropbox on the following morning is assumed to have been turned in on time.

Papers and programming assignments are similarly due by midnight. Late papers and programs may be accepted after their due date, but I am likely to mark them down for lateness.

Course resources

The textbook for this course is

Michael Sipser Introduction to the theory of computation PWS Publishing/Cengage Learning

The book is fairly expensive new from the bookstore.

If you are willing to wait a few days to order it online, you can obtain much more cheaply used. I usually buy used books from Abebooks.com, but Ebay and Amazon both carry used books.

There are many editions available. I planned my syllabus using the 2007 India edition, and there isn't a whole lot of difference between the later editions. The bookstore will probably carry only the third US edition. You won't be surprised to learn that the newer edition is usually more expensive used.

Because the chapter numbering differs between the various editions, I refer to chapters and sections by name instead of by number.

From time to time I will put programs from lectures on the web.

I usually record grades in blackboard.

Reading and Lab Project Schedule:

• Friday lab section schedule

Final Exam

Topics

Grading

Tentative grade rubric:

1. There will be several pop quizzes, making up in total 10% of the final grade.
2. I'll assign homework, which will be 20% of the final grade, but will probably constitute the most valuable part of the course. Don't skimp on it! I will collect homework -- that's how I can give a grade on it -- but I will not mark or return it. I will just tally whether you turned it in or not, although I may skim your paper to see if you actually did anything. Instead of grading, we will discuss each week's homework in class. Since I'll collect the papers before the discussion, you may want to keep notes to refer to during the class discussion.
3. There will be a final exam and midterms, which will make up 60% of the final grade.

   The exam questions will be similar to the homework, and will in fact often have already been assigned as homework, so doing the homework is the best preparation for the exam.

4. The remaining 10% of the grade will be based on class participation and other utterly subjective measures.

Late work

I do not consider homework which is emailed to me to be turned in on time, no matter when you sent it. Instead use the Blackboard dropbox.

There are no makeup or early exams, but I may excuse an exam for a good story, presented in advance, like your grandmother getting married that day in Provincetown.

Each student is responsible for completing all course requirements and for keeping up with all activities of the course (whether a student is present or not).

Academic Honesty

I consider it plagiarism to share typing or fail to give credit to other peoples' ideas.

Fitchburg State has an Academic Dishonesty policy, which can be found in the college catalog. Penalties for academic dishonesty, including submitting work which is not your own, and assisting other students on examinations, can be severe.

Accommodation