CSE 3502: Introduction to the Theory of Computation
Fall 2018

  Prof. Dina Goldin
Computer Science & Engineering, UConn


Important Information 

Lecture Room: MCHU 306
Lecture HoursMonWed 5-6:15PM

Instructor: Dina Goldin
Office: ITE 230
Office Hours: MonWed 4:15-4:45pm, 6:30-7pm


Misagh Kordi misagh.kordi@uconn.edu
Office Hours:
Tue 2-3pm, Wed 2-3pm in ITE 140


Sam Sledzieski samuel.sledzieski@uconn.edu
Office Hours: Mon 1-2pm, Fri 1-2pm in ITE 140


o   Lecture Notes

o   Homeworks and Handouts 

o   Course Description and Syllabus

o   Course Policy and Honor Code

o   Textbook

o   Miscellaneous Links


Course Description and Syllabus

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.

o   Course syllabus

Course Policy

There will be weekly short (5-minute) quizzes, weekly homeworks, a midterm and a final.  The final grade will be computed as follows:

homeworks                        30%
quizzes                               15%
midterm exam                   20%  
final exam                         35%

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.

o   CSE 3502 Honor Code

Between lectures, we will communicate with you via the "announcements" page, linked at the top of this homepage.  Please check for new announcements regularly.

Homeworks and Handouts

All homeworks will be handed out on-line, in this section. Unless directed otherwise, they will be turned in in class, on paper.

o   Homework 0: questionnaire - due by email before 4pm on Wednesday, September 5

o   Homework 1: regular expressions - due in class on Wednesday, September 12

o   Homework 2: finite state automata - due in class on Wednesday, September 19

o   Homework 3: regular and non-regular languages - due in class on Wednesday, September 26

o   Homework 4: context-free grammars - due in class on Wednesday, October 3

o  Homework 5: push-down automata - due in class on Wednesday, October 10

o  Homework 6: non-context-free languages - due in class on Monday, October 15

o  Practice Midterm

o  Homework 7: TM programs - due by email at 4pm on Wednesday, October 31

o  Homework 8: TM Variants - due in class on Wednesday, November 7

o  Homework 9: Decidability - due in class on Wednesday, November 14

Lecture Notes

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. 

o   Lecture 1, 8/27/18 - Introduction

o   Lecture 2, 8/29/18 - Regular Expressions

o   Lecture 3, 9/5/18 - Regular Languages

o   Lecture 4, 9/10/18 - DFAs

o   Lecture 5, 9/12/18 - NFAs

o   Lecture 6, 9/17/18 - Regular Language Theorem

o   Lecture 7, 9/19/18 - Closure Rules

o   Lecture 8, 9/24/18 - Context-Free Grammars

o   Lecture 9, 9/26/18 - Parse Trees

o   Lecture 10, 10/1/18 - Push-Down Automata 

o   Lecture 11, 10/3/18 - From PDAs to CFGs

o   Lecture 12, 10/8/18 - Closure Rules for CFLs

o   Lecture 13, 10/10/18 - Non-context-free Languages

o   Lecture 14, 10/22/18 - Turing Machines

o   Lecture 15, 10/24/18 - TM Diagrams

o   Lecture 16, 10/29/18 - TM Variants

o   Lecture 17, 10/31/18 - Nondeterministic TMs

o   Lecture 18, 11/5/18 - Enumerator TMs

o   Lecture 19, 11/7/18 - Decidability

o   Lecture 20, 11/12/18 - Undecidability



Introduction to the Theory of Computation by Michael Sipser, 3rd edition
ISBN 113318779X

o   Textbook link on Amazon

NOTE: the "LOOK INSIDE" feature on this website gives access to the full text for Chapter 0 of the textbook.

Miscellaneous Links

o   Proof of Problem 1b on Homework6

o  Why it's better to take notes by hand. 

         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

         Leaflet from the Technical Youth Program (PDF)

The Technical Youth Program at is a free service for UCONN students, which offers:

o   Resume critiques from local recruiters

o   Technical interview preparation

o   Market insight into technical roles within companies in the Hartford, Stamford, and Boston location

Their goal is "to help students find a role after graduation, that fits their passions in the technical field".  They "partner with clients throughout the northeast, to fill their entry-level roles."