The CS3800 10F Homepage

You have reached the homepage for the Northeastern University, College of Computer and Information Science, Fall 2010 session of Theory of Computation, also known as "CS3800 10F." CS3800 is an undergraduate course on the theory of computation. This course serves as an introduction to formal models of languages and computation. Topics covered include finite automata and regular languages, pushdown automata and context-free languages, Turing machines, computability, and NP-completeness.

This document, and all documents on this website, may be modified from time to time; be sure to reload documents on occasion and check the "last modified" date against any printed version you may have.

Contents

• Basic Course Information (below)


• Course Schedule (different page), includes homeworks and handouts

Basic Information

Instructor

• Name:Emanuele Viola
• Office:246 West Village H
• Office hours:After class in room 246 West Village H until 5:30 pm.
• Phone: 373-8298
• E-mail: viola@ccs.neu.edu

Teaching Assistant

• Name: Eric Miles
• Office:266 West Village H
• Office hours:Tuesday and Friday 11am-1pm.
• Phone:373-8340
• E-mail: enmiles@ccs.neu.edu

Course

• Lecture: Monday and Wednesday, 2:50 pm - 4:30 pm.
• Room:West Village H 108.

Prerequisites

• CS2510, Fundamentals of Computer Science 2
• CS2800, Logic and Computation

Text

• Required: Introduction to the Theory of Computation, Second Edition , by Michael Sipser.

Homework

• There will be weekly written assignments, generally handed out on Wednesdays and due the following Wednesday. Some of the exercises will be routine, but others will be more challenging. I do not expect you to solve all of the homework problems, but I hope that you will benefit from working on the more difficult ones. A few hints on the homework assignments:
  • Start early: Difficult problems are not typically solved in one sitting. Start early and let the ideas come to you over the course of a few days.
  • Be rigorous: CS3800 is a theory course, and as such, a certain level of mathematical rigor will be expected in your solutions.
  • Be concise: Express your solutions at the proper level of detail. Give enough details to clearly present your solution, but not so many that the main ideas are obscured.
  • Work with others: Some of the problems will be difficult, and it will often be helpful to discuss them with others. Feel free to form study groups. However, the idea is for everyone to understand the problems and experience working through the solutions, so you may not simply "give" a solution to another classmate. In particular, each student must write up his or her own homework solutions and must not read or copy the solutions of others. If you work with others on a problem, you must note with whom you discussed the problem at the beginning of your solution write-up.

Homework Policy

• Homework is due at the beginning of class on the announced due date. You will be granted one homework extension, to be used at your discretion, no questions asked. After the first late assignment, unexcused late assignments will be penalized 20% per calendar day late. I normally will not accept assignments after the date on which the following assignment is due or after the solutions have been handed out, whichever comes first. If you will have a valid reason for turning in an assignment late, please see me in advance to obtain full-credit.

Homework Grading

• We will employ a somewhat unusual grading scheme. Each homework assignment will have n problems, and each problem will be worth k points. You will be required to attempt any m problems. (The parameters n, m and k will vary from assignment to assignment.) These m problems will be graded in the usual manner: you will receive full or partial credit out of k points. You may also choose to attempt the remaining n-m problems. These problems will be graded as follows. Say that you would have received a score of j points if this problem had been graded normally. If j is less than k/2, then you will receive zero points. Otherwise, you will receive 2j points. Note that attempting extra problems can only help you. Your grade on an assignment will be reported by two numbers: the regular-credit points R you obtain and the extra-credit points E you obtain. Your final grade for that problem set is: (R + E)/(m*k + E).
  Intuitively, getting R regular credit points takes you to the fraction 0 <= R/(m*k) <= 1. Then, solving extra credit problems takes you closer to 1.
  The advantage of solving an extra credit problem is usually smaller than that of solving another regular credit problem. Hence you are usually better off declaring regular credit for those problems you are sure about.
• The purpose of this policy is threefold:
  1. It is designed so as not to penalize you for skipping some problems.
  2. It is designed to encourage you to attempt all of the problems.
  3. It is designed specifically to discourage you from writing up long answers which you suspect are incorrect, in the hopes of picking up a point or two.
• Note: Your free late assignment and any unexcused late assignments will only be graded for regular problems. Excused late assignments (e.g., due to illness) will be graded for both regular and extra credit.

Exams

• There will be a midterm and a final exam. The midterm exam will be held during a regularly scheduled class period, and the final exam will be held during finals week. Both exams are open book.

Grading

• Homeworks: 50%
• Midterm: 25%
• Final: 25%

Academic Honesty

• All work submitted for credit must be your own.
• You may discuss the homework problems with your classmates, the teaching assistant(s), and the professor. You must acknowledge the people with whom you discussed your work, and you must write up your own solutions. Any written sources used (apart from the text) must also be acknowledged; however, you may not consult any solutions from previous years' assignments whether they are student or faculty generated.
• Please ask if you have any questions about academic honesty as it applies to CS3800.

Further reading

• The classic book Introduction to Automata Theory, Languages, and Computation covers more than we do in this class.
• To learn more about complexity theory, good starting points are the book Computational Complexity: A Modern Approach (free), and the Electronic Colloquium on Computational Complexity.