**Web page:** http://cseweb.ucsd.edu/classes/fa15/cse105-a

**Instructor:** Daniele Micciancio

**Textbook:** M. Sipser, *Introduction to the Theory of Computation* (any edition)

**Lectures:** MWF

- (Section A) 12:00p-12:50p (CENTR 212)
- (Section B) 10:00a-10:50a (CSB 002)

**Discussions:** M 6:00p-6:50p (CSB 002) and M 7:00p-7:50p (CSB 002)

**Exams:**

- Midterm 1: M 10/19/2015, 7:00p-7:50p (CENTR 212)
- Midterm 2: F 11/13/2015, 5:00p-5:50p (CENTR 212)
- Final: W 12/09/2015, 7:00p-9:59p (TBA)

**Course Description:** This course introduces the basic, formal ideas underlying the notion of computation. Syllabus: finite automata, regular expressions, context-free grammars, pushdown automata, Turing machines, decidability, undecidability, the halting problem, Turing reductions, map reductions, introduction to computational complexity.

The formal prerequisites for CSE 105 are CSE 12 and CSE 21, as well as all implied prerequisites of those classes (most importantly CSE 20.) One of Math 15B, Math 100A, or Math 103A may substitute for CSE 21.

We expect you to be comfortable with mathematical concepts such as sets, tuples, relations, and functions. You should in particular be familiar with the notion that a set is (or isn’t) closed under some operation. We expect you to be comfortable with manipulating formal mathematical definitions, reading and writing formal proofs.

We further expect you to be comfortable with basic data structures, such as trees and graphs; with basic algorithms on those data structures, such as depth-first search and graph reachability; with basic tools of algorithm analysis, such as big-O notation; and with general computer and programming concepts, so to be able to easily pick up a new programming language and write short snippets of code.

Our objectives in CSE 105 are: (1) to define computation formally; (2) to show that there are limits to what is computable; (3) to reason precisely about computation and its limits. Along the way, we will pick up some useful tools (finite automata, regular expressions, context-free grammars) and lay the foundation for the study (in CSE 200) of complexity theory.

*Learning outcomes*:

A successful student will learn the following in CSE 105:

- Recall, understand and manipulate formal tuple definitions for DFAs, NFAs, CFGs, and TMs, and understand implications of these definitions and variants thereof.
- Understand and manipulate language definitions written in ``set-builder’’ notation.
- Understand and generate closure-property proofs for claims of the form ``if
*L*is a regular language, then so is*f(L)*’’ for*f*transforming a language into another, and also for other classes of languages than regular languages. - Understand the meaning and implications of closure properties, especially for the standard language operations; e.g., if two languages are not regular, can/must their concatenation be regular?
- Understand and use reductions for decidability and undecidability, and mapping reductions for recognizability.
- Given a language, determine whether it is decidable or undecidable and prove that claim formally and convincingly.

**Exams:** There will be 6-7 homework assignments, 2 midterm exams, and a final. Midterm and Final exams dates/times have been set by the university before registration, and everybody is expected to attend. There will be no make up midterm or final. Not showing up to either exam will count as 0 grade, unless your absence is due to a demonstrated personal health problem at the time. Exams will be closed book, closed notes.

**Homework** assignments will typically go out on Wednesday, and be due after one week. (No late submissions accepted.) Submission instructions will be specified on the class webpage. Your class grade will be based on your Homework submissions (20% total), the two Midterm exams (20% each), and the final (40%).

**Grades** will be available through GradeSource. If you are enrolled in the class you should have received an email from gradesource with instructions and a secret number to access your grades. Final grades will be based roughly on the following scale: 50-55% (D), 55-70% (C), 70-85% (B), 85-100% (A), with (+) and (-) assigned to the instructor discretion. This includes, but is not limited to improvement over the quarter, class participation, and natural “breaks” in the distribution of scores.

**Regrade requests**. Regrades on assignments and midterms are only accepted within a week after the graded object has been returned. Do not modify your solutions after they are returned to you. If you alter your solutions, you loose any right to request a regrade of that exam. Modifying the exam and then bringing it back to ask for a regrade will be treated as a violation of academic honesty rules, and so prosecuted.

**Academic honesty:** All students are expected to be familiar with and abide by the rules of UCSD Policy on Integrity of Scholarship as described in the UCSD General Catalog. In case of cheating, such policy will be enforced. This means an F grade in the course, and action by the Dean of your college (probation or suspension from UCSD).

**Homework and Collaboration Policy**

You are encouraged to form study groups to discuss the material presented in class and the homework assignments. However, you should write the solutions to the homework entirely on your own. If you collaborated with other students on the solution of the homework, you must list the name of everyone you discussed the homework with, and which problems you discussed with whom.

You can use Internet, additional textbooks, and any material you find useful as a study tool. However, the use of any such resource in the solution of homework assignments is prohibited. In particular, you should **not** search for solutions to homework problems on-line, or post homework related questions on any site other than the course web discussion board. Should you still (inadvertently) come across material on the internet that is closely related to the solution of the homework assignments, make sure you clearly aknowledged your source in your solutions to avoid academic dishonesty charges. Posting of your solutions (as a whole, or in part, even after the homework due date) is also prohibited. No form of collaboration is allowed during midterm and final exams.