Theory of Computer Science

A required course in the FSU MSCS program.

Spring 2015 -- 3 credit hours

Meeting

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

Instructor: | Stephen Taylor |

Office: | Edgerly 312A and sometimes Edgerly 101 |

Office hours: | T,W,R: 12:30-3:30 (and by appointment) |

Web page: | http://computersystemsartists.net/ |

Email: | staylor@fitchburgstate.edu |

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.
*

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

- 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.

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.

The textbook for this course isMichael Sipser

Introduction to the theory of computationPWS Publishing/Cengage LearningThe 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.

Tentative grade rubric:

- There will be several pop quizzes, making up in total 10% of the final grade.
- 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.
- 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.

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

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).

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.