Important Dates:
What is this course about? In this course theoretical models for computation and problem solving are studied in the hope of gaining further insight into the what is and isn't possible to solve on a computer. Studying theoretical computational models can also provide a basis for building particular devices and software to solve practical problems arising in fields from compiler design, to network communication and natural language recognition. The main objective of the course is to understand the theoretical underpinnings, rather than the particular applications. In line with its theoretical spirit, homework problems do not involve any serious programming, though some simple stand-alone programming tools such as egrep may be incorporated into some homework assignments.
CS 3261 constitutes the last CS Theory course required to be taken by all CS majors. Other theory courses available include CS 4231 Analysis of Algorithms, CS 4236 Introduction to Computational Complexity which contain portions which are closely related to CS 3261, and CS 4261 Cryptography which utilizes the Turing Machine model. Non-theory courses which benefit from taking CS 3261 include CS 4115 Programming Languages and Translators (3261 is a pre-requisite), CS 4705 Natural Language Processing , and CS 4861 Computer-Aided Design of Digital Systems. The first part of the course (automata theory) is probably of most practical use, and is of fundamental importance in any discipline which uses pattern recognition, from DNA Sequencing to Intrusion Detection.
Pre-requisites: Discrete Math (COMS 3203), and to a lesser degree Data Structures (COMS 3137 or 3139). If you're not sure whether you are ready for this course, try doing the first ten problems in Chapter 0 of the text-book. If you can understand the problems, you should be ready to take this course.
Course web site:
www.cs.columbia.edu/~zeph/3261/
Required Text : Introduction to the Theory of Computation by Sipser (PWS Publishing, ISBN: 053494728X). Available at Labyrinth books (112th between Broadway and Amsterdam)
Recommended References:
Readings and Lectures: The syllabus/schedule (www.cs.columbia.edu/~zeph/3261/schedule.html) contains a list of readings for each lecture. You should complete the book readings before the lecture. Old electronic lecture notes will also be provided for another viewpoint, but you are responsible for the material taught in class, not the lecture notes.
Participation: Part of your grade will be based on participation If you attend all the lectures and respond to questions you are guarantee full participation credit. -->Homeworks: There are 5 homeworks. The homework due-dates are given in the schedule. (www.cs.columbia.edu/~zeph/3261/schedule.html) for a precise list. All the homework problems are located at the homework page (www.cs.columbia.edu/~zeph/3261/hw). Homework solutions will be available online with a password, through the left frame of the homepage (www.cs.columbia.edu/~zeph/3261/) (CLICK ON "SOLUTIONS AND DOWNLOADS").
Homework lateness policy: Some homeworks may not be accepted late, as they must be graded immediately before exams. Such homeworks will be hilighted. Other homeworks may be accepted up to 5 days late, and incur a 10% penalty for each day late. If you hand in homework after the beginning of class, the homework is considered slightly late and incurs a 5% penalty. If you want to hand the homework in late, it will be your responsibility to find the grading TA and hand the work to him/her at the TA's convenience.
Exams : There will be one in-class midterm and a final exam. Not showing up for the final is an automatic course failure. No accomodations can be made for students who miss the midterm or show up late. If there is a reason you cannot come to the scheduled midterm or final please tell us as soon as possible. Quizzes are designed to test basic understanding of the homework, but the midterm and final are more difficult as typical exam question ask you to integrate several concepts
Grading: There will be seperate curves on homeworks and exams. The percentage breakdown after the curve is:
Regrades: If you feel that a problem on a homework or on the midterm was graded incorrectly, we can give you a regrade. Be aware that the TA will regrade the whole assignment (except in cases such as incorrect recording of score) and that your score may go down if mistakes which were previously ignored are discovered. All regrades must be requested within 2 weeks of when the assignment or exam was returned. For homeworks, contact the TA who graded your assignment, but for exams contact the instructor. Grade changes are subject to instructor approval.
Honesty: Homework and exams should constitute your own work. You are encouraged to discuss homeworks with other students, but in such a case you should list all the people that you collaborated with on the top of the submitted work. You should not copy solutions from other students. Further information about our department's cheating policy can be found at www.cs.columbia.edu/home/academics/cheating.html.
Here are typical examples of what does and does not constitute cheating:Uncollected work: A designated TA or the instructor will hold on to any homework or midterm that you didn't pick up.
Special circumstances: If there are reasons beyond your control which make it impossible to follow one of the above policies, you should inform us as soon as possible. You will need to properly document your special situation.