Prof. Dina Goldin
Computer Science & Engineering, UConn
Room: LH 301
TA: Anna Gorbenko
· Course Policy and Honor Code
Formal models of computation, such as finite state automata, pushdown automata, and Turing machines, and their corresponding elements in formal languages (regular, context-free, recursively enumerable). The complexity hierarchy. Church's thesis and undecidability. NP completeness. Theoretical basis of design and compiler construction. Prerequisite: CSE 2100, CSE 2500.
There will be weekly short (5-minute) quizzes, weekly homeworks, a midterm and a final. The final grade will be computed as follows:
midterm exam 20%
final exam 30%
You are encouraged to discuss homework problems in a group. BUT write your own solutions and state on the paper with whom you have discussed the problems together. The following criteria are important for judging the quality of a solution:
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).
No late homeworks will be accepted. The grade for two worst homeworks and two worst quizzes will be dropped, which will account for anyone having an illness, emergency, etc.
The University regulations and the CSE 3502 Honor Code will be applied to all cases of plagiarism and academic misconduct.
Between lectures, we will communicate with you via the "announcements" page, linked at the top of this homepage. Please check for new announcements regularly.
All homeworks will be handed out on-line, in this section. Unless directed otherwise, they will be turned in in class, on paper.
· Homework 1 (Regular Expressions and FSAs), due Wednesday 9/13/17
· Homework 2 (DFAs, proofs) due Wednesday 9/20/17
· Homework 3 (NFAs and non-regular languages) due Wednesday 9/27/17
· Homework 4 (Context Free Grammars) due Wednesday 10/4/17
· Homework 5 (Push-Down Automata) due Wednesday 10/11/17
· Practice Midterm (extra credit problem due Monday 10/16/17)
· Homework 6 (TM Simulator) due Wednesday 11/1/17
· Homework 7 (TM Variants) due Wednesday 11/8/17
· Homework 8 (Decidability) due Wednesday 11/15/17
· Homework 9 (Undecidability) due Wednesday 11/29/17
· Homework 10 (P and NP) due Wednesday 12/6/17
These notes are updated after each lecture. They will summarize what was covered in each lecture, tell you what to read, what to pay attention to, etc.
· Lecture 1 (Introduction) 8/28/17
· Lecture 2 (Regular Expressions) 8/30/17
· Lecture 3 (Finite State Automata) 9/6/17
· Lecture 4 (DFAs and NFAs) 9/11/17
· Lecture 5 (REs to NFAs) 9/13/17
· Lecture 6 (Converting NFAs to DFAs) 9/18/17
· Lecture 7 (Non-regular Languages) 9/20/17
· Lecture 8 (Context-Free Grammars) 9/25/17
· Lecture 9 (CFG Properties) 9/27/17
· Lecture 10 (Push-Down Automata) 10/2/17
· Lecture 11 (Converting CFGs to PDAs) 10/4/17
· Lecture 12 (Converting PDAs to CFGs) 10/9/17
· Lecture 13 (Non-context-free Languages) 10/11/17
· Lecture 14 (Turing Machines) 10/23/17
· Lecture 15 (TM Diagrams) 10/25/17
· Lecture 16 (Multitape TMs) 10/30/17
· Lecture 17 (Nondeterministic TMs) 11/1/17
· Lecture 18 (Enumerators) 11/6/17
· Lecture 19 (Reductions) 11/8/17
· Lecture 20 (Undecidability) 11/13/17
· Lecture 21 (Mapping reductions) 11/15/17
· Lecture 22 (Time complexity) 11/27/17
· Lecture 23 (PTIME reductions) 11/29/17
· Lecture 24 (Complexity Hierarchy) 12/4/17
to the Theory of Computation by Michael Sipser,
ISBN 113318779X (2nd ed. is fine as reading material, but not for homeworks)
· Link to textbook website
Note; the LOOK INSIDE feature on this website gives access to the full text for Chapter 0 of the textbook.
Turing Machine simulator: http://morphett.info/turing/turing.html
Here is a link to a great paper about the
history of the incorrect CTT:
Refuting the Strong Church-Turing Thesis: the Interactive Nature of Computing (PDF)
Minds and Machines, 18:1, pp.17-38, March 2008
This page last updated on 8/23/17