Welcome to CSE 105! This course will help you answer fundamental questions about computing:
**even before there were any physical computers**. You'll also learn about the relationship of these models to some essential tools in a computer scientist's toolkit, such as regular expressions and context-free grammars. Finally, you'll develop your technical communication skills in writing formal arguments and proofs.

- What problems are computers capable of solving?
- What resources are needed to solve a problem?
- Are some problems harder than others?

- Prof: Shachar Lovett, email: slovett@ucsd.edu, office hours: W 2-4pm, CSE 4234
- TAs:
- John Clara, email: jclara@ucsd.edu, office hours: T 11am-1pm
- Nicholas Genise, email: ngenise@ucsd.edu, office hours: Th 4-6pm
- Kaave Hosseini, email: skhossei@ucsd.edu, office hours: T 1-3pm
- Chandana Lakshminarayana, email: clakshmi@ucsd.edu, office hours: F 3:30-5:30pm
- Sankeerth Rao, email: skaringu@ucsd.edu, office hours: Th 9-11am
- Kevin Yin, email: h3yin@ucsd.edu, office hours: M 4-6
- Jiapeng Zhang, email: jiz173@ucsd.edu, office hours: F 11-1

- Lecture: MW 5-6:20pm, Peterson Hall 108
- Discussion:
- A01: M 3-3:50pm, Pepper Canyon Hall 122
- A02: W 12-12:50pm, Center 212
- A03: F 8-8:50am, Pepper Canyon Hall 122
- A04: F 2-2:50pm, Center 216

Michael Sipser, Introduction to the Theory of Computation, 3rd ed.

We will use the international edition, which is much more affordable. It is available on Amazon for about $15, or the bookstore for $17.50.

See also the errata for a list of known typos/errors in the book.

We will use the international edition, which is much more affordable. It is available on Amazon for about $15, or the bookstore for $17.50.

See also the errata for a list of known typos/errors in the book.

The final grade will be composed as follows:

- Final exam: 40% (must pass to pass class)
- Midterms: 30% (2 midterms; lowest grade dropped)
- Homework: 20% (7 homeworks; the lowest grade is dropped)
- Participation: 10% (see explanation below)

- A range (A-,A,A+): 88.0% - 100%
- B range (B-,B,B+): 75.0% - 87.9%
- C range (C-,C,C+): 60.0% - 74.9%
- D: 50.0% - 59.9%
- F: below 50.0%

Homework is 20% of the final grade. There will be 7 homeworks, your lowest grade will be dropped.
Homework is due on **Mondays 11pm**, except for weeks with midterms. **Submission is online** via Gradescope
(you should already be enrolled; if not, enroll using your @ucsd.edu email and the code MGEP28).

Instructions:

Instructions:

- Homework should be solved in groups of 3-4 students (you can change groups for different homeworks; students may be in different sections).
- Submit only one submission per group.
- No collaboration or discussion outside the groups is allowed (but if you are stuck on a problem, please come to discussion or office hours).

Participation is 10% of the total grade. For full participation grade, you need to collect 20 participation points. How to collect participation points:

- 1 point: coming to lecture and participating in clicker discussions (max 2 per week, not including midterms)
- 1 point: coming to discussion section (max 1 per week)
- 2 points: solving the weekly review quiz

We use Piazza for discussion forums: any questions that you have on the material, and finding other students for group study and homework.

You can access all previous classes through podcast.

Date | Subject | Chapter | Slides | HW |
---|---|---|---|---|

10/02/2017 | Logistics, introduction to automata | Sipser 0, 1.1 | slides | |

10/04/2017 | Formal definition of Deterministic Finite Automata (DFA) | Sipser 1.1 | slides | |

10/09/2017 | Regular languages, closure under: complementation, union | Sipser 1.1,1.2 | slides | HW1 due |

10/11/2017 | Formal definition of Nondeterministic Finite Automata (NFA) | Sipser 1.1,1.2 | slides | |

10/16/2017 | Equivalence of DFAs and NFAs | Sipser 1.2,1.3 | slides | HW2 due |

10/18/2017 | Equivalence of DFAs and regular expressions | Sipser 1.2,1.3 | slides | |

10/23/2017 | Limits of regular languages: the pumping lemma | Sipser 1.4 | slides | HW3 due |

10/25/2017 | More examples of pumping lemma, intro to Context Free Grammar (CFG) | Sipser 1.4, 2.1 | slides | |

10/30/2017 | Midterm 1 (in class) |
|||

11/01/2017 | Context Free Grammar (CFG), Push Down Automata (PDA) | Sipser 2.1 | slides | |

11/06/2017 | More on Push Down Automata (PDA) | Sipser 2.1 | slides | HW4 due |

11/08/2017 | Introduction to Turing machines (TM) | Sipser 3.1 | slides | |

11/13/2017 | Turing machines: more examples and equivalent models | Sipser 3.1,3.2 | slides | HW5 due |

11/15/2017 | More on models, encodings of inputs and proving decidability | Sipser 3.2,4.1 | slides | |

11/20/2017 | Proving decidability | Sipser 4.1 | slides | HW6 due |

11/22/2017 | Proving undecidability by diagonalization | Sipser 4.2 | slides | |

11/27/2017 | Midterm 2 (in class) |
|||

11/29/2017 | Reductions and the halting problem | Sipser 5.1 | slides | |

12/04/2017 | Introduction to complexity | Sipser 7.1,7.2,7.3 | slides | HW7 due |

12/06/2017 | Summary | slides | ||

12/14/2017 | Final exam |