**CSE 3502: Theory of Computation**

Fall 2016

**Instructor:** Mukul Bansal, ITEB 359, mukul.bansal@uconn.edu

**Time and place:** Tu and Th 9:30AM-10:45AM. LH-305.

**Grader:** Nhan Nguyen (nhan.q.nguyen@uconn.edu).

**Instructor office hours:** Mo and We 9:00AM-10:00AM (ITEB 359) or by appointment.

### Course Description

This course is designed to introduce students to the theoretical foundations of computing. This is the stuff that makes computer science a

*science* and understanding it is crucial for developing a deeper understanding of computing. Topics to be covered in this course include 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), Church-Turing thesis, decidability/undecidability, and NP completeness.

**Prerequisites:** CSE 2100 and CSE 2500

**Textbook:** We will use the book "Introduction to the Theory of Computation" by Michael Sipser; 3rd edition. (The material we will cover is also available in the 2nd edition, but homework will be assigned from the 3rd edition). This may be supplemented by other material from various sources.

**Grading:** Grading will be based on 6 bi-weekly homework assignments (25%), two mid-term exams (20% + 20%) and a final exam (35%). All exams will be closed book. Final grades will be curved, i.e., grading will be relative.

**HuskyCT:** We have a HuskyCT site for the class; you can access it by logging in with your NetID and password at https://lms.uconn.edu. Please check this site regularly for class materials, homework assignments, solutions, grades, assignment clarifications, changes in class schedule, and other class announcements.

**Homework policy:**Homework solutions can be either hand written clearly or printed/typed and must be turned in at the beginning of class on the due date (or earlier). Homework may be turned in up to two days late but at a penalty of 25% of the grade. Students are permitted to discuss general concepts, ideas and questions concerning the homework assignments, but sharing written solutions with others or using solutions provided by others (including those found on the internet), in part or in whole, is prohibited. You are encouraged to seek help from the instructor whenever needed. If you consult any sources other than the course notes or the textbook, you are required to cite the source in your homework and ensure that the submitted work is your own, i.e., written by you in your own words.

*Last updated on Aug 30, 2016*