CSE 105 - Theory of Computation, Winter 2022


Welcome to CSE 105! This course will help you answer fundamental questions about computing: In this course, we will explore what it means to be "computable". We begin with a very simple model of computation, and work our way to the most powerful, the Turing machine, named after Alan Turing, who formalized the notion of "algorithm" in this last model 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.


Remote instruction

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.

Class times

Note that the locations below are only for in person instruction. When the university is remote, we will use the zoom meeting room given above.
TypeDayTimeLocation
LectureMW5-6:20pmPeterson 108
Discussion A01M4-4:50pmPeterson 108

Instructors

RoleNameEmailOffice hours
ProfessorShachar Lovettslovett@ucsd.eduWed 3-4pm, CSE 4234
TAParth Doshipdoshi@ucsd.eduTue 12:30-1:30pm, CSE B275
TASatvik Guptasag005@ucsd.eduMon 11:00-12:00pm, CSE B275 (Tantative)
TATony Hutoh008@ucsd.eduThu 9:30-10:30am, CSE B240A
TASaketh Khandavallilkhandavalli@ucsd.eduWed 11:00am-12:00pm, CSE B215
TASanju Koyaspkoya@ucsd.eduTue 3:30-4:30pm, CSE B260A
TAVenkat Krishnamohanvkrishnamohan@ucsd.eduMon 10:00-11:00 am, CSE B240A
TANirmal Thomasnithomas@ucsd.eduFri 10:00-11:00am, CSE B275
TASatish Yervasyerva@ucsd.eduWed 1-2pm, CSE B260A
TutorDustin Lind6lin@ucsd.eduThurs 1:00-2:00pm, location TBD

Textbook

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.

Grading

The final grade will be composed as follows: A passing grade in the final exam (at least 50%) is required to pass the class. Letter grades will be assigned as follows: The designation of +/- inside a grade range is based on the instructor discretion, and will depend on the grade distribution as well as your particiaption in class and discussion, coming to office hours, and improvement throughout the class.

Homework

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

Participation

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.

Discussion forums

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.

Podcast

You can access all previous classes through podcast.

Academic integrity

Your goal is to excel in this class with integrity. It is an academic violation to: This is a partial list of common academic violations in this class. If you are not sure if some activity constitutes an academic violation or not, please ask us before doing it. We will report academic violations to the academic integrity office. See also the detailed academic integrity policy for more information.

Schedule

NOTE: Subject to change throughout the quarter.
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 annotated slides video HW2 due
01/26/2022 Limits of regular languages: the pumping lemma Sipser 1.4 slides annotated slides video
01/31/2022 More examples of pumping lemma, intro to Context Free Grammar (CFG) Sipser 1.4, 2.1 slides annotated slides video 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 annotated slides video
02/09/2022 More on Push Down Automata (PDA) Sipser 2.2 slides annotated slides video
02/14/2022 Introduction to Turing machines (TM) Sipser 3.1 slides video HW4 due
02/16/2022 Turing machines: more examples and equivalent models Sipser 3.1, 3.2 slides annotated slides video
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 annotated slides video
02/28/2022 Proving undecidability by diagonalization Sipser 4.2 slides annotated slides video HW6 due
03/02/2022 Reductions and the halting problem Sipser 5.1 slides video
03/07/2022 Summary slides annotated slides video HW7 due
03/09/2022 Midterm 2 (in class)
03/14/2022 Final exam