CSE 237: Introduction to the Theory of Computation
Computer Science & Engineering, U.Conn

  Prof. Dina Q Goldin
http://www.cse.uconn.edu/~dqg/cse237

Spring 2006, MW 11:00 AM - 12:15 PM, BRON 124

Contents of CSE 237 Home Page

• Course Description and Syllabus
• Textbook
• Course Policy
• Homeworks and Handouts
• Lecture Schedule and Notes
• Links

Course Description and Syllabus

Introduction to theoretical aspects of computing, including models of computation, formal languages, and inherent limits on computation. Church's thesis and undecidability. Complexity classes and NP completeness. Theoretical basis of design and compiler construction. Prerequisite: CSE 254.

• Course syllabus

Textbook

Introduction to the Theory of Computation, 2nd edition, by Michael Sipser
PWS Publishing Company 1997,  ISBN #0-534-950973

Please note the list of corrections for the text.

Course Policy

There will be regular homeworks, a midterm and a final.  The final grade will be computed as follows:

class participation             5%
homeworks                        35%
midterm exam                    25%
final exam                          35%

The homework sets are assigned on Wednesday, unless otherwise specified.  Each is due in class on Wednesday, a week after it is assigned. You are allowed to submit late (at the following lecture) one homework, which will account for anyone having problems with illness, emergency, etc. No other late homeworks will be accepted. 

Collaboration policy: You are encouraged to discuss problems and projects in a group. However, you must write up the solutions/programs in your own words. Copying is strictly forbidden. If you use any source other than the text, reference it/him/her in your solution/program, whether it be a person, a book, a solution set, a web page or whatever.

Homeworks and Handouts

The following criteria are important for judging the quality of problem solutions:

     correctness (of the whole solution, not just the final answer);
     clarity (being able to state your thoughts clearly using proper terminology);
     conciseness (do not include unnecessary or irrelevant information).

All homeworks will be handed out on-line, in this section. Except for the questionnaire, they will be turned in on paper, in class.

• Questionnaire (homework 0) - due 1/23/06, before class
• Homework 1 - due 2/01/06, in class
• Homework 2 - due 2/08/06, in class
• Homework 3 - due 2/15/06, in class
• Homework 4 - due 2/22/06, in class
• Homework 5 - due 3/01/06, in class
• Homework 6 - due 3/15/06, in class
• Homework 7 - due 3/22/06, in class
• Solution for Homework 5, problem 3 (PDF)
• Homework 8 - due 4/10/06, in class (and some by email)
• Homework 9 (PDF) - due 4/17/06, in class
• Homework 10 - due 4/24/06, in class (one more to go after this!)
• Homework 11a - due 4/28/06, in review session
• Homework 11b - due 4/28/06, in review session

Please refer to the Course Policy section for our collaboration policy.

Lecture Schedule and Notes

Below is a tentative schedule for the semester. There will be lecture notes posted here after each lecture. These notes summarize what was covered in each lecture, what to read, what to pay attention to; they are NOT a replacement for attending class.

Useful Links

• Cute but undecidable problems (PDF handouts): Post Correspondence Problem (PCP) and Unbounded Tiling Problem
• Turing Machine Simulator. There is a link to documentation at the bottom. The easiest way to start playing with it is to load either a subtractor or a palindrome detector, and step through computations for various inputs. Note that this TM is not exactly the same as what we have seen in class. For example, it has only one halting state H; it also handles moving-left-at-start differently.
• The Church-Turing Thesis: Breaking the Myth. My paper about why the claim at the beginning of Chapter 3 is wrong (11 pages in PDF format)
• Here is the Wikipedia page about Normal Forms. It lists Chomsky Normal Form, as well as Greibach Normal Form for context-free grammars. It also has many others, from such fields as logic, databases, and linear algebra.
• Backus-Naur form is a special notation for specifying context-free grammars that is often used to describe the syntax of programming languages. Here is the Wikipedia page about it. Here is C syntax in Backus-Naur form. Here is SQL syntax in Backus-Naur form.
• Regular expressions can be found in some programming languages (PERL) and in some utilities (VI, grep).  Here is a Wikipedia definition of regular expressions that discusses this.
• Spring 2006 Schedule of CSE classes
• Spring 2006 UConn academic calendar