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?

- Homework 1, due Monday 10/14 midnight (solutions)
- Homework 2, due Monday 10/21 midnight (solutions)
- Homework 3, due Monday 10/28 midnight (solutions)
- Homework 4, due Tuesday 11/12 midnight (solutions)
- Homework 5, due Tuesday 11/19 midnight (solutions)
- Homework 6, due Monday 11/25 midnight (solutions)
- Homework 7, due Tuesday 12/3 5pm (solutions)

- Review quiz 1, due Friday 10/4 midnight (questions only) (solutions)
- Review quiz 2, due Friday 10/11 midnight (questions only) (solutions)
- Review quiz 3, due Friday 10/18 midnight (questions only) (solutions)
- Review quiz 4, due Friday 10/25 midnight (questions only) (solutions)
- Review quiz 5, due Friday 11/1 midnight (questions only) (solutions)
- Review quiz 6, due Friday 11/8 midnight (questions only) (solutions)
- Review quiz 7, due Sunday 11/17 midnight (questions only) (solutions)
- Review quiz 8, due Friday 11/22 midnight (questions only) (solutions)
- Review quiz 9, due Sunday 12/01 midnight (questions only) (solutions)
- Review quiz 10, due Friday 12/06 midnight

Role | Name | Office hours | |
---|---|---|---|

Professor | Shachar Lovett | slovett@ucsd.edu | Wed 10am-noon, CSE 4234 |

TA | Karthika Aravind | ksreejay@ucsd.edu | Mon 11:30 am - 1:30 pm, CSE B260A |

TA | Michael Borkowski | mborkows@ucsd.edu | Sat 11/30 2 pm - 5 pm, CSE 4217 Sun 12/8 1 pm - 5 pm, CSE 4258 |

TA | Dhiren Lad | dlad@ucsd.edu | Thur 2:00pm - 3:00pm, 7:30pm - 8:30pm CSE B240A |

TA | Sankeerth Rao | skaringu@ucsd.edu | Tue 8am-10am, CSE 4217 |

TA | Manish Singh | mksingh@ucsd.edu | Fri 1 pm - 3 pm, CSE B240A |

TA | Ritwik Vatsyayan | rvatsyay@ucsd.edu | Mon 6:30pm-8:30pm, CSE B240A |

TA | Lisa Xue | zixue@ucsd.edu | Tue 10am - 11am CSE B215, Wed 1pm - 2pm CSE B240A |

TA | Ahmed Youssef | a1yousse@ucsd.edu | Wed 8am - 9am CSE B250A, Wed 9am - 10am CSE B215A |

Tutor | Joshua Comes | jcomes@ucsd.edu | Wed 7pm-9pm, CSE B250A |

Type | Day | Time | Location |
---|---|---|---|

Lecture | MW | 5-6:20pm | Peterson (PETER) 110 |

Discussion A01 | W | 7-7:50pm | Cognitive Science Building (CSB) 002 |

Discussion A02 | W | 8-8:50pm | Cognitive Science Building (CSB) 002 |

Discussion A03 | F | 4-4:50pm | Center Hall (CENTR) 109 |

Discussion A04 | F | 5-5:50pm | Center Hall (CENTR) 109 |

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 about $19.

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 about $19.

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 is dropped)
- Homework: 20% (7 homeworks; 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 midnight**. **Submission is online** via Gradescope
(you should already be enrolled; if not, enroll using your @ucsd.edu email and the code M3DNJ3).

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. There are several ways in which you can get particiaption 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 register your i-Clicker here.
If you are asked to pay, please use this alternative form.

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/2019 | Logistics, introduction to automata | Sipser 0, 1.1 | slides | |

10/07/2019 | Formal definition of Deterministic Finite Automata (DFA) | Sipser 1.1 | slides | |

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

10/14/2019 | Formal definition of Nondeterministic Finite Automata (NFA) | Sipser 1.1, 1.2 | slides | HW1 due |

10/16/2019 | Equivalence of DFAs and NFAs | Sipser 1.2, 1.3 | slides | |

10/21/2019 | Equivalence of DFAs and regular expressions | Sipser 1.2, 1.3 | slides | HW2 due |

10/23/2019 | Limits of regular languages: the pumping lemma | Sipser 1.4 | slides | |

10/28/2019 | More examples of pumping lemma, intro to Context Free Grammar (CFG) | Sipser 1.4, 2.1 | slides | HW3 due |

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

11/04/2019 | Context Free Grammar (CFG), Push Down Automata (PDA) | Sipser 2.1, 2.2 | slides | |

11/06/2019 | More on Push Down Automata (PDA) | Sipser 2.2 | slides | |

11/11/2019 | Veterans day (no class) | HW4 due | ||

11/13/2019 | Introduction to Turing machines (TM) | Sipser 3.1 | slides | |

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

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

11/25/2019 | Proving decidability | Sipser 4.1 | slides | HW6 due |

11/27/2019 | Proving undecidability by diagonalization | Sipser 4.2 | slides | |

12/02/2019 | Reductions and the halting problem | Sipser 5.1 | slides | HW7 due |

12/04/2019 | Midterm 2 (in class) |
|||

12/12/2019 | Final exam |