The purpose of this course is to study the capabilities and limitations of computers, by formulating mathematically various models of idealized computers and establishing rigorously for these models what kinds of problems can and cannot be solved, as well as what kinds of problems can and cannot be solved with a reasonable amount of computing resources.
This semester, I plan some amount of treatment of at least the following topics, and possibly others if time permits:
Computability theory: Turing machines, Church-Turing thesis, halting problem and unsolvability, universal Turing machine, introductory recursion theory.
Complexity theory: complexity measures, time and space hierarchy, NP-complete problems, intractability
Advanced topics: circuit complexity, probabilistic algorithms, interactive proofs.
The official prerequisite for this course is the undergraduate course CSE 303 (Introduction to the Theory of Computation). You should already have taken a previous course like that one and be familiar with deterministic and nondeterministic finite automata, regular languages and regular expressions, context-free grammars, context-free languages, and pushdown automata, and you should have had at least a brief introduction to Turing machines. The material on finite automata, regular languages, and context-free languages is an important prerequisite, because they often serve as a source of examples of the kind of computational problems studied in computability theory.
| Lecture: | Tuesday and Thursday, 2:30PM-3:50PM, Heavy Engineering Lab 201. |
There will be a midterm exam and a final exam.
| Midterm: | TBA (in class) |
| Final: | Monday, Dec 18, 11:15AM-1:45PM |
I expect the exam questions to be mostly at the level of "exercises", rather than "problems", especially on the midterm exam when time is very limited. In view of the limited time for the midterm, the final exam will potentially cover topics from the entire semester; not just from the second half.
The official book for the course is the following:
The following book might also be helpful to you. I will likely draw on some material from it.
There will be regular homework assignments in this course, given and due at approximately two-week intervals, with about five or six homework assignments in all. The homework scores will contribute to your final grade, though this contribution will be much less than that of the exams. The reason for de-emphasizing homework scores as a component of the final grade is that, in the modern world, a student's ability to turn in solutions to typical exercises that would be assigned in course like can no longer be regarded as a reliable indicator of whether the student has mastered the material. However, to actually succeed in mastering the material, doing the homework exercises (and as many others as you can manage) is essential. In short, you won't learn anything unless you make a serious attempt at the homework. See here for a rather more long-winded explanation of my philosophy on the role of homework exercises in mathematical courses.
Each student must submit their own individual homework writeup. If more than one student submits substantially the same writeup for a particular homework problem, or if there is some other evidence that the writeup you submit is not your own work, I will regard this as evidence that you are trying to get a higher grade without actually doing the required work and may choose either to make a corresponding deduction from your homework score or (in egregious cases) to pursue the matter as a case of academic dishonesty. Having said that, I want to make clear that it is OK and encouraged to discuss homework problems with each other, as long as the writeup you submit is your own work. Personally, though, I think it is best not to discuss a problem with others until you have attempted it yourself first, since it is from that individual attempt that you will derive the most benefit.
Homeworks should be handed in on time. Each homework assignment will be graded in one session only, which might take place as early as the day after the due date for that assignment. Homeworks submitted in time for the grading session will be regarded as on time. Homeworks submitted after the due date run the risk of missing the grading session, and thus not being graded. If your homework assignment is not graded due to late submission, at the instructor's discretion you will receive either a zero for that assignment or you will receive a score equal to the average grade you received on all your homeworks that were graded.
Homework submissions must be typeset and submitted in PDF form.
In view of the mathematical content, use of PDFLaTeX is recommended.
Please don't turn in any handwritten homeworks, .docx
files, or any format other than PDF.
Note: Depending on the number of students who are ultimately registered for the course, and the level of suitable TA or grader support for this class, homework grading could range any where from simple "spot checks" to record whether you attempted the exercises, to a more detailed reading of your solutions. If you are a Ph.D. student who needs this course to pass the qualifiers, then you should expect that I will take a greater personal interest in your homework submissions.
The final grade will be determined as follows: The raw scores obtained by students on each homework assignment will be summed, and the result standardized by representing the sum as a percentage of the total points possible for the homework assignments. The raw scores obtained by a student on each exam will be standardized by converting them to percentile scores. A weighted sum of the resulting standardized scores will then be formed (with weights as shown below) to obtain a composite score for each student.
Finally, the composite scores will be ranked, and the instructor will apply a subjective method of his choice to determine the cutoffs for each grade category. Absolute performance standards, the distribution of composite scores, and information derived from late homeworks are factors likely to contribute to this decision.
"If you have a physical, psychological, medical or learning disability that may impact on your ability to carry out assigned course work, I would urge that you contact the staff in the Disability Support Services office (DSS), ECC Building (behind SAC), 632-6748/TDD. DSS will review your concerns and determine, with you, what accommodations are necessary and appropriate. All information and documentation of disability is confidential."
Students who require assistance during emergency evacuation are encouraged to discuss their needs with their professors and Disability Support Services. For procedures and information go to this web site and search Fire Safety and Evacuation and Disabilities.
Stony Brook University expects students to respect the rights, privileges, and property of other people. Faculty are required to report to the Office of Judicial Affairs any disruptive behavior that interrupts their ability to teach, compromises the safety of the learning environment, or inhibits students' ability to learn.
An outline of the course can be found by clicking on the following link: topics.html.