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?

In the first two weeks of the quarter (and whenever required) all lectures/discussions/office hours will be on zoom.
To simplify life, we will use the same zoom meeting room for all of them:
zoom link.
If you want to connect directly, the meeting id is 93416739827 and the password is cse105.

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

Lecture | MW | 5-6:20pm | Peterson 108 |

Discussion A01 | M | 4-4:50pm | Peterson 108 |

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

Professor | Shachar Lovett | slovett@ucsd.edu | Wed 3-4pm, CSE 4234 |

TA | Parth Doshi | pdoshi@ucsd.edu | Tue 12:30-1:30pm, CSE B275 |

TA | Satvik Gupta | sag005@ucsd.edu | Fri 5:00-6:00pm, CSE B275 (Tantative) |

TA | Tony Hu | toh008@ucsd.edu | Thu 9:30-10:30am, CSE B240A |

TA | Saketh Khandavalli | lkhandavalli@ucsd.edu | Wed 11:00am-12:00pm, CSE B215 |

TA | Sanju Koya | spkoya@ucsd.edu | Tue 3:30-4:30pm, CSE B260A |

TA | Venkat Krishnamohan | vkrishnamohan@ucsd.edu | Mon 10:00-11:00 am, CSE B240A |

TA | Nirmal Thomas | nithomas@ucsd.edu | Fri 10:00-11:00am, CSE B275 |

TA | Satish Yerva | syerva@ucsd.edu | Wed 1-2pm, CSE B260A |

Tutor | Dustin Lin | d6lin@ucsd.edu | Thurs 1:00-2:00pm, location TBD |

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 or the UCSD bookstore for about $20.

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 or the UCSD bookstore for about $20.

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)
- Homework: 30% (7 homeworks)

- 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 30% of the final grade. There will be 7 homeworks.
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 V8RJJK).

- Homework 1 (Deadline: 17 Jan 2022 11:59 PM)
- Homework 2 (Deadline: 24 Jan 2022 11:59 PM)

- 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).

I want to keep this class as interactive as possible, to help you follow lectures better and to help identify mis-understood concepts early on. For this we will use clicker for in person classes and zoom pools for remote classes.

We use Piazza for discussion forums: any questions that you have on the material, and finding other students for group study and homework. Please use public posts for general questions about the class or material, and private posts for personally relevant questions or questions that can reveal a solution or approach to a homework problem.

You can access all previous classes through podcast.

Your goal is to excel in this class **with integrity**.
It is an academic violation to:

- Ask others to give you homework or test answers
- Share your answers on homework or tests
- Work on the homework with anyone other than your homework partners
- Share answers or notes while taking an exam
- Search the internet or other resources not provided for the class for homework solutions
- Use chegg or similar websites/services to ask or get answers for homework or exams

Date | Subject | Chapter | Slides | Annotated slides | Videos | HW |
---|---|---|---|---|---|---|

01/03/2022 | Logistics, introduction to automata | Sipser 0, 1.1 | slides | annotated slides | video | |

01/05/2022 | Formal definition of Deterministic Finite Automata (DFA) | Sipser 1.1 | slides | annotated slides | video | |

01/10/2022 | Regular languages, closure under: complementation, union | Sipser 1.1, 1.2 | slides | annotated slides | video | |

01/12/2022 | Formal definition of Nondeterministic Finite Automata (NFA) | Sipser 1.1, 1.2 | slides | annotated slides | video | |

01/17/2022 | Martin Luther King, Jr. Holiday (no class) | HW1 due | ||||

01/19/2022 | Equivalence of DFAs and NFAs | Sipser 1.2, 1.3 | slides | annotated slides | video | |

01/24/2022 | Equivalence of DFAs and regular expressions | Sipser 1.2, 1.3 | slides | HW2 due | ||

01/26/2022 | Limits of regular languages: the pumping lemma | Sipser 1.4 | slides | |||

01/31/2022 | More examples of pumping lemma, intro to Context Free Grammar (CFG) | Sipser 1.4, 2.1 | slides | HW3 due | ||

02/02/2022 | Midterm 1 (in class) |
|||||

02/07/2022 | Context Free Grammar (CFG), Push Down Automata (PDA) | Sipser 2.1, 2.2 | slides | |||

02/09/2022 | More on Push Down Automata (PDA) | Sipser 2.2 | slides | |||

02/14/2022 | Introduction to Turing machines (TM) | Sipser 3.1 | slides | HW4 due | ||

02/16/2022 | Turing machines: more examples and equivalent models | Sipser 3.1, 3.2 | slides | |||

02/21/2022 | Presidents' Day Holiday (no class) | HW5 due | ||||

02/23/2022 | More on models, encodings of inputs and proving decidability | Sipser 3.2, 4.1 | slides | |||

02/28/2022 | Proving decidability | Sipser 4.1 | slides | HW6 due | ||

03/02/2022 | Proving undecidability by diagonalization | Sipser 4.2 | slides | |||

03/07/2022 | Reductions and the halting problem | Sipser 5.1 | slides | HW7 due | ||

03/09/2022 | Midterm 2 (in class) |
|||||

03/14/2022 | Final exam |