Prof. Dina Goldin
Computer Science & Engineering, UConn
http://www.cse.uconn.edu/~dgoldin/cse3502
Important Information
Lecture
Room: UTEB 150 Instructor:
Dina Goldin |
TA: Siena Biales Email: siena.biales@uconn.edu Office
Hours: |
o Course Description and Syllabus
o Course Policy and Honor Code
o Textbook
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.
There will be weekly short (5-minute) quizzes, weekly homeworks, a midterm and a final. The final grade will be computed as follows:
homeworks
35%
quizzes
15%
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.
o
Homework 0 (Questionnaire)
o
Homework 1 (Regular Expressions)
o
Homework 2 (Finite State Automata)
o
Homework 3 (non-regular languages)
o
Homework 4 (Context-Free Grammars)
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 (Introduction) -- 1/16/18
o Lecture 2 (Regular Expressions) -- 1/18/18
o Lecture 3 (Finite State Automata) -- 1/23/18
o Lecture 4 (DFAs vs. NFAs) -- 1/25/18
o Lecture 5 (REs to NFAs) -- 1/30/18
o Lecture 6 (NFAs to DFAs, closure) -- 2/1/18
o Lecture 7 (non-regular languages) -- 2/6/18
o Lecture 8 (context-free grammars) -- 2/8/18
o Lecture 9 (parse trees) -- 2/13/18
o
Lecture 10 (push-down automata) -- 2/20/18
Introduction
to the Theory of Computation by Michael Sipser,
3rd edition
ISBN 113318779X (2nd ed. is fine as reading material, but not for homeworks)
o
Link to textbook website
Note; the "LOOK
INSIDE"
feature on this website gives access to the full text for Chapter 0 of the
textbook.
o Why it's better to take notes by hand.
o Leaflet from the Technical Youth Program (PDF)
The Technical Youth Program at is
a free service for UCONN students, which offers:
·
Resume critiques from local recruiters
·
Technical interview preparation
·
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."