CSC 7050
Theory of Computer Science
A required course in the FSU MSCS program.
Spring 2015 -- 3 credit hours

5:00PM-7:30PM Thu: Jan 22-May 8Edgerly 102

Contact Information

Instructor:Stephen Taylor
Office: Edgerly 312A and sometimes Edgerly 101
Office hours: T,W,R: 12:30-3:30 (and by appointment)
Web page:
Office phone: 978-665-3704
Home phone: 508-867-9288

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

Course Goals: The purpose of this course is to develop students' understanding of the mathematical foundations of the study of computation.

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:

Course Objectives

Upon successful completion of the course, a student will have:

Attendance policy

There are class meetings each week. I expect you to attend them all. Please talk to me if this creates a schedule conflict for you.

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, 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:

Final Exam

There is a final exam, and three mid-term exams, all of which are in very similar formats, although of course they cover different material.



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

Deadlines are made to be bent, but exceptions create extra work for me. Assignments are due at the beginning of class. I may give credit or partial credit for late work, but you should talk to me as soon as you know it will be late. I will always give at least partial credit for partial work turned in on time, so turning in something incomplete but on time is a sensible strategy.

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 expect you to be so interested in your projects and labs that you discuss them with everyone, including your mom, your little brother, and other members of the class (who will at least know what they're being sympathetic about.) So I won't be too surprised if several people come up with the same idea, or even the same programming trick. But I want you to do each homework yourself, and I don't want you to share typing, even if you both worked on the problem together, and you can't really tell anymore who came up with what. (Except of course for group projects, for which the group will be designated in advance.) To keep from confusing me, your homework should mention everyone you talked to and every web site you looked at. You can only skip mentioning your little brother, if you think he wasn't any help at all...

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.


If you require course adaptations or accommodation because of a disability or acute medical condition or if you require assistance in the event of an emergency evacuation of the classroom, please see the instructor as soon as possible. Students with disabilities are encouraged to register with the Office of Disability Services on the 3rd floor of the Hammond Building.