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?

Please use this form to give feedback on the class, to help us improve it. Your answers are anonymous. Feel free to comment on any aspect of the class: lectures, discussion sessions, office hours, textbook, piazza, homework, review quizzes, exams, anything.
GO TO FORM

- Homework 1 due Monday 10/9 11pm
- Homework 1 solution
- Homework 2 due Monday 10/16 11pm
- Homework 2 solution
- Homework 3 due Monday 10/23 11pm
- Homework 3 solution
- Homework 4 due Monday 11/6 11pm
- Homework 4 solution
- Homework 5 due Monday 11/13 11pm
- Homework 5 solution
- Homework 6 due Monday 11/20 11pm
- Homework 6 solution

- Review quiz 1 due Friday 10/6 11pm
- Review quiz 2 due Friday 10/13 11pm
- Review quiz 3 due Sunday 10/22 11pm (note new due date)
- Review quiz 4 due Friday 10/29 11pm
- Review quiz 5 due Sunday 11/12 11pm
- Review quiz 6 due Friday 11/17 11pm

- Prof: Shachar Lovett, email: slovett@ucsd.edu, office hours: W 2-4pm in CSE 4234
- TAs:
- John Clara, email: jclara@ucsd.edu, office hours: M 2-3,4-5 in CSE basement hallway
- Nicholas Genise, email: ngenise@ucsd.edu, office hours: W 9-11am in B275
- Kaave Hosseini, email: skhossei@ucsd.edu, office hours: Th 1-3pm in common area outside 4232
- Chandana Lakshminarayana, email: clakshmi@ucsd.edu, office hours: F 2:30-4:30pm in B250A
- Sankeerth Rao, email: skaringu@ucsd.edu, office hours: Th 9-10am in B260A
- Kevin Yin, email: h3yin@ucsd.edu, office hours: M 12-2 in B260A
- Jiapeng Zhang, email: jiz173@ucsd.edu, office hours: F 11-1 in B215

- 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

Please use the following options when registering: (1) iClicker classic (2) no LMS.

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 | Reductions and the halting problem | Sipser 5.1 | slides | |

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

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 |