CSU390: Basic Information

Created: Thursday, January 05, 2006
Last modified:

Instructor

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

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.

There will be almost-weekly written assignments, generally due on Fridays 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.
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.

All work submitted for credit must be your own.
You may discuss the homework problems with your classmates, the grader or 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 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 grader) personally after the assignments are collected at the start of class, but on the same day, will incur a 10% penalty. Any assignment due on Friday will incur a 30% late penalty if it appears in my mailbox by 1:30 the following Monday; if handed in after that but by the start of Tuesday’s class it will incur a late penalty of 50%. (If Monday is a holiday, then the 30% penalty option is not available.) Solutions will routinely be provided at Tuesday’s class following the Friday 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.

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.

There will be three exams, each given equal weight. 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.