CSU390: Basic Information

Created: Monday, July 24, 2006
Last modified:

Instructor

Name: Ron Williams
Office: 334 West Village H
Phone: 617-373-8683
E-mail: rjw@ccs.neu.edu

Teaching Assistant

Name: Tianhua (Andy) Zheng
Office: 466 West Village H
Phone: 617-373-4605
E-mail: tianhua@ccs.neu.edu

Course

Lecture: Sequence F (TuF 1:35 - 3:15pm)
Room: 108 West Village H

Prerequisites

CSU213, Fundamentals of Computer Science 2
PHLU215, Symbolic Logic

Also vitally important is the material from CSU200, Discrete Structures, which itself is a prerequisite for CSU213.

Text

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

Errata for this text are available on line. If you are concerned that something in the text might be a typo, please check the errata available here: Errata for Introduction to the Theory of Computation, Second Edition by Michael Sipser.

Homework Assignments

There will be almost-weekly written assignments, generally due on Tuesdays and always provided electronically (via this website) at least one week before their due date . 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: CSU390 is a theory course, so a certain level of mathematical rigor will be expected in your solutions in order for you to receive full credit.
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.

Academic Honesty

All work submitted for credit must be your own.
You may discuss the homework problems with your classmates, the teaching assistant, and Professor Williams. 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, including sources found on the web. However, you may not consult any solutions from previous years' assignments whether they are student- or faculty-generated.
If you find a solution to a problem on-line (or somewhere else), you must cite the URL (or other appropriate reference) where you found it. Failure to do this constitutes plagiarism, and will be dealt with in the same manner as any other form of plagiarism. If you do obtain a solution in this way, you will not be penalized as long as you cite the source properly and re-express it in your own words. Of course using solutions already developed by others deprives you of the opportunity to develop your own problem-solving skills, so I strongly discourage you from seeking solutions from outside sources in the first place.
Please ask if you have any questions about academic honesty as it applies to CSU390.

Homework Policy

Homework is due in hardcopy form 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 as follows: Any assignment turned in to me (or to the TA) personally after the assignments are collected at the start of class, but on the same day, will incur a 5% penalty. Any assignment turned in later than that will incur an additional 15% penalty for each additional 24 hours late it is turned in. Each 24-hour period is measured from 1:35 p.m. For example, if an assignment due at Tuesday’s class first appears in my mailbox before 1:35 p.m. the following Thursday, its overall late penalty is 5%+15%+15% = 35%. The maximum late penalty is 50%. Solutions will routinely be provided at the class period following the class period when the assignment is due, so no assignments will be accepted beyond the 50% late penalty period. Also, there will be one or two assignments that will not be accepted late at all because solutions will be provided at that class period to help you prepare for an upcoming exam. When this is the case it will be clearly indicated on the assignment. 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 out of zero points, as if you had not attempted the problem. Otherwise, you will receive 2j out of 2j points. Note that attempting extra problems can only help you. Your grade on an assignment will be reported as two numbers: the points you obtain and the points you effectively attempt. Your homework grade at the end of the term will be calculated as the sum of the points you obtained divided by the sum of the points you effectively attempted.
The purpose of this policy is threefold:

It is designed to not penalize you for skipping some problems.
It is designed to encourage you to attempt all of the problems.
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 three exams. Exams 1 and 2 will each be held during a regularly scheduled class period, and Exam 3 will be held during the time slot allotted for our final exam during finals week.

Grading

Homeworks: 20-30%
Exam 1: 20-30%
Exam 2: 20-30%
Exam 3: 20-30%

A flexible weighting system will be used that assigns 30% of the overall total to each of your two best scores among the homework total and the three exam scores and 20% to each of your two worst scores among these four.

Switch to:

CSU390 Home Page

rjw@ccs.neu.edu